K-th Largest Sum Subarray

Easy
0/40
Average time to solve is 10m
profile
Contributed by
118 upvotes
Asked in companies
OlaAmazonSolomon Capital

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
3 3
3 -2 5
2 2
4 1

Sample output 1 :

3
4

Explanation of Sample output 1 :

For the first test case, 
Sum of [0, 0] = 3
Sum of [0, 1] = 1
Sum of [0, 2] = 6
Sum of [1, 1] = -2
Sum of [1, 2] = 3
Sum of [2, 2] = 5
All sum of subarrays are {6, 5, 3, 3, 1, -2} where the third largest element is 3.

For the second test case, 
Sum of [0, 0] = 4
Sum of [0, 1] = 5
Sum of [1, 1] = 1
All sum of subarrays are {5, 4, 1} where the second largest element is 4.

Sample Input 2 :

2
4 10
5 4 -8 6
3 1
1 2 3

Sample output 2 :

-8
6

Explanation of Sample output 2 :

For the first test case, among the sum of all the subarray, the tenth-largest sum will be -8.

For the second test case, among the sum of all the subarray, the largest sum will be 6.
Hint

Can you think of considering all subarrays?

Approaches (2)
Brute Force

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:

  1. Create an array/list “bin” that stores the subarray sum of every possible subarray.
  2. 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”.
  3. Sort the “bin” in non-increasing order and return the element at the (K - 1)-th index.
Time Complexity

O(N ^ 2 * log(N), where ‘N’ is the length of the given array/list.

 

We are iterating through each subarray of the given array/list using a nested loop which takes O(N ^ 2). And then sorting the “bin” array/list which contains (N * (N + 1)) / 2 elements. Sorting takes O((N ^ 2) * log(N ^ 2)) = O((N ^ 2) * log(N)). So the overall time complexity will be O((N ^ 2) * log(N)).

Space Complexity

O(N ^ 2), where ‘N’ is the length of the given array/list.

 

Since we are using an array/list to store the sum of every subarray of the given array/list. And there will be (N * ( N + 1) ) / 2 such elements. So the overall space complexity will be O(N ^ 2).

Code Solution
(100% EXP penalty)
K-th Largest Sum Subarray
Full screen
Console