Given an array, return its running sum. Position i of the answer is the sum of every number from index 0 up to i.
DSA Animator › DSA Revision › Arrays › Running Sum of 1D Array
Remember: prefix sum at i equals prefix sum at i minus 1, plus the value at i. This prefix sum idea is the base of many harder array problems. The video solves Running Sum of 1D Array (LeetCode 1480, Easy) with the Prefix Sum pattern from the Arrays topic, and you can replay every step in the interactive Running Sum of 1D Array animation.
Given an array, return its running sum. Position i of the answer is the sum of every number from index 0 up to i.
For 1, 2, 3, 4, the running sum is 1, 3, 6, 10. For example, 6 is 1 plus 2 plus 3.
The brute force re-adds everything from the start for each position. That's O of n squared, and it repeats the same additions again and again.
Each running sum is the previous running sum, plus the current number. So walk left to right, and add the previous value into the current one, in place.
Index 0 stays 1, because nothing comes before it. Index 1 becomes 2 plus 1, which is 3. Index 2 becomes 3 plus 3, which is 6. Index 3 becomes 4 plus 6, which is 10. The array now holds the running sum: 1, 3, 6, 10.
In code, start the loop at index 1. Add the value just before into the current value. One pass, so it's O of n time, and O of 1 extra space.
Remember: prefix sum at i equals prefix sum at i minus 1, plus the value at i. This prefix sum idea is the base of many harder array problems.