Leetcode – Running Sum of 1d Array Solution

Spread the love

The “Running Sum of 1D Array” problem is a straightforward problem on Leetcode but serves as a foundation for understanding the cumulative sum technique in array manipulation. In this article, we will dissect the problem, look at different approaches to solve it, understand the time and space complexities, and finally, evaluate its practical applications.

Problem Statement

Firstly, let’s go over the problem statement.

Given an array nums, we have to return a new array called running_sum, where running_sum[i] is the sum of the first i + 1 elements of nums.

Example

Input: nums = [1, 2, 3, 4]
Output: [1, 3, 6, 10]
Explanation: running_sum[0] = nums[0] = 1, running_sum[1] = nums[0] + nums[1] = 1 + 2 = 3, etc.

Brute-force Approach

The most naive way to solve this problem is to use nested loops to calculate the running sum for each index.

def runningSum(nums):
    n = len(nums)
    running_sum = []
    for i in range(n):
        sum = 0
        for j in range(i + 1):
            sum += nums[j]
        running_sum.append(sum)
    return running_sum

# Test the function
print(runningSum([1, 2, 3, 4]))  # Output should be [1, 3, 6, 10]

Time Complexity

The time complexity of the brute-force approach is O(n^2).

Space Complexity

The space complexity is O(n) because we create a new list to store the running sum.

Optimized Approach

We can optimize the brute-force approach by observing that running_sum[i] = running_sum[i-1] + nums[i]. This relation allows us to calculate the running sum in a single pass through the array.

def runningSum(nums):
    n = len(nums)
    running_sum = [nums[0]]
    for i in range(1, n):
        running_sum.append(running_sum[-1] + nums[i])
    return running_sum

# Test the function
print(runningSum([1, 2, 3, 4]))  # Output should be [1, 3, 6, 10]

Time Complexity

The time complexity of the optimized approach is O(n).

Space Complexity

The space complexity remains O(n).

In-Place Approach

We can also solve this problem in-place by updating the original array. This will reduce the space complexity to O(1).

def runningSum(nums):
    for i in range(1, len(nums)):
        nums[i] += nums[i - 1]
    return nums

# Test the function
print(runningSum([1, 2, 3, 4]))  # Output should be [1, 3, 6, 10]

Time Complexity

The time complexity is O(n).

Space Complexity

The space complexity is O(1) as we are not using any extra space other than the input array.

Use Cases and Applications

Understanding how to efficiently compute a running sum is crucial in many areas of computer science:

  1. Data Analysis: Running sums are used to analyze trends over a period.
  2. Dynamic Programming: This technique is commonly used in dynamic programming problems to keep track of sums over a range of array elements.
  3. Financial Computations: Used to calculate accumulated values, e.g., interests or investments over time.
  4. Sliding Window Problems: The concept can be adapted for solving more complex problems that involve sliding windows.

Conclusion

The “Running Sum of 1D Array” problem is an elementary array manipulation problem that serves as an entry point to understanding more complex algorithms. We explored multiple approaches with their respective time and space complexities. We started with a brute-force approach and then incrementally optimized it.

Leave a Reply