1480. Running Sum of 1d Array
Problem Description
In this problem, you're given an array nums
which contains a list of integers. The task is to calculate a running sum of this array. The running sum is a new array where each element at index i
is the sum of all the numbers in the nums
array up to and including the number at index i
.
More formally, the running sum of nums
is an array where the value at the i-th
index is equal to sum(nums[0]ā¦nums[i])
. So for runningSum[i]
, we add up all the elements from the start of the array to the current element at i
.
Your goal is to return the running sum of the given array nums
.
Intuition
To solve this problem, we can use a common algorithm called Prefix Sum. The idea behind Prefix Sum is simple ā as we move through the array element by element, we keep updating the current element to be the sum of itself and all previous elements.
So how do we arrive at this solution? Let's think about the process step by step. If we were doing this by hand, we'd start at the first element ā nothing to add here since it's the start. We note this number down. Then, we'd move to the next number, add it to the first, and note this new sum down. Then, for the third number, we'd add it to the new sum we just computed, and so on.
This is exactly what the Prefix Sum algorithm does. We start with the first element, then for each subsequent element at index i
, we add the current element nums[i]
to the sum we have obtained so far, which is the previous element nums[i-1]
. This updated sum becomes the new value for nums[i]
.
By following this approach, we only need to traverse the array once, making our algorithm efficient and straightforward.
Learn more about Prefix Sum patterns.
Solution Approach
The solution provided uses a built-in Python function accumulate
from the itertools
module, which essentially applies the Prefix Sum algorithm automatically for us.
Here's the step by step approach using the Prefix Sum concept:
- Initialize a variable, let's call it
prefixSum
, to store the sum of elements we've encountered so far. InitiallyprefixSum
is set to 0. - Traverse the array
nums
from the first to the last element. - For each element at index
i
, updateprefixSum
by adding the current elementnums[i]
to it. This will hold the sum of all elements up to the current index. - Assign the value of
prefixSum
back tonums[i]
to reflect the running sum till the current element. - Repeat steps 3-4 for the entire length of the array.
- Once the loop ends, we'd have transformed the original
nums
array into the running sum array.
Now, in the provided solution, the step-by-step process is neatly wrapped up by Python's accumulate()
function. This function takes an iterable (in our case, the array nums
) and returns an iterator that yields accumulated sums (or other binary functions if specified).
The solution could also be implemented more explicitly, without the use of accumulate()
, which would look something like this:
class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
for i in range(1, len(nums)):
nums[i] += nums[i-1]
return nums
In the above explicit implementation:
- We use a
for
loop to traverse the array starting from the second element (since the first element's running sum is the element itself). - We then continuously update each element with the sum of itself and all previous elements. This is done by adding the current element
nums[i]
with the previous elementnums[i-1]
and storing the result back innums[i]
. - After traversing through the array, we return the
nums
array which now contains the running sum.
Both approaches accomplish the task using the powerful concept of Prefix Sum, but one is more succinct by leveraging Python's built-in functionality.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to make the solution approach clear. Suppose the nums
array is [3, 1, 2, 10]
.
Here are the steps we would take to get the running sum:
- Start with the first element. Since there are no elements before it, the running sum is just the element itself. So
runningSum[0]
would be3
. - Move to the second element,
1
. We add this to the previous running sum (3
), giving us4
. SorunningSum[1]
is3 + 1
which equals4
. - Next, the third element is
2
. Adding this to the running sum we have so far (4
), we get6
. Now,runningSum[2]
is4 + 2
which equals6
. - Finally, take the fourth element,
10
. We add this to the last running sum (6
), which gives us16
. Therefore,runningSum[3]
is6 + 10
which equals16
.
The final output, our running sum array, is [3, 4, 6, 16]
.
Implementing this in Python code without the use of accumulate()
from the itertools
module would look like this:
class Solution:
def runningSum(self, nums):
for i in range(1, len(nums)):
nums[i] += nums[i-1]
return nums
If we use this code with our example nums
array [3, 1, 2, 10]
, here's what happens step by step in the loop:
i = 1
:nums[1]
(which is1
) is updated tonums[1] + nums[0]
(which is1 + 3
), sonums[1]
becomes4
.i = 2
:nums[2]
(which is2
) is updated tonums[2] + nums[1]
(which is2 + 4
), sonums[2]
becomes6
.i = 3
:nums[3]
(which is10
) is updated tonums[3] + nums[2]
(which is10 + 6
), sonums[3]
becomes16
.
And we get the final updated nums
array [3, 4, 6, 16]
, which is the same result we calculated manually.
Solution Implementation
1from itertools import accumulate # Import accumulate function from itertools module
2
3class Solution:
4 def runningSum(self, nums: List[int]) -> List[int]:
5 # Calculate the running sum of the list of numbers using accumulate
6 running_sum = list(accumulate(nums))
7 # Return the running sum as a list
8 return running_sum
9
1class Solution {
2
3 // Method to calculate the running sum of the given array
4 public int[] runningSum(int[] nums) {
5 // Loop through the array starting from the second element
6 for (int index = 1; index < nums.length; index++) {
7 // Update the current element by adding the previous element's sum to it
8 nums[index] += nums[index - 1];
9 }
10 // Return the modified array containing the running sum
11 return nums;
12 }
13}
14
1#include <vector> // Include vector library for using the vector class
2
3class Solution {
4public:
5 // Function to calculate the running sum of a 1D vector
6 vector<int> runningSum(vector<int>& nums) {
7 // Iterate over the vector starting from the second element
8 for (size_t i = 1; i < nums.size(); ++i) {
9 // Add the previous element's value to the current element
10 nums[i] += nums[i - 1];
11 }
12 // Return the modified vector with the running sum
13 return nums;
14 }
15};
16
1/**
2 * Computes the running sum of an array of numbers.
3 * For every index in the array, it modifies the value at that index
4 * to be the sum of all elements up to and including that index.
5 *
6 * @param {number[]} numbers - The array of numbers to calculate the running sum for.
7 * @returns {number[]} - The array of numbers with the running sum computed.
8 */
9function runningSum(numbers: number[]): number[] {
10 // Start iterating from the first index because the running sum at index 0 is just the element itself
11 for (let index = 1; index < numbers.length; ++index) {
12 // Update the element at the current index to be the sum of the element at the current index
13 // and the element at the previous index which now contains the running sum up to the previous index
14 numbers[index] += numbers[index - 1];
15 }
16 // Return the modified array with the running sums
17 return numbers;
18}
19
Time and Space Complexity
The time complexity of the code is O(n)
, where n
is the length of the input array. This is because accumulate
function goes through each element of the array only once to calculate the running sum.
The space complexity in the given code should be O(n)
, not O(1)
as the reference answer suggests. This difference arises because although accumulate
itself may operate with O(1)
additional space, calling list(accumulate(nums))
stores the results of accumulate(nums)
in a new list, which takes up O(n)
space based on the number of elements in nums
.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!