Running Sum of 1D Array

Problem Link

1480. Running Sum of 1D Array – LeetCode

Problem Statement

Given an integer array nums, compute and return the running sum of the array.

The running sum is defined as:

runningSum[i] = nums[0] + nums[1] + ... + nums[i]

Examples

• Input: nums = [1, 2, 3, 4]
  Output: [1, 3, 6, 10]
  Explanation:
  1, 1+2=3, 1+2+3=6, 1+2+3+4=10

• Input: nums = [1, 1, 1, 1, 1]
  Output: [1, 2, 3, 4, 5]

• Input: nums = [3, 1, 2, 10, 1]
  Output: [3, 4, 6, 16, 17]

Constraints

• 1 <= nums.length <= 1000

• -10⁶ <= nums[i] <= 10⁶

Intuition

This problem is a straightforward prefix computation. You’re asked to construct a new array where each element at index i is the cumulative sum of all elements from index 0 to i.

We solve it iteratively by:

• Initializing the result array.

• Keeping a running total and updating it as we iterate through the input.

This is also known as a Prefix Sum problem.

Approach

1. Initialize a result array ans[] of the same length as nums.

2. Set ans[0] = nums[0].

3. Iterate from index 1 to the end:

   • For each i, set ans[i] = ans[i-1] + nums[i]

4. Return ans.

Java Code

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

Time and Space Complexity

• Time Complexity: O(n)
  We process each element exactly once.

• Space Complexity: O(n)
  We use an output array ans of size n.

Note: If modifying the input array is allowed, we can do it in-place with O(1) space by updating nums[i] += nums[i-1].

Dry Run

Input:

nums = [3, 1, 2, 10, 1]

Steps:

• ans[0] = 3

• ans[1] = 3 + 1 = 4

• ans[2] = 4 + 2 = 6

• ans[3] = 6 + 10 = 16

• ans[4] = 16 + 1 = 17

Output:

[3, 4, 6, 16, 17]

Conclusion

This is a classic Prefix Sum problem that introduces the concept of cumulative sums, which is foundational in many algorithms, such as:

• Range sum queries

• Sliding window techniques

• Subarray sum problems

A solid understanding of this pattern is crucial for optimizing problems involving range queries or aggregation over sequences.