Skip to main content
Talentd

Minimum Value to Get Positive Step by Step Sum - Solution & Explanation

EasyArrayPrefix Sum13 min readAsked at: Amazon, Microsoft, Goldman Sachs +6
Practice this problem

Problem Statement

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.

 

Example 1:

Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
step by step sum
startValue = 4 | startValue = 5 | nums
  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
  (4 +2 ) = 6  | (5 +2 ) = 7    |   2

Example 2:

Input: nums = [1,2]
Output: 1
Explanation: Minimum start value should be positive.

Example 3:

Input: nums = [1,-2,-3]
Output: 5

 

Constraints:

  • 1 <= nums.length <= 100
  • -100 <= nums[i] <= 100

Approach Overview

Problem Overview: You are given an integer array nums. Starting with an unknown positive value startValue, you add each element in order and keep a running sum. The requirement is simple: the running sum must never drop below 1. The task is to compute the smallest possible starting value that guarantees this condition.

Approach 1: Calculate Minimum Start Value using Cumulative Sum (O(n) time, O(1) space)

Traverse the array while maintaining a running cumulative sum. Track the minimum value that this cumulative sum reaches during the traversal. If the lowest prefix sum becomes negative, the starting value must offset that dip so the total never falls below 1. Mathematically, the required start value is 1 - minPrefixSum. If the minimum prefix sum is already positive, the answer is simply 1. This works because every running total equals startValue + prefixSum, so ensuring the smallest prefix keeps the total ≥ 1 guarantees the rest will also be valid. The algorithm scans the array once and uses constant extra memory.

This approach relies on tracking prefix accumulation, which is a common technique in array problems and especially those involving prefix sum reasoning. You only store the current running sum and the minimum value encountered.

Approach 2: Prefix Sum with Constant Adjustment (O(n) time, O(1) space)

Another way to think about the problem is to explicitly compute the prefix sums and adjust them so the smallest prefix becomes 1. Iterate through nums, accumulate a prefix sum, and track the minimum prefix encountered. Instead of adjusting the prefix array itself, compute a constant shift that raises the minimum prefix to 1. That constant shift is the starting value. This interpretation emphasizes the idea that every prefix sum can be translated upward by the same constant to satisfy the constraint.

The logic is nearly identical to the cumulative-sum approach but framed as a transformation of the prefix sequence. It helps build intuition for similar problems where you normalize prefix values or maintain constraints across running totals. Because only two variables are maintained (current prefix and minimum prefix), the space complexity remains constant.

Recommended for interviews: The cumulative sum solution is the expected answer. It demonstrates that you recognize the prefix-sum pattern and can derive the minimum offset required to keep the running total positive. Explaining the minimum-prefix insight clearly usually matters more than the code itself. A brute-force simulation with increasing start values shows basic understanding, but interviewers typically expect the single-pass O(n) prefix analysis.

Approach 1: Calculate Minimum Start Value using Cumulative Sum

The idea is to simulate the step by step summation of the start value with the elements of the array. We maintain a running sum and adjust the start value such that this sum never drops below 1. At each step, if the running sum is less than 1, we calculate and update the new minimum start value needed to keep the running sum at least 1.

We iterate over the nums array, maintaining a cumulative running sum. We track the minimum value of this sum as min_sum. After processing all elements, the start value must be greater than or equal to 1 minus this minimum sum in order to ensure the step by step sum never falls below 1.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(1), as we are using a constant amount of space.

Try this approach in the editor →

Approach 2: Prefix Sum with Constant Adjustment

This approach is similar to the first but conceptualized through using prefix sums and adjusting the needed start value based on the lowest prefix sum reached. We cumulatively add each number and check if the prefix sum dips below a certain threshold, indicating the minimal adjustment needed for the start value.

By maintaining a prefix sum across the array, the minimum observed prefix sum is used to calculate the requisite start value. This ensures the prefix sum stays positive throughout iterations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n).
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Calculate Minimum Start Value using Cumulative Sum

Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(1), as we are using a constant amount of space.

Prefix Sum with Constant Adjustment

Time Complexity: O(n).
Space Complexity: O(1).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Cumulative Sum with Minimum Prefix TrackingO(n)O(1)Best general solution. Single pass and minimal memory.
Prefix Sum with Constant AdjustmentO(n)O(1)Useful when reasoning about shifting prefix sums or teaching prefix-sum transformations.

Video Solution

Minimum Value to Get Positive Step by Step Sum | Leetcode 1413 | Live coding session 🔥🔥🔥 • Coding Decoded • 4,272 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Value to Get Positive Step by Step Sum easy or hard?
Minimum Value to Get Positive Step by Step Sum is classified as an Easy problem. The key insight is recognizing that the smallest prefix sum determines the minimum starting value needed to keep all running totals positive.
Minimum Value to Get Positive Step by Step Sum Python/Java solution
Both Python and Java implementations follow the same logic: iterate through the array, accumulate the running sum, track the minimum prefix value, and return max(1, 1 - minPrefix). The algorithm runs in O(n) time and O(1) space in both languages.
How to solve Minimum Value to Get Positive Step by Step Sum in O(n)?
Iterate through the array while computing a running prefix sum. Track the smallest prefix value encountered during the traversal. If the minimum prefix sum is negative, the required starting value is 1 minus that value; otherwise it is 1. This single pass guarantees the step-by-step total never drops below 1.
What is the best approach for Minimum Value to Get Positive Step by Step Sum?
The optimal approach tracks the running prefix sum and records the minimum value reached during traversal. The smallest starting value required is 1 minus that minimum prefix sum. This guarantees every step stays at least 1. The algorithm runs in O(n) time with O(1) extra space.
Is Minimum Value to Get Positive Step by Step Sum asked at Google/Amazon/Meta?
Prefix sum and running-total constraint problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. While this exact question may vary, the underlying technique of tracking minimum prefix sums is a common interview pattern.
What data structure is used in Minimum Value to Get Positive Step by Step Sum?
The solution primarily uses simple variables to maintain a running sum and the minimum prefix value. Conceptually it relies on the prefix sum technique applied to an array, but no additional data structures like stacks or hash maps are required.
What is the time complexity of Minimum Value to Get Positive Step by Step Sum?
The optimal solution runs in O(n) time because the array is scanned once while maintaining a running sum and the minimum prefix value. Only constant extra variables are used, so the space complexity is O(1).

Ready to solve this problem?

Practice Minimum Value to Get Positive Step by Step Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays