We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Running Sum of 1d Array

Number: 1603

Difficulty: Easy

Paid? No

Companies: Google, tcs, Amazon, Adobe, Apple, Bloomberg, Microsoft

Problem Description

Given an array nums, compute and return the running sum of nums, where each element at index i in the running sum array is the sum of all elements from index 0 to i in the original array.

Key Insights

  • The problem requires computing cumulative sums, also known as prefix sums.
  • Iterating over the array while maintaining a running total yields the answer.
  • In-place modification is possible if allowed, but creating a new array maintains immutability.
  • The constraints are small enough to allow a simple O(n) solution.

Space and Time Complexity

Time Complexity: O(n) because we process each element once. Space Complexity: O(n) if we store the running sum in a new array; O(1) extra space if modified in-place.

Solution

The solution uses a simple iterative approach. Initialize a variable to keep track of the cumulative sum. Then iterate over the input array, updating the cumulative sum with each element and storing it in the resulting array. This approach uses the array itself (or an additional output array) to build the running sum in a single pass through the data. The algorithm leverages the concept of prefix sum which allows for an efficient calculation with minimal additional memory overhead.

Code Solutions

# Function to compute running sum of a 1d array.
def running_sum(nums):
    # Initialize an empty list to store the running sum.
    result = []
    # Initialize the cumulative sum as 0.
    cumulative = 0
    # Iterate over each value in the input list.
    for num in nums:
        # Update the cumulative sum with the current number.
        cumulative += num
        # Append the updated cumulative sum to the result list.
        result.append(cumulative)
    # Return the list containing the running sums.
    return result

# Example usage:
print(running_sum([1, 2, 3, 4]))  # Expected output: [1, 3, 6, 10]
← Back to All Questions