Given Matrix, write a Python program to sort rows by maximum of K sized subarray sum.
Examples:
Input : test_list = [[4, 3, 5, 2, 3], [6, 4, 2, 1, 1], [4, 3, 9, 3, 9], [5, 4, 3, 2, 1]], K = 3
Output : [[4, 3, 5, 2, 3], [6, 4, 2, 1, 1], [5, 4, 3, 2, 1], [4, 3, 9, 3, 9]]
Explanation : 12 = 12 = 12 < 21, is order of maximum sum 3 length substring.Input : test_list = [[4, 3, 5, 2, 3], [4, 3, 9, 3, 9], [5, 4, 3, 2, 1]], K = 3
Output : [[4, 3, 5, 2, 3], [5, 4, 3, 2, 1], [4, 3, 9, 3, 9]]
Explanation : 12 = 12 < 21, is order of maximum sum 3 length substring.
Method #1 : Using max() + sum() + slicing + sort()
In this, maximum of K length subarray is computed using max(), sum() and slicing using external function and inplace sorting is done using sort().
Python3
# Python3 code to demonstrate working of# Sort Matrix by K Sized Subarray Maximum Sum# Using max() + sum() + slicing + sort()def max_ksub(row): # getting maximum K length sum return max(sum(row[idx: idx + K]) for idx in range(len(row) - K))# initializing listtest_list = [[4, 3, 5, 2, 3], [6, 4, 2, 1, 1], [4, 3, 9, 3, 9], [5, 4, 3, 2, 1]]# printing original listprint("The original list is : " + str(test_list))# initializing KK = 3# performing inplace sortingtest_list.sort(key=max_ksub)# printing resultprint("The sorted result : " + str(test_list)) |
Output:
The original list is : [[4, 3, 5, 2, 3], [6, 4, 2, 1, 1], [4, 3, 9, 3, 9], [5, 4, 3, 2, 1]] The sorted result : [[4, 3, 5, 2, 3], [6, 4, 2, 1, 1], [5, 4, 3, 2, 1], [4, 3, 9, 3, 9]]
Time Complexity: O(nlogn+mlogm)
Auxiliary Space: O(1)
Method #2 : Using sorted() + lambda + max() + sum() + slicing
In this, we perform task of sorting using sorted() + lambda function which injects comparator logic and avoids calling external function.
Python3
# Python3 code to demonstrate working of# Sort Matrix by K Sized Subarray Maximum Sum# Using sorted() + lambda + max() + sum() + slicing# initializing listtest_list = [[4, 3, 5, 2, 3], [6, 4, 2, 1, 1], [4, 3, 9, 3, 9], [5, 4, 3, 2, 1]]# printing original listprint("The original list is : " + str(test_list))# initializing KK = 3# sorted() performs inplace sort# lambda function injects comparison logicres = sorted(test_list, key=lambda row: max( sum(row[idx: idx + K]) for idx in range(len(row) - K)))# printing resultprint("The sorted result : " + str(res)) |
Output:
The original list is : [[4, 3, 5, 2, 3], [6, 4, 2, 1, 1], [4, 3, 9, 3, 9], [5, 4, 3, 2, 1]] The sorted result : [[4, 3, 5, 2, 3], [6, 4, 2, 1, 1], [5, 4, 3, 2, 1], [4, 3, 9, 3, 9]]
Time Complexity: O(nlogn+mlogm)
Auxiliary Space: O(n)
Method 3: Using heapq.nlargest() + sum() + enumerate()
Python3
# Python3 code to demonstrate working of# Sort Matrix by K Sized Subarray Maximum Sum# Using heapq.nlargest() + sum() + enumerate()# importing required moduleimport heapq# initializing listtest_list = [[4, 3, 5, 2, 3], [6, 4, 2, 1, 1], [4, 3, 9, 3, 9], [5, 4, 3, 2, 1]]# printing original listprint("The original list is : " + str(test_list))# initializing KK = 3# heapq.nlargest() returns the n largest elements from the iterable# lambda function calculates the sum of K-sized subarrays of a row# enumerate() adds index to the result of heapq.nlargest()# sorted() sorts the rows based on their K-sized subarray maximum sumres = sorted(test_list, key=lambda row: heapq.nlargest(1, ((sum(row[i:i+K]), i) for i in range(len(row) - K + 1)), key=lambda x: x[0])[0][1])# printing resultprint("The sorted result : " + str(res)) |
The original list is : [[4, 3, 5, 2, 3], [6, 4, 2, 1, 1], [4, 3, 9, 3, 9], [5, 4, 3, 2, 1]] The sorted result : [[4, 3, 5, 2, 3], [6, 4, 2, 1, 1], [5, 4, 3, 2, 1], [4, 3, 9, 3, 9]]
Time complexity: O(n * k * log(n)), where n is the number of rows and k is the subarray size.
Auxiliary space: O(n * k).
