Return the running (prefix) sum of the array: each output element is the sum of all input elements up to and including that index.
runningSum(nums)
Input format: space-separated integers. Output the running sums, space-separated.
[1, 2, 3, 4] // → [1, 3, 6, 10]
[3, 1, 2] // → [3, 4, 6]
[] // → []
Each output is the sum of everything up to and including that position. The naive way follows the definition literally: re-sum from the start for every position. That repeats enormous work — the sum for position 5 shares nearly all its terms with position 4, but a fresh re-summation throws that overlap away.
The sum through position i is just the sum through i-1, plus the new element at i. Each answer is one addition away from the previous one — no need to revisit earlier elements at all.
By the end, every output is produced with one addition per element.
Brute force costs O(n) per output position across n positions — O(n²) total, millions of redundant additions for a few thousand numbers. The running-total approach does constant work per element — O(n), the best possible since you must look at every element once.
This — deriving a value cheaply from the immediately preceding one instead of recomputing from scratch — is one of the most common ways to turn quadratic brute force into linear, and it's the same idea behind prefix sums generally: once you have running totals everywhere, any contiguous range's sum is just two stored totals apart, no re-summing needed.
def running_sum(nums):
result = []
total = 0
for n in nums:
total += n
result.append(total)
return result
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.