What is the brute force approach and complexity for Running Sum of 1d Array?

For each index, add up nums[0..i] from scratch with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Running Sum of 1d Array?

One pass: running[i] = running[i−1] + nums[i], done in place with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Running Sum of 1d Array?

Look for key signals in the prompt: "sum of nums[0] up to nums[i]" indicates A total that always starts at index 0 → a prefix (running) sum.; "for every index" indicates We need all the totals, so build them in one left-to-right pass.; "each total includes the one before" indicates total(i) = total(i − 1) + nums[i] → one addition per index..

Running Sum of 1d Array

Easy·LeetCode #1480Basic Anchor

LeetCode

Jump:

30-Second Mental ModelPrefix Sum (running total)

Complexity:O(N²)→O(N)

Key Insight

The total up to i is just the total up to i − 1 plus nums[i]. So walk once from left to right and add the previous total into the current cell. We can even store it back into nums, because we never need the old value again.

Core Validity Invariant

Before we handle index i, the cell nums[i − 1] already holds the full total of everything before i. That one fact is all we need.

Problem

You are given an integer array nums.

Build a new array where position i holds the total of everything from nums[0] up to and including nums[i]. This is called the running sum.

Input

An integer array nums.

Output

An array of the same length, where element i is nums[0] + nums[1] + … + nums[i].

Example 1

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

Output: [1, 3, 6, 10]

1 = 1, 3 = 1+2, 6 = 1+2+3, 10 = 1+2+3+4.

Example 2

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

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

Each new 1 raises the total by one.

Example 3

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

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

3, then 3+1 = 4, then 4+2 = 6, then 6+10 = 16, then 16+1 = 17.

Constraints

• 1 ≤ nums.length ≤ 1000
• −10^6 ≤ nums[i] ≤ 10^6
• The biggest possible total is 1000 · 10^6 = 10^9, which still fits in an `int`.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
What is the answer at index 0? Do I need to add anything?
2.
Write the totals for index 2 and index 3 side by side. What do they share?
3.
If I already know the total up to index i − 1, how much extra work is the total up to i?
4.
Do I still need the original nums[i] after I have used it once?
5.
Is the answer at index i "up to i" or "before i"? Does that matter?

Brute force approach

Idea

The answer at index i is the sum of nums[0..i]. So for every i, start a fresh sum at 0 and add every element from 0 to i.

Thinking process

1
The definition says "sum of the first i + 1 elements". The most direct code just does that.
2
For each i, loop j from 0 to i and add nums[j].
3
Store the sum in the result array.
4
It is correct, but index 0 gets added n times, index 1 gets added n − 1 times, and so on.

Visual

Orange cells were already added for the previous index — brute force adds them again from the start.

Brute force re-addsnums = [3, 1, 2, 10, 1, -4, 5]step 1/7

nums

-4

▲i

result

Work

this index: 1 additions
re-added: 0
total additions: 1

Index 0: one addition

Index 0: start from 0 and add nums[0..0] → 3.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);

        // For every index i, add up nums[0..i] from scratch.
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = 0; j <= i; j++) {
                sum += nums[j];
            }
            result[i] = sum;
        }
        return result;
    }
};

class Solution {
    public int[] runningSum(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];

        // For every index i, add up nums[0..i] from scratch.
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = 0; j <= i; j++) {
                sum += nums[j];
            }
            result[i] = sum;
        }
        return result;
    }
}

class Solution:
    def runningSum(self, nums: list[int]) -> list[int]:
        n = len(nums)
        result = [0] * n

        # For every index i, add up nums[0..i] from scratch.
        for i in range(n):
            current_sum = 0
            for j in range(i + 1):
                current_sum += nums[j]
            result[i] = current_sum
        return result

export function runningSum(nums: number[]): number[] {
    const n = nums.length;
    const result: number[] = new Array(n);

    // For every index i, add up nums[0..i] from scratch.
    for (let i = 0; i < n; i++) {
        let sum = 0;
        for (let j = 0; j <= i; j++) {
            sum += nums[j];
        }
        result[i] = sum;
    }
    return result;
}

Complexity

Time O(N²)Space O(1)

The inner loop runs 1 + 2 + … + n = n(n+1)/2 times. With n = 1000 that is about 500,000 additions — it passes here, but it is the kind of repeated work the whole Prefix Sum pattern is built to remove. Only O(1) extra memory besides the output array.

Optimized approach

Idea

Start from brute force

Brute force computes the total up to i by adding nums[0..i], then throws it away and adds nums[0..i+1] from scratch for the next index.

Find the repeated work

The total up to i + 1 contains the whole total up to i. Brute force rebuilds that shared part every time, so the first elements get added again and again.

