Minimum Value to Get Positive Step by Step Sum: Prefix Sum Pattern

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.

This is LeetCode 1413: Minimum Value to Get Positive Step by Step Sum, and it is one of the cleanest introductions to the prefix sum pattern. The solution requires just a few lines, but the reasoning behind it reveals a powerful idea: instead of trying different starting values, you can compute exactly the right one by analyzing the prefix sums.

Why this problem matters

Prefix sums show up everywhere in array problems. They let you answer range queries in constant time, detect subarray patterns, and transform "cumulative" questions into simpler ones. This problem strips the prefix sum idea down to its essence: compute the running total, find the worst point, and offset it.

Many harder problems build on this same foundation. In "Subarray Sum Equals K," you use prefix sums with a hash map to count subarrays. In "Maximum Subarray," Kadane's algorithm is really tracking a running prefix sum and resetting when it goes negative. Understanding how prefix sums relate to running totals gives you a lens for all of these.

The beauty of LeetCode 1413 is that it asks you to reason backward from the prefix sums. You are not computing a sum and returning it. You are computing a sum, finding its minimum, and then using that minimum to determine a starting offset. This kind of reverse reasoning, where you derive a constraint from the prefix sums rather than just computing them, is a skill that transfers to much harder problems.

The key insight

Think about what happens as you walk through the array. At each position, you have accumulated a prefix sum. If you start with startValue, then after processing position i, your running total is startValue + prefixSum[i]. You need this to be at least 1 at every step.

The tightest constraint comes from the smallest prefix sum. If the minimum prefix sum across the entire array is minPrefixSum, then you need startValue + minPrefixSum >= 1. Rearranging gives you startValue >= 1 - minPrefixSum.

That is it. Find the minimum prefix sum, and the answer is max(1, 1 - minPrefixSum). You do not need to try different starting values or binary search. One pass through the array tells you exactly what startValue must be.

The solution

def min_start_value(nums: list[int]) -> int:
    prefix_sum = 0
    min_prefix = 0
    for num in nums:
        prefix_sum += num
        min_prefix = min(min_prefix, prefix_sum)
    return 1 - min_prefix

Let's walk through what each piece does.

The variable prefix_sum tracks the running total as you iterate through the array. At each step, you add the current element. The variable min_prefix records the smallest prefix sum seen so far.

Notice that min_prefix starts at 0, not at infinity. This is intentional. If all prefix sums are positive, the minimum prefix sum is effectively 0 (meaning no offset is needed), and the answer is 1 - 0 = 1. This handles the case where the array contains only positive numbers without any special logic.

At the end, 1 - min_prefix gives the answer directly. If min_prefix is negative (say -4), then 1 - (-4) = 5. If min_prefix is 0 or positive, the answer is 1, because startValue must be at least 1 by the problem constraints.

Visual walkthrough

Let's trace through nums = [-3, 2, -3, 4, 2] step by step. At each position, we compute the prefix sum and track the minimum. The minimum prefix sum determines how much offset we need.

The minimum prefix sum is -4, which occurs at index 2. So startValue = 1 - (-4) = 5. You can verify by adding 5 to each prefix sum: [2, 4, 1, 5, 7]. Every value is at least 1.

Complexity analysis

Time is O(n) where n is the length of the array. You make a single pass, doing constant work at each position: one addition and one comparison.

Space is O(1). You only need two variables (prefix_sum and min_prefix), regardless of the input size. There is no need to store the entire prefix sum array since you only care about the minimum.

The building blocks

1. Running prefix sum

The pattern of accumulating a running total as you scan through an array:

prefix_sum = 0
for num in nums:
    prefix_sum += num

This is the foundation of nearly every prefix sum problem. In "Subarray Sum Equals K," you store each prefix sum in a hash map. In "Range Sum Query," you precompute all prefix sums into an array. In this problem, you just track the running value and its minimum. The core loop is always the same: add the current element to a running total.

2. Tracking an extremum during a scan

The pattern of maintaining a running minimum (or maximum) as you iterate:

min_so_far = initial_value
for item in sequence:
    value = compute(item)
    min_so_far = min(min_so_far, value)

This appears in maximum subarray (Kadane's algorithm tracks a running minimum of prefix sums implicitly), in stock buy/sell problems (tracking the minimum price seen so far), and in many greedy algorithms. The idea is that you do not need a second pass to find the extremum. You compute it on the fly during the same scan that builds up the values.

Edge cases

Before submitting, think through these scenarios:

• All positive numbers nums = [1, 2, 3]: every prefix sum is positive, so min_prefix stays at 0. The answer is 1.
• All negative numbers nums = [-1, -2, -3]: prefix sums are [-1, -3, -6]. The minimum is -6, so the answer is 7.
• Single element, positive nums = [5]: prefix sum is 5, minimum is 0, answer is 1.
• Single element, negative nums = [-5]: prefix sum is -5, minimum is -5, answer is 6.
• Prefix sum hits exactly zero nums = [1, -1]: prefix sums are [1, 0]. The minimum prefix sum is 0, and the answer is 1. Note that a running total of exactly 0 is not enough; we need it to be at least 1.
• Large negative spike followed by recovery nums = [-10, 20]: the minimum prefix sum is -10, so the answer is 11, even though the final prefix sum is 10.

From understanding to recall

You have seen how one pass through the array, tracking the running prefix sum and its minimum, gives you the exact answer. The solution is short and the logic is clean. But under interview pressure, even simple solutions can trip you up.

Which variable do you initialize to 0 and which to the first element? Do you return 1 - min_prefix or -min_prefix + 1 or max(1, 1 - min_prefix)? These feel obvious when reading an explanation, but reproducing them from scratch is a different challenge.

Spaced repetition is how you close that gap. You practice writing the prefix sum loop, the minimum tracking, and the final calculation from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "find a starting value to keep a running total positive" and the code flows out without hesitation.

Related posts

• Maximum Subarray - Kadane's algorithm also tracks prefix sums and their minimum to find the best subarray
• Product of Array Except Self - Uses prefix and suffix products, a close relative of prefix sums
• Subarray Sum Equals K - Prefix sums combined with a hash map to count subarrays with a target sum

CodeBricks breaks this problem into its prefix sum and running minimum building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a prefix sum problem shows up in your interview, you do not think about it. You just write it.