Last Updated: 2 Dec, 2020
K-th Largest Sum Subarray
Easy
Asked in companies
Given an array of integers, find the Kth largest sum subarray For example, given the array [1, -2, 3, -4, 5] and K = 2, the 2nd largest sum subarray would be [3, -4, 5], which has a sum of 4.
Please note that a subarray is the sequence of consecutive elements of the array.
Input Format :
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first input line of each test case contains two space-separated integers ‘N’ and ‘K’.
The second input line of each test case contains ‘N’ space-separated integers denoting the elements of the given array.
Output Format :
For each test case, print the K-th largest sum subarray.
The output of each test case will be printed in a separate line.
Note: You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 50
1 <= N <= 100
1 <= K <= (N * (N + 1)) / 2
-1000 <= ARR[i] <= 1000
Where ‘T’ is the number of test cases, ‘N’ is the length of the given array/list, ‘K’ is the given integer and ARR[i] denotes the i-th element of the given array/list.
Time limit: 1 sec
Approaches
The key idea of this approach is to find the subarray sum of every possible subarray and store it in an array/list. We can easily get the k-th largest element after sorting the array/list in non-increasing order.
Consider the following steps:
- Create an array/list “bin” that stores the subarray sum of every possible subarray.
- Start iterating the given array/list using a variable ‘i’ such that 0 <= ‘i’ <= ‘N’ - 1. Here ‘i’ denotes the smallest index of the subarray which we are considering.
- Create a variable “sum” which stores the subarray sum. Initialize it to zero.
- Create a nested loop using a variable ‘j’ such that ‘j’ <= ‘i’ <= ‘N’ - 1. Here ‘j’ denotes the largest index of the subarray which we are considering.
- Add the sum of the current element i.e. “sum” = “sum” + ARR[j]
- Now, append the “sum” which denotes the subarray sum of ARR[i : j] in the “bin”.
- Sort the “bin” in non-increasing order and return the element at the (K - 1)-th index.
The key idea of this approach is to use a min-heap to store the sum of subarrays.
Consider the following steps:
- Create a min-heap that stores the subarray sum.
- Start iterating the given array/list using a variable ‘i’ such that 0 <= ‘i’ <= ‘N’ - 1. Here ‘i’ denotes the smallest index of the subarray which we are considering.
- Create a variable “sum” which stores the subarray sum. Initialize it to zero.
- Create a nested loop using a variable ‘j’ such that ‘j’ <= ‘i’ <= ‘N’ - 1. Here ‘j’ denotes the largest index of the subarray which we are considering.
- Add the sum of the current element i.e. “sum” = “sum” + ARR[j]
- If the size of the min-heap is less than ‘K’, push the “sum” in the min-heap.
- Otherwise, if the current element is greater than the top-most element (i.e. smallest element) then pop the top-most element and push the “sum” in the min-heap.
- The top-most element of the min-heap denotes the K-th largest subarray sum. Return it.