Define the state — what variables do I need?

i: The index we are filling in now.
nums[0..i−1]: Already turned into running totals. nums[i − 1] is the sum of the original nums[0..i−1].
nums[i..n−1]: Still the original values, not touched yet.

Define validity

Before we handle index i, the cell nums[i − 1] already holds the full total of everything before i. That one fact is all we need.

Define the transitions — when does each pointer move, and why is it safe?

i = 0

Do nothing

The total up to index 0 is just nums[0] itself.

Every i from 1 to n − 1

nums[i] += nums[i − 1]

nums[i − 1] is already the total of everything before i, and nums[i] is still its original value. Their sum is the total up to i.

What does the current window add to the answer?

Each step fills one answer cell with one addition. After the last step, every cell holds its running total.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        // nums[i - 1] already holds the total of nums[0..i-1],
        // so the total up to i is that plus the original nums[i].
        for (int i = 1; i < (int)nums.size(); i++) {
            nums[i] += nums[i - 1];
        }
        return nums;   // nums[0] is already its own running total
    }
};

class Solution {
    public int[] runningSum(int[] nums) {
        // nums[i - 1] already holds the total of nums[0..i-1],
        // so the total up to i is that plus the original nums[i].
        for (int i = 1; i < nums.length; i++) {
            nums[i] += nums[i - 1];
        }
        return nums; // nums[0] is already its own running total
    }
}

class Solution:
    def runningSum(self, nums: list[int]) -> list[int]:
        # nums[i - 1] already holds the total of nums[0..i-1],
        # so the total up to i is that plus the original nums[i].
        for i in range(1, len(nums)):
            nums[i] += nums[i - 1]
        return nums

export function runningSum(nums: number[]): number[] {
    // nums[i - 1] already holds the total of nums[0..i-1],
    // so the total up to i is that plus the original nums[i].
    for (let i = 1; i < nums.length; i++) {
        nums[i] += nums[i - 1];
    }
    return nums;
}

Complexity

Time O(N)Space O(1)

If you are not allowed to change the input, copy it first or write into a new array. The idea is the same. It works in place.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each index, add up nums[0..i] from scratch	O(N²)	O(1)
Optimal	One pass: running[i] = running[i−1] + nums[i], done in place	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“sum of nums[0] up to nums[i]”A total that always starts at index 0 → a prefix (running) sum.
“for every index”We need all the totals, so build them in one left-to-right pass.
“each total includes the one before”total(i) = total(i − 1) + nums[i] → one addition per index.

Total from the start+needed at every index+each total extends the previous one→Prefix Sum (running total)

This is the anchor of the Static range sum sub-pattern. Here we only build the running totals. The next two questions use the same totals to answer any range sum with one subtraction. To make that subtraction clean, they shift the array by one and put a 0 in front — see the first mistake below for how the two versions line up.

Don't make this mistake

Mixing up the running sum with the "prefix with a leading 0"

✗ // running[i] = nums[0..i] (this problem) // then using it for a range query: sum(l, r) = running[r] - running[l - 1]; // crashes when l = 0

✓ // prefix has size n + 1 and prefix[0] = 0 // prefix[i] = nums[0..i-1] (sum BEFORE index i) sum(l, r) = prefix[r + 1] - prefix[l];

There are two common versions. Running sum (this problem): same length as nums, and running[i] includes nums[i]. Prefix with a leading 0 (used for range queries): length n + 1, prefix[0] = 0, and prefix[i] is the sum of everything before i. So prefix[i + 1] = running[i]. Use the running sum when the question wants the totals themselves. Use the leading-0 version when you will subtract two totals to get a range: it never needs index −1. Most off-by-one bugs in this pattern come from using one version's formula on the other.

Starting the loop at i = 0

✗ for (int i = 0; i < n; i++) nums[i] += nums[i - 1];

✓ for (int i = 1; i < n; i++) nums[i] += nums[i - 1];

At i = 0 there is nothing before it, and nums[-1] reads outside the array. Index 0 is already its own total.

Adding the original value instead of the running total

✗ result[i] = nums[i - 1] + nums[i]; // nums is never updated

✓ result[i] = result[i - 1] + nums[i];

You must add the total so far, not just the previous element. The wrong version gives the sum of two neighbours, e.g. [1,2,3,4] → [1,3,5,7] instead of [1,3,6,10].

Reaching for a sliding window

Pattern-confusion trap. A sliding window is for a range that moves (its left end goes forward). Here every total starts at index 0 — the left end never moves — so there is nothing to shrink. It is just a running total.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Prefix Sum translate into production architectures and low-level memory mechanics.

LLD Architecture