Running Sum of 1D Array — Practice

Problem

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

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