1480. Running Sum of 1d Array
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 88.6%
Problem Breakdown
The problem requires us to compute the running sum of a given 1-dimensional array nums. The running sum at index i is defined as the sum of all elements from the start of the array up to index i, inclusive.
Inputs:
- An array of integers
nums.
Outputs:
- A new array where each element at index
iis the sum of all elements innumsfrom index 0 toi.
Implicit Constraints or Edge Cases:
- The input array can be empty, though this is not explicitly stated.
- The array can contain negative numbers.
- The length of the array is between 1 and 1000.
Intuition
A brute-force approach would involve iterating over each element in the array and summing all elements up to that point. This would result in a time complexity of O(n^2) because for each element, we are potentially summing all previous elements.
The key insight is that we can optimize this by maintaining a cumulative sum as we iterate through the array. This way, each new running sum can be computed in constant time by adding the current element to the last running sum. This reduces the time complexity to O(n).
Approach
- Initialize an empty list
running_sumto store the results. - Use a variable
current_suminitialized to 0 to keep track of the cumulative sum as we iterate through the array. - For each element in
nums, add it tocurrent_sum. - Append
current_sumto therunning_sumlist. - Return the
running_sumlist.
This approach leverages a single pass through the array, maintaining a running total and updating the result list in place.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the input array
nums. We iterate through the array once. - Space Complexity: O(n), as we store the running sum for each element in a new list.
Solution
def runningSum(nums):
running_sum = []
current_sum = 0
for num in nums:
current_sum += num
running_sum.append(current_sum)
return running_sum
Edge Cases Handled
- Empty Array: If the input array is empty, the function will return an empty list as expected.
- Negative Numbers: The solution correctly handles negative numbers by maintaining the cumulative sum accurately.
- Single Element Array: For a single-element array, the running sum is simply the element itself.