Difficulty: Easy Link: Day 3: May Leetcode Challenge
Given an array
nums. We define a running sum of an array as
runningSum[i] = sum(nums…nums[i]).
Return the running sum of
Input: nums = [1,2,3,4] Output: [1,3,6,10] Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].
Input: nums = [1,1,1,1,1] Output: [1,2,3,4,5] Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].
Input: nums = [3,1,2,10,1] Output: [3,4,6,16,17]
1 <= nums.length <= 1000
-10^6 <= nums[i] <= 10^6
This is the easiest problem you would ever get on Leetcode (Except Fibonacci numbers ofcourse). For people new to programming, this method of finding cumulative sum of terms in a sequence is called PrefixSum. This is an important paradigm in competitive programming and you should read more about it if you haven’t came across it before. You can follow the link on CMU Page and GeeksForGeeks article to know more about its applications.
We can solve the problem by simply taking a variable for storing the cumulative sum we found. We can use the input array to update the sum before the ith Index. Iterate from the second element of the array and update the current number with the current number + element at previous index, ie,
prefixSum [i] = prefixSum [i-1] + nums [i]. Since there is no number before the first number,
prefixSum  = nums  itself.
We are simply iterating over the input array so N operations are done. We are using the input array to compute so no extra space.
Time = O(N)
Space = O(1)