Nowadays, especially in the field of competitive programming, the utility of computing prefix sum is quite popular and features in many problems. Hence, having a one-liner solution to it would possess a great help. Let’s discuss certain way in which this problem can be solved.
Method #1: Using list comprehension + sum() + list slicing This problem can be solved using the combination of above two functions in which we use list comprehension to extend logic to each element, sum function to get the sum along, slicing is used to get sum till the particular index.
Python3
# Python3 code to demonstrate# prefix sum list# using list comprehension + sum() + list slicing # initializing listtest_list = [3, 4, 1, 7, 9, 1]# printing original listprint("The original list : " + str(test_list))# using list comprehension + sum() + list slicing# prefix sum listres = [sum(test_list[ : i + 1]) for i in range(len(test_list))]# print resultprint("The prefix sum list is : " + str(res)) |
The original list : [3, 4, 1, 7, 9, 1] The prefix sum list is : [3, 7, 8, 15, 24, 25]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #2: Using accumulate(iterable) method.
Python3
# function to find cumulative sum of listfrom itertools import accumulate def cumulativeSum(lst): print (list(accumulate(lst))) # Driver program if __name__ == "__main__": lst = [3, 4, 1, 7, 9, 1] cumulativeSum(lst) |
[3, 7, 8, 15, 24, 25]
Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(n), as we create a new list of the same length as the input list to store the cumulative sum.
Method#3: Using For loop and list indexing The above problem can be solve using two mention techniques. For loop is used for iterating in list and list indexing is used to access current element and previous element.
Python3
# Python3 code to demonstrate# prefix sum list# using For loop + list indexing# initializing listtest_list = [3, 4, 1, 7, 9, 1]# printing original listprint("The original list : " + str(test_list))# using For loop and list indexing# prefix sum listres = [0]*len(test_list)res[0] = test_list[0]for i in range(1, len(test_list)): res[i] = res[i-1] + test_list[i]# print resultprint("The prefix sum list is : " + str(res)) |
The original list : [3, 4, 1, 7, 9, 1] The prefix sum list is : [3, 7, 8, 15, 24, 25]
Time complexity: O(n).where n is the length of the input list.
Auxiliary space: O(n). As an additional list of the same length as the input list is created to store the prefix sum values.
Method#4: Using the reduce function from the functools module:
The reduce function applies the given function to the elements of lst in a cumulative manner, starting with an initial accumulator value of 0. The function passed to reduce takes two arguments, a and b, and returns a new list a + [a[-1] + b]. The first element of the list is the accumulator value, and the second element is the sum of the accumulator value and the current element in lst.
Python3
from functools import reducedef prefix_sum(lst): # Use the reduce function to apply a function to the elements of lst in a cumulative manner, starting with an initial accumulator value of 0 res = list(reduce(lambda a, b: a + [a[-1] + b], lst, [0])) # Print the original and final lists print("Original list:", lst) print("Prefix sum list:", res[1:])# Test the functionlst = [3, 4, 1, 7, 9, 1]prefix_sum(lst)#This code is contributed by Edula Vinay Kumar Reddy |
Original list: [3, 4, 1, 7, 9, 1] Prefix sum list: [3, 7, 8, 15, 24, 25]
Time complexity: O(n), since the reduce function iterates over the elements in lst.
Auxiliary space: O(n), since the function returns a list with the same number of elements as lst.
Method #5 : Using NumPy
The cumsum function from NumPy returns the cumulative sum of elements along a given axis. In this case, we pass in the test_list and get back the prefix sum list.
Python3
import numpy as np# initializing listtest_list = [3, 4, 1, 7, 9, 1]# printing original listprint("The original list : " + str(test_list))# using NumPy to generate prefix sum listres = np.cumsum(test_list)# print resultprint("The prefix sum list is : " + str(res)) |
OUTPUT:
The original list : [3, 4, 1, 7, 9, 1] The prefix sum list is : [ 3 7 8 15 24 25]
Time complexity: O(n), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list.
