Prerequisite: Loop Invariants — the first post in this series covers what an invariant is and how to state one. If the word "invariant" is new to you, start there.
The Problem (15 seconds)
Given an array nums, return an array where each element is the running sum up to that index.
Input: [1, 2, 3, 4]
Output: [1, 3, 6, 10]
// result[0] = 1
// result[1] = 1 + 2 = 3
// result[2] = 1 + 2 + 3 = 6
// result[3] = 1 + 2 + 3 + 4 = 10
LeetCode #1480 — Running Sum of 1D Array
The Obvious Mistake
Most engineers look at this problem and see a loop inside a loop.
"For each index, add up everything before it." That's the instinct. It's technically correct. It's also exactly the kind of thinking that produces O(n²) code when O(n) was sitting right there.
// Brute force — recompute the sum from scratch for each index
function runningSum(nums: number[]): number[] {
const result: number[] = [];
for (let i = 0; i < nums.length; i++) {
let sum = 0;
for (let j = 0; j <= i; j++) {
sum += nums[j]!;
}
result.push(sum);
}
return result;
}
O(n²). For each element, summing everything from the start again. But by the time you're computing result[3], you already know result[2].
You already did that work. Why are you doing it again?
The Moment It Clicks
You're not computing sums from scratch. You're carrying one forward.
result[i] = result[i-1] + nums[i]
Each running sum is just the previous running sum plus the current number. You don't look backward — you carry the answer forward. That shift in mental model — from "compute everything again" to "carry the last answer forward" — is the entire insight. Every problem after this is just a variation on it.
This is the running state pattern: instead of recomputing from scratch, maintain a variable that accumulates as you go.
The Invariant
At step
i,sumequals the total ofnums[0]throughnums[i-1].
After adding nums[i], sum becomes the total through nums[i] — which is exactly result[i].
Let's trace it:
nums = [1, 2, 3, 4]
Before loop: sum = 0 → total of nothing ✓
i=0: sum = 0 + 1 = 1 → total of [1] ✓ → result = [1]
i=1: sum = 1 + 2 = 3 → total of [1,2] ✓ → result = [1,3]
i=2: sum = 3 + 3 = 6 → total of [1,2,3] ✓ → result = [1,3,6]
i=3: sum = 6 + 4 = 10 → total of [1,2,3,4] ✓ → result = [1,3,6,10]
The invariant held at every step. The result is guaranteed correct.
Solution
TypeScript:
function runningSum(nums: number[]): number[] {
const result: number[] = [];
let sum = 0;
for (const num of nums) {
sum += num;
result.push(sum);
}
return result;
}
Python:
def running_sum(nums: list[int]) -> list[int]:
result: list[int] = []
total = 0
for num in nums:
total += num
result.append(total)
return result
Complexity: O(n) time, O(n) space (for the result array).
In-place variant (modifies the input):
function runningSum(nums: number[]): number[] {
for (let i = 1; i < nums.length; i++) {
nums[i]! += nums[i - 1]!;
}
return nums;
}
The Foundation of Everything Hard
Running Sum is the simplest prefix sum — a running total stored at every index. That stored total is the key that unlocks a whole class of harder problems:
-
Subarray Sum Equals K (#560) — does any slice of the array add up to exactly
k? -
Range Sum Query (#303) — what's the total between index
iand indexj? - Maximum Subarray / Kadane's (#53) — which contiguous slice has the biggest sum?
- Product of Array Except Self (#238) — same idea, with multiplication instead of addition
You don't need to know how to solve these yet. Just notice: every one of them is asking a question that gets dramatically easier once you have the running totals precomputed. The only thing that changes problem to problem is the operation — sum, max, product. The carry-forward structure is identical.
People skip this problem because it's labeled "Easy." That's the mistake. The "Easy" label measures implementation difficulty, not conceptual weight. You'll hit Subarray Sum Equals K and wonder why prefix sums feel unfamiliar — it's because you rushed past the problem that introduced them.
It's Not Just This Problem
Here's the real pattern underneath all of it.
When you see yourself writing a nested loop where the inner loop starts at index 0 every single time — that's the signal. You're recomputing something you already know. The fix is always the same: carry it forward in a variable.
Kadane's carries the best sum forward. Sliding Window carries the window total forward. Dynamic Programming carries the answer to the previous subproblem forward. Different problems, different names — same move underneath.
The shape changes. The principle doesn't.
Don't recalculate. Accumulate. Running sum is the first time you'll see this idea. It won't be the last.
How to Recognize This Pattern
You need the accumulator pattern when:
- The answer at position
idepends on all previous positions (not just neighbors) - You catch yourself writing a nested loop where the inner loop starts at 0 every time
- The problem says "running", "cumulative", "prefix", or "so far"
The signal: "I'm recomputing something I already know." The fix is always the same — carry it forward in a variable.
There's a version of you that solves this problem in five minutes, checks it off, and moves on without thinking about it again. That version hits a wall at Subarray Sum Equals K and can't figure out why the prefix sum lookup feels alien.
The other version pauses here. States the invariant. Traces through it manually. Asks: "Where else does this carry-forward idea show up?" That version arrives at Kadane's with the pattern already loaded. The algorithm makes sense on first reading because the shape is familiar.
This is an easy problem. That doesn't mean it's a small one.
What pattern did you miss the first time you solved it — and only understood later when you hit a harder version of the same idea?
Next in the series: Contains Duplicate (#217) — where you'll learn the "have I seen this before?" pattern with hash sets. Then Valid Anagram (#242) and finally Two Sum (#1) — invariant + lookup + accumulator, all together.
Top comments (0)