Skip to main content

1480. Running Sum of 1d Array

easy

Given an array nums, return the running sum where runningSum[i] = sum of nums[0..i]. A foundational prefix-sum warm-up that unlocks a whole family of range-query problems.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]..nums[i]). Return the running sum of nums.

Constraints

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

Examples

Example 1

Input
nums = [1,2,3,4]
Output
[1,3,6,10]

Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

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]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

The naive approach recomputes a sum for every index. Can you reuse the work from the previous index?

Hint 2

Notice runningSum[i] = runningSum[i-1] + nums[i]. That is the entire algorithm.

Hint 3

You can do this in place by mutating nums itself to save the extra array allocation.

Solution approach

Reveal approach

Walk the array left to right while keeping a single accumulator. At index i, set nums[i] += nums[i-1] (or write to a fresh result array if mutation is forbidden). The trick is recognising that each running sum is one addition away from the previous one, which collapses what looks like an O(n^2) double-loop into a single linear pass. This same prefix-sum primitive powers range-sum queries, equilibrium-index problems, and 2D summed-area tables.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • prefix-sum

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Google

More Arrays practice problems

See all Arrays problems →