How do you approach Running Sum of 1d Array?

Keep a single accumulator that carries the sum of everything seen so far.

What is the time complexity of Running Sum of 1d Array?

Time complexity: O(n). Space complexity: O(1) extra, or O(n) if you build a separate output array..

What are common mistakes on Running Sum of 1d Array?

Not seeding the map with a zero-sum prefix, which loses every subarray starting at index 0. Counting the current prefix before checking for its complement, so a zero-sum range matches itself. Mixing inclusive and exclusive bounds between building the array and querying it - a consistent, invisible off-by-one.

gitGood.dev

← Back to problems

Running Sum of 1d Array

EasyAlgorithms

Description

Given an array nums, return its running sum.

The running sum is defined as runningSum[i] = sum(nums[0] ... nums[i]).

This is the prefix-sum array in its purest form - every prefix-sum problem starts by building this, even when the final solution never materializes the whole array.

Example 1

Input: nums = [1,2,3,4]

Output: [1,3,6,10]

Example 2

Input: nums = [1,1,1,1,1]

Output: [1,2,3,4,5]

Example 3

Input: nums = [3,1,2,10,1]

Output: [3,4,6,16,17]

Constraints

- 1 <= nums.length <= 1000 - -10^6 <= nums[i] <= 10^6

Running Sum of 1d Array: approach, complexity and pitfalls

An easy prefix sum problem, graded against 6 test cases (3 of them hidden).

The pattern: Prefix Sum

Precomputed cumulative totals so any range query becomes one subtraction.

Reach for it when you see: Repeated range-sum queries, or counting subarrays that sum to a target.

If you are stuck

Show the 3-step hint ladder

Keep a single accumulator that carries the sum of everything seen so far.
At index i, the answer is accumulator + nums[i] - then update the accumulator to that value.
You can write the result into a new array, or overwrite nums in place: nums[i] += nums[i - 1] starting at i = 1.

The optimal approach

Show the approach: Prefix sums in one pass

Walk the array once carrying a running total. At each index, add the current element to the total and write the total out. That is the whole algorithm - and the array it produces is the tool the harder prefix-sum problems rely on, because the sum of any range `[i, j]` is `prefix[j] - prefix[i - 1]`, an O(1) lookup after O(n) setup.

The in-place variant (`nums[i] += nums[i - 1]`) uses no extra space, which matters when the caller does not need the original array.

Time: O(n)
Space: O(1) extra, or O(n) if you build a separate output array.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Prefix Sum mistakes

These apply to the pattern as a whole, not just this problem.

Not seeding the map with a zero-sum prefix, which loses every subarray starting at index 0.
Counting the current prefix before checking for its complement, so a zero-sum range matches itself.
Mixing inclusive and exclusive bounds between building the array and querying it - a consistent, invisible off-by-one.