Running Sum of 1d Array
Problem statement
Given an integer array nums, return a new array out of the same length where out[i] is the sum of nums[0] through nums[i], inclusive. This is also called a cumulative sum or prefix sum.
Examples
Example 1
Input: nums = [2, 5, -1, 4]
Output: [2, 7, 6, 10]
Explanation: 2, then 2 + 5, then 2 + 5 - 1, then 2 + 5 - 1 + 4.
Example 2
Input: nums = [0, 0, 3]
Output: [0, 0, 3]
Hints
Approach
Carry the total forward. Each position is the previous running total plus the current element, so one pass is enough. You can even write the totals back into nums itself.
- For
ifrom1ton - 1:nums[i] += nums[i - 1]. - Return
nums.
After step 1 runs for index i, nums[i - 1] already holds the sum up to i - 1, which is exactly what the update needs.
O(n)Space O(1) extraclass Solution: def runningSum(self, nums: list[int]) -> list[int]: for i in range(1, len(nums)): nums[i] += nums[i - 1] # previous slot already holds its running total return numsFollow-up questions
- Using the running sums, return the sum of any range
[l, r]in constant time. - Compute a running maximum instead of a running sum.
Frequently asked questions
On this problem, yes, and it saves memory. In real code, ask first: callers may not expect their list to change. Copy it (out = nums[:]) if the original is needed later.
The running sum is the building block for a whole family of problems: range sums in O(1), pivot indices, and counting subarrays with a given sum. Understanding it well makes those much easier.
Turning per-minute counts into cumulative totals, like bytes transferred so far today or requests served since the last deploy. Monitoring counters are stored as running totals for exactly this reason: the amount in any interval is one subtraction.