1480. Running Sum of 1D Array - Leetcode Solution

Leetcode Problem Link Code Solution Link:

💡 Step-by-Step Thought Process

Understand the problem: Compute the running sum of an array, where each element at index i is the sum of all elements from index 0 to i.
Initialize a variable s to 0 to track the cumulative sum.
Get the length n of the input array nums.
Create an array prefix_sum of size n initialized with zeros to store the running sums.
Iterate through each index i from 0 to n-1.
Add nums[i] to s to update the cumulative sum.
Store s in prefix_sum[i] as the running sum up to index i.
Return prefix_sum as the result.

Code Solution

class Solution:
    def runningSum(self, nums):
        s = 0
        n = len(nums)
        prefix_sum = [0] * n
        
        for i in range(n):
            s += nums[i]
            prefix_sum[i] = s
        
        return prefix_sum
        # Time: O(n)
        # Space: O(n)

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        int s = 0;
        int n = nums.size();
        vector<int> prefix_sum(n);
        
        for (int i = 0; i < n; i++) {
            s += nums[i];
            prefix_sum[i] = s;
        }
        
        return prefix_sum;
    }
    // Time: O(n)
    // Space: O(n)
};

class Solution {
    public int[] runningSum(int[] nums) {
        int s = 0;
        int n = nums.length;
        int[] prefix_sum = new int[n];
        
        for (int i = 0; i < n; i++) {
            s += nums[i];
            prefix_sum[i] = s;
        }
        
        return prefix_sum;
    }
    // Time: O(n)
    // Space: O(n)
}

var runningSum = function(nums) {
    var s = 0;
    var n = nums.length;
    var prefix_sum = new Array(n).fill(0);
    
    for (var i = 0; i < n; i++) {
        s += nums[i];
        prefix_sum[i] = s;
    }
    
    return prefix_sum;
    // Time: O(n)
    // Space: O(n)
};

Detailed Explanation

What Is the Running Sum of a 1D Array?

The running sum of a 1D array is a fundamental problem in array manipulation and prefix sum techniques. It involves creating a new array where each element at index i contains the sum of all elements from index 0 to i in the original array. This technique is widely used in many algorithmic problems, such as subarray sum queries, cumulative frequency analysis, and more.

Problem Statement Explained

Given an input array nums, return a new array runningSum such that runningSum[i] = nums[0] + nums[1] + ... + nums[i]. This is equivalent to computing the prefix sum at each index in a single pass through the array.

Optimal Solution Strategy

The optimal approach for solving this problem is simple and highly efficient. You initialize a variable to track the cumulative sum as you iterate through the array. At each step, you add the current number to the cumulative sum and store the result in the corresponding index of the output array.

This one-pass strategy ensures optimal performance with minimal memory overhead. If modifying the input array is allowed, you can even compute the result in-place.

Step-by-Step Example

Let's say nums = [1, 2, 3, 4]. The running sum array would be:

runningSum[0] = 1
runningSum[1] = 1 + 2 = 3
runningSum[2] = 1 + 2 + 3 = 6
runningSum[3] = 1 + 2 + 3 + 4 = 10

Final result: [1, 3, 6, 10]

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array. The array is traversed once.
Space Complexity: O(n) for the output array. If computed in-place, space can be reduced to O(1).

Why This Problem Matters

The running sum is a core building block for more advanced algorithms like range sum queries, sliding window techniques, and dynamic programming. Mastering this pattern will help in optimizing solutions where repeated summation of ranges would otherwise lead to inefficient nested loops.

Conclusion

Solving the "Running Sum of 1D Array" problem efficiently demonstrates your understanding of array traversal and prefix sum optimization. This simple yet powerful concept is frequently tested in coding interviews and competitive programming.

Get Personalized Support at AlgoMap Bootcamp 💡

AlgoMap.io

Want Help Cracking FAANG?