Python – Suffix List Sum
Nowadays, especially in the field of competitive programming, the utility of computing suffix 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 the 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 the 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 # Suffix List Sum # 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 # Suffix List Sum test_list.reverse() res = [ sum (test_list[: i + 1 ]) for i in range ( len (test_list))] # print result print ( "The suffix sum list is : " + str (res)) |
The original list : [3, 4, 1, 7, 9, 1] The suffix sum list is : [1, 10, 17, 18, 22, 25]
Time complexity: O(n^2), where n is the length of the input list.
Auxiliary space: O(n) The program uses a list of length n to store the suffix sums.
Method#2: Using a for loop
Python3
def suffix_sum(lst): result = [] sum = 0 for i in range ( len (lst) - 1 , - 1 , - 1 ): sum + = lst[i] result.append( sum ) return result # input sample list test_list = [ 3 , 4 , 1 , 7 , 9 , 1 ] print ( "The original list :" , test_list) res = suffix_sum(test_list) # printing list print ( "The suffix sum list is :" , res) |
The original list : [3, 4, 1, 7, 9, 1] The suffix sum list is : [1, 10, 17, 18, 22, 25]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method#3: Using the Recursive method
Python3
def suffix_sum_recursive(lst, sum = 0 , result = None ): if result is None : result = [] if len (lst) = = 0 : return result sum + = lst[ - 1 ] result.append( sum ) return suffix_sum_recursive(lst[: - 1 ], sum , result) # input sample list test_list = [ 3 , 4 , 1 , 7 , 9 , 1 ] print ( "The original list :" , test_list) res = suffix_sum_recursive(test_list) # printing the list print ( "The suffix sum list is :" , res) |
The original list : [3, 4, 1, 7, 9, 1] The suffix sum list is : [1, 10, 17, 18, 22, 25]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method#4: Using itertools.accumulate() function:
Algorithm:
- Reverse the original list.
- Compute the cumulative sum of the reversed list using itertools.accumulate() function.
- Reverse the cumulative sum list to get the final suffix sum list.
Python3
from itertools import accumulate test_list = [ 3 , 4 , 1 , 7 , 9 , 1 ] # printing original list print ( "The original list : " + str (test_list)) suffix_sum = list (accumulate( reversed (test_list))) # printing the list print ( "The suffix sum list is:" , suffix_sum) |
The original list : [3, 4, 1, 7, 9, 1] The suffix sum list is: [1, 10, 17, 18, 22, 25]
Time Complexity:
The time complexity of this algorithm is O(n), where n is the length of the input list. The itertools.accumulate() function takes O(n) time to compute the cumulative sum, and the reverse operation takes O(n) time as well.
Auxiliary Space:
The space complexity of this algorithm is also O(n), where n is the length of the input list. The itertools.accumulate() function creates a generator object that stores the intermediate values of the cumulative sum, which takes O(n) space. The final suffix sum list also takes O(n) space.
Method 5: using a generator expression and the reversed() function:
Steps:
- Define a function suffix_sum_generator() that takes a list lst as input.
- Initialize an empty list suffix_sum to store the suffix sums.
- Create a generator expression using a for loop and the sum() function to calculate the suffix sum for each suffix of the list. The generator expression yields the suffix sums in reverse order.
- Convert the generator expression to a list and reverse it using the reversed() function to get the suffix sums in the correct order.
- Append each suffix sum to the suffix_sum list.
- Return the suffix_sum list.
Python3
def suffix_sum_generator(lst): suffix_sum = [] suffix_sum_gen = ( sum (lst[i:]) for i in range ( len (lst))) for num in reversed ( list (suffix_sum_gen)): suffix_sum.append(num) return suffix_sum # Sample input test_list = [ 3 , 4 , 1 , 7 , 9 , 1 ] print ( "The original list :" , test_list) # Call suffix_sum_generator() function res = suffix_sum_generator(test_list) # printing list print ( "The suffix sum list is :" , res) |
The original list : [3, 4, 1, 7, 9, 1] The suffix sum list is : [1, 10, 17, 18, 22, 25]
Time complexity: O(n^2)
Auxiliary space: O(n)
Method 6: Using numpy.cumsum() function
Step-by-step algorithm:
- Initialize an empty list suffix_sum.
- Initialize a variable total to 0.
- Loop through the input list test_list in reverse order using the reversed() function:
- Add the current element to total.
- Append total to the suffix_sum list.
- Reverse the suffix_sum list using the reverse() method.
- Return the suffix_sum list.
Python3
# import numpy library import numpy as np # initialize list test_list = [ 3 , 4 , 1 , 7 , 9 , 1 ] # reverse the list using slicing and compute the cumulative sum using numpy.cumsum() # then reverse the result again to obtain the correct order of suffix sum values suffix_sum = np.cumsum(test_list[:: - 1 ])[:: - 1 ].tolist() # create a list of indices in descending order index_list = list ( range ( len (test_list) - 1 , - 1 , - 1 )) # use the index list to access the suffix sum values in the correct order suffix_sum_ordered = [suffix_sum[i] for i in index_list] # print the ordered suffix sum list and the index list print ( "Index list:" , index_list) print ( "Ordered suffix sum list:" , suffix_sum_ordered) |
output
Index list: [5, 4, 3, 2, 1, 0] Ordered suffix sum list: [1, 10, 17, 18, 22, 25]
Time complexity:
The time complexity of this approach is O(n), where n is the length of the input list test_list. This is because we loop through the list once, and perform constant time operations inside the loop.
Auxiliary space complexity:
The auxiliary space complexity of this approach is O(n), where n is the length of the input list test_list. This is because we create a new list suffix_sum to store the suffix sum values, which requires n elements of space. Additionally, we use a constant amount of space for the total and loop variables.
Contact Us