Running Sum of 1d Array

Problem Overview

Given an array, return a new array where each element is the sum of itself and every element before it.

Why solve this?

The single simplest possible statement of the prefix-sum idea — every later prefix-sum, range-query and difference-array problem in this course is a variation of exactly this running total.

Pattern Recognition

Any time a problem repeatedly asks about the sum of everything up to index i, or the sum of a range, a running total computed once up front is almost always faster than re-summing a range from scratch each time.

Prerequisites

• No prior lessons required — this is the starting point for prefix-sum thinking.

Hints

1. You only need one running variable to build the whole output array.
2. runningSum[i] = runningSum[i-1] + nums[i] — each answer builds on the previous one.
3. You can build the answer in place, overwriting nums itself, if that's allowed.

Approach

Keep a single running total. Walk the array once, adding each element to the running total, and write that running total into the output at the same index. Because each output value only depends on the running total and the current element, one pass is enough.

Code

class Solution {
    public int[] runningSum(int[] nums) {
        int[] result = new int[nums.length];
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            result[i] = sum;
        }
        return result;
    }
}

Related Problems

• Reverse an Arrayeasy
• Second Largest Element in an Arrayeasy
• Plus Oneeasy
• Maximum Consecutive Oneseasy