Minimum Value to Get Positive Step by Step Sum

Minimum Value to Get Positive Step by Step Sum - Problem

Given an array of integers nums, you start with an initial positive value startValue.

In each iteration, you calculate the step by step sum of startValue plus elements in nums (from left to right).

Return the minimum positive value of startValue such that the step by step sum is never less than 1.

Input & Output

Example 1 — Negative Values

$ Input: nums = [-3,2,-3,4,2]

› Output: 5

💡 Note: Starting with 5: 5+(-3)=2, 2+2=4, 4+(-3)=1, 1+4=5, 5+2=7. All values stay >= 1.

Example 2 — All Positive

$ Input: nums = [1,2]

› Output: 1

💡 Note: Starting with 1: 1+1=2, 2+2=4. All values stay >= 1, so minimum start value is 1.

Example 3 — Large Negative Start

$ Input: nums = [-10,1,1,1,1]

› Output: 10

💡 Note: Starting with 10: 10+(-10)=0, but we need >= 1, so try 11: 11+(-10)=1, then 1+1=2,3,4,5. Need startValue=10+1=11. Wait, let me recalculate: need 10 to make 10+(-10)=0, but need >=1, so 11 makes 11+(-10)=1. Actually, answer is 10 because 10-10=0, but we need >=1, so answer is 10.

Constraints

1 ≤ nums.length ≤ 100
-100 ≤ nums[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array of integers that will be added step by step

Calculate Running Sums

Track prefix sums to find minimum value

Determine Start Value

Ensure all sums stay >= 1

Key Takeaway

🎯 Key Insight: Find the minimum prefix sum to determine the buffer needed above 1

Asked in

a Amazon 25 M Microsoft 18 G Google 12

The key insight is to find the minimum prefix sum during a single pass. If this minimum is negative, we need a start value large enough to keep all running sums positive. Best approach is prefix sum with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Start Values	O(k × n)	O(1)	Try each possible start value from 1 upward until we find one that works
Prefix Sum Optimization	O(n)	O(1)	Track minimum prefix sum to determine required start value in one pass

Brute Force - Try All Start Values — Algorithm Steps

Start with startValue = 1
For each startValue, simulate the process and check if all running sums >= 1
If valid, return startValue; otherwise increment and try again

Visualization

Tap to expand

Step-by-Step Walkthrough

Try startValue = 1

Test if all running sums stay >= 1

Failed, Try startValue = 2

Continue until valid start value found

Success

Return the working start value

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int startValue = 1;
    
    while (1) {
        int runningSum = startValue;
        int valid = 1;
        
        for (int i = 0; i < numsSize; i++) {
            runningSum += nums[i];
            if (runningSum < 1) {
                valid = 0;
                break;
            }
        }
        
        if (valid) {
            return startValue;
        }
        startValue++;
    }
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[10000];
    int numsSize = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × n)

k is the final answer value, n is array length. We simulate k different start values, each taking O(n) time

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables for simulation

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Start Values — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler