Wednesday, December 25, 2024
Google search engine
HomeLanguagesPython | Prefix sum list

Python | Prefix sum list

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 list
test_list = [3, 4, 1, 7, 9, 1]
 
# printing original list
print("The original list : " + str(test_list))
 
# using list comprehension + sum() + list slicing
# prefix sum list
res = [sum(test_list[ : i + 1]) for i in range(len(test_list))]
 
# print result
print("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)
Auxiliary Space: O(n)

Method #2: Using accumulate(iterable) method.

Python3




# function to find cumulative sum of list
from itertools import accumulate
 
def cumulativeSum(lst):
    print (list(accumulate(lst)))
 
# Driver program
if __name__ == "__main__":
    lst = [3, 4, 1, 7, 9, 1]
    cumulativeSum(lst)


Output

[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 list
test_list = [3, 4, 1, 7, 9, 1]
 
# printing original list
print("The original list : " + str(test_list))
 
# using For loop and list indexing
# prefix sum list
res = [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 result
print("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). 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 reduce
 
def 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 function
lst = [3, 4, 1, 7, 9, 1]
prefix_sum(lst)
#This code is contributed by Edula Vinay Kumar Reddy


Output

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 list
test_list = [3, 4, 1, 7, 9, 1]
 
# printing original list
print("The original list : " + str(test_list))
 
# using NumPy to generate prefix sum list
res = np.cumsum(test_list)
 
# print result
print("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.

RELATED ARTICLES

Most Popular

Recent Comments