06 · Mindset & Problem Solving
#1480 Running Sum of 1d Array
the problem
In plain words
Return an array where element i is nums[0] + nums[1] + … + nums[i].
in nums = [1,2,3,4]
out [1,3,6,10]
in nums = [3,1,2,10,1]
out [3,4,6,16,17]
- 1 ≤ nums.length ≤ 1000
- -10⁶ ≤ nums[i] ≤ 10⁶
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternPrefix sums
The running sum at i is the running sum at i − 1 plus nums[i]. Reuse the previous answer instead of re-adding everything.
solutions
From brute force to optimal
For every i, add nums[0..i] from scratch.
- For each i, loop k = 0..i and add.
1 + 2 + … + n = n(n+1)/2 additions.
The output array.
class Solution { public int[] runningSum(int[] nums) { int[] out = new int[nums.length]; for (int i = 0; i < nums.length; i++) for (int k = 0; k <= i; k++) out[i] += nums[k]; // re-add everything each time return out; }}Keep sum as you go and write it into a new array.
- sum = 0.
- For each i: sum += nums[i]; out[i] = sum.
One addition per element.
A new output array.
class Solution { public int[] runningSum(int[] nums) { int[] out = new int[nums.length]; int sum = 0; for (int i = 0; i < nums.length; i++) { sum += nums[i]; // carry the total forward out[i] = sum; } return out; }}nums[i] += nums[i − 1], left to right.
- For i from 1: nums[i] += nums[i − 1].
- Return nums.
n − 1 additions.
Overwrites the input (ask first whether that's allowed).
class Solution { public int[] runningSum(int[] nums) { for (int i = 1; i < nums.length; i++) { // nums[0] is already its own running sum nums[i] += nums[i - 1]; // previous cell already holds the sum before i } return nums; }}Dry run
in the room
How to say it in the interview
talk track
- Ask: may I modify the input? That decides between the in-place and the new-array version.
- Mention overflow: max |sum| = 1000 × 10⁶ = 10⁹ < 2³¹ − 1, so int is safe here.
traps
- Starting the in-place loop at i = 0 —
nums[i - 1]is thennums[-1]and throws. - Overwriting the input when the interviewer wanted it kept — ask first.
what they ask next
Follow-ups
Sum of any range [l, r] many times?
Build prefix sums once; each query is prefix[r+1] − prefix[l] in O(1) (LC 303).
before you submit
Edge cases to test
- One element: the answer is the array itself.
- Negative numbers: the running sum can go down, or back to 0.
- Largest input: 1000 × 10⁶ = 10⁹ still fits in an int (limit ≈ 2.147·10⁹).
practise next
Similar problems
- #303Range Sum Query - ImmutableEasyin Hashing
- #560Subarray Sum Equals KMediumin Hashing