Running Sum of 1d Array (Leetcode 1480)

Difficulty: Easy Link: Day 3: May Leetcode Challenge

Problem Statement

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

Examples

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]

Constraints

  • 1 <= nums.length <= 1000
  • -10^6 <= nums[i] <= 10^6

Solution

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 [0] = nums [0] itself.

Swift

class Solution {
func runningSum(_ nums: [Int]) -> [Int] {
var nums = nums
for i in 1..<nums.count {
nums[i] = nums[i 1] + nums[i]
}
return nums
}
}
view raw running_sum.swift hosted with ❤ by GitHub

Python

class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
for i in range (1, len(nums)):
nums [i] = nums [i] + nums [i1]
return nums
view raw running_sum.py hosted with ❤ by GitHub

Java

class Solution {
public int[] runningSum(int[] nums) {
for (int i = 1; i < nums.length; i++)
nums [i] += nums [i1];
return nums;
}
}
view raw running_sum.java hosted with ❤ by GitHub

Complexity Analysis

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)

Leave a Reply

Your email address will not be published. Required fields are marked *