What pattern does Running Sum of 1d Array use?

Running Sum of 1d Array is a Prefix Sum problem. The key question to ask is: If you know the running sum up to index i-1, what's the formula for the running sum at index i?

What is the time complexity of the brute-force approach to Running Sum of 1d Array?

The brute-force approach runs in O(n²) time and O(n) space.

← All problems

PremiumPrefix SumEasy

Running Sum of 1d Array

Asked at:AmazonGoogle

Given an array nums, return the running sum where runningSum[i] = sum of nums[0] through nums[i].

This is a premium problem.

Unlock Running Sum of 1d Array with both full courses, DSA and System Design, and every other premium problem.

See plans →Or learn Prefix Sum free first →

Problem

Given an array nums, return the running sum of nums where runningSum[i] = sum(nums[0] ... nums[i]).

Input

An integer array `nums`.

Output

An array where each element is the sum of all elements from index 0 to that index.

Examples

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

Output: [1,3,6,10]

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

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

The brute-force approach

For each index i, sum nums[0..i] from scratch.

result = []
for i in range(n):
    result.append(sum(nums[:i+1]))
return result

O(n²) — recomputing the sum from scratch each time.

Time: O(n²)Space: O(n)

Spotting the pattern

This is a Prefix Sum problem. The key question to ask yourself:

If you know the running sum up to index i-1, what's the formula for the running sum at index i?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.

Premium

Unlock the full guided solution

The Prefix Sum walkthrough for Running Sum of 1d Array: the progressive hint ladder, a row-by-row dry run, the optimized code, and an in-browser runner, plus both full courses, DSA and System Design, and every other premium problem.

Already finished Big-O and Hash Maps free? This picks up right where the path leads: same format, harder patterns, the ones that show up in every FAANG-style screen.

What you get

✓The full DSA course: concept lessons, drills, graded tests, and cold-read capstones for every pattern
✓The full System Design course: 20 building-block units for the design round, included at no extra cost
✓Stop going blank on algorithm problems. The hint ladder walks you to the answer without spoiling it.
✓Actually internalize the trace: dry runs walk state row by row so it clicks before you write a line
✓Know when to reach for each pattern. Every problem names the trigger so you spot it next time.
✓Write and run JS or Python in the browser with real test cases on every problem
✓Access every new problem, unit, and pattern guide as they ship weekly

Big_Wolverine_7575Founding Member· unprompted on Reddit

“This app finally made it click. I tried NeetCode, CTCI, and YouTube for years and still couldn't solve Two Sum. The beginner mental models for the patterns are genuinely so helpful. THANK YOU.”

Full access · both courses

Full access

$49 / year

or $9 / month

Now includes a C++ runner alongside JavaScript and Python.

LeetCode Premium is $159/year and doesn't teach you anything.

Less than one Udemy course, with guided problems instead of passive lectures.

One extra month of job searching costs more than a full year here.

✓Both courses, every unit: DSA + System Design
✓All 150 problems across 33 patterns, plus every new one
✓New problems and units weekly
✓Cancel anytime

Cancel anytime. Not useful within 7 days? Email for a full refund. Secured by Stripe.