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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Running Sum of 1d Array and Arrays problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →