Running Sum of 1D Array — DSA

Problem

Given an array nums, return an array runningSum where runningSum[i] is the sum of all elements from index 0 through i (inclusive).

Input:  [1, 2, 3, 4]        →   [1, 3, 6, 10]
Input:  [3, 1, 2, 10, 1]    →   [3, 4, 6, 16, 17]
Input:  [1, 1, 1, 1, 1]     →   [1, 2, 3, 4, 5]

The output has the same length as the input.
This running total is a prefix sum array. Once you have it, the sum of any range nums[l..r] is prefix[r] - prefix[l-1] in O(1). That's the foundation for Subarray Sum Equals K and range-sum queries.

Examples

Example 1

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

Output: [1,3,6,10]

Explanation: runningSum = [1, 1+2, 1+2+3, 1+2+3+4].

Example 2

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

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

Explanation: Each step adds exactly 1.

Constraints

•1 <= nums.length <= 1000
•-10^6 <= nums[i] <= 10^6

Hints

Hint 1

This is the prefix sum concept in its most literal form — the output array IS the sequence of prefix sums.

Hint 2

You don't need a separate output array allocated up front and filled in a second pass — you can build it in place.

Hint 3

Each output value only depends on the previous output value plus the current input — one running total, one pass.

Solutions

public int[] runningSumBruteForce(int[] nums) {
    int[] result = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = 0; j <= i; j++) sum += nums[j]; // resum from scratch for every output position
        result[i] = sum;
    }
    return result;
}

Time: O(n^2) · Space: O(n) for the output array