Table of contents

Introduction

1.1.

Problem Statement

1.2.

Some Examples

Brute-Force Approach

2.1.

Implementation in C++

2.1.1.

Complexity Analysis

Optimal Approach

3.1.

Algorithm

3.2.

Implementation in C++

3.2.1.

Complexity Analysis

Frequently Asked Questions

4.1.

When can we expect an ArrayStoreException?

4.2.

What is the limitation of an array?

4.3.

Can the size of the array change at runtime?

Conclusion

Last Updated: Mar 27, 2024

Medium

K-th Largest Sum Contiguous Subarray

Author Prerna Tiwari

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

In this blog, we will be finding the K-th largest sum Contiguous Subarray. So, let's get started by introducing the array and the subarray.

An array is a data structure that can hold a fixed-size sequential collection of the same type of elements. An array is often regarded as a collection of the same type of variables.

The array comes under one of the essential topics for programming interviews, so an individual must have a thorough understanding of this topic.

A sub-array is an array with a length less than or equal to the size of the given array, whose elements are all present in the given array.A subarray is a contiguous section of an array

Let us understand the problem statement of K-th Largest Sum Contiguous Subarray

Problem Statement

Ninja has an array of size N. He gave that array to you. He wants to find the K-th largest sum of contiguous subarray within the array of numbers which can have both negative and positive numbers. But, the problem is that he cannot do it by himself. Can you help him in finding K-th largest sum contiguous subarray?

Some Examples

Input:

arr[]= {10, 5, -12}, k = 2

Output:

Explanation:

All sums of contiguous subarrays are (10, 5, 15, -12, 3,-7), so the 2nd largest sum is 10.

Input:

arr[] = {-1, -6, -8}, k = 3

Output:

-7

Explanation:

All sum of contiguous subarrays are (-1, -7, -6, -8, -14,-15), so the 2nd largest sum is -6.

Brute-Force Approach

We can solve this problem of K-th Largest Sum Contiguous Subarray with a brute force approach by storing sums of all the subarrays in another array, and after that sorting them, and printing the kth largest.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
vector<int> SumOfAllSubarrays(vector<int> &arr, int n)
{
    vector<int> sumArray;
    int current = 0;

    for (int i = 0; i < n; i++)
    {

        current = 0;
        for (int j = i; j < n; j++)
        {

            current += arr[j];
            sumArray.push_back(current);
        }
    }

    return sumArray;
}
int main()
{
    vector<int> arr{3, 5, -1, 9, 8};
    int k = 3;
    vector<int> ContiguousSumArray = SumOfAllSubarrays(arr, arr.size());

    sort(ContiguousSumArray.begin(), ContiguousSumArray.end(), greater<int>());

    cout << ContiguousSumArray[k - 1] << endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Complexity Analysis

Time Complexity

The above approach to solving K-th Largest Sum Contiguous Subarray has a quadratic O((nlog(n))^2) time complexity because we are using nested loops and we are storing all the n^2 sums in the array and after that, we are sorting that array since sorting takes nlog(n) time, therefore, the overall time complexity would be O((nlog(n))^2). Hence, it is not suitable for large input.

Space Complexity

We are using an extra array to store the sum of subarrays. The number of subarrays for an array of size N is given by (N * (N + 1) / 2). Hence, the space complexity is O(n). The memory may run out of space since the number of subarrays can be very large.

Optimal Approach

We can optimize our approach to calculate K-th largest sum contiguous subarray by storing the prefix-sum of the array. We can then find the sum of a contiguous subarray from one index i to another index j by using the formula sum[j]-sum[i-1].

Algorithm

Use a priority queue(min-heap) to store the kth largest sum.
Push the sums in the min-heap till the size of the min-heap is equal to k
When the size of the min-heap becomes equal to k, check if the element is greater than the Kth element.
If the element is greater, pop the top element from the min-heap and insert the element.

Implementation in C++

// CPP program to find the k-th largest sum contiguous subarray
#include <bits/stdc++.h>
using namespace std;

vector<int> prefixSum(int arr[], int n)
{
    vector<int> sum(n + 1, 0);

    for (int i = 2; i <= n; i++)
        sum[i] = sum[i - 1] + arr[i - 1];
    return sum;
}
int main()
{
    int a[] = {6, 7, 7, 41, 5, 3, 1, 3};
    
    int n = sizeof(a) / sizeof(a[0]);
    
    int k = 3;

    // array to store the prefix sum of the array
    vector<int> sum = prefixSum(a, n);

    // priority queue to store the top k sums of subarrays
    priority_queue<int, vector<int>, greater<int>> pq;
    
    // finding out kth largest sum
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j++)
        {
            int x = sum[j] - sum[i - 1];
            if (pq.size() < k)
                pq.push(x);
            else
            {
                if (pq.top() < x)
                {
                    pq.pop();
                    pq.push(x);
                }
            }
        }
    }
    
    cout << pq.top() << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Complexity Analysis

Time Complexity

The above approach has an O(n^2 log (k)) time complexity because the outer loop has the complexity of O(n) and the inner loop has the complexity of O(nlog (k)) because we are inserting only k element in the priority queue, therefore after multiplying complexities of both the loops we get the overall complexity as O(n^2 log(k)) where n is the size of the array.

Space Complexity

We are using an extra space as a min-heap. Hence, the space complexity is O(k).

Check out this problem - Subarray With 0 Sum

Frequently Asked Questions

When can we expect an ArrayStoreException?

It is a runtime error. A String Array, for example, can only store string elements. If we try to insert an integer element into this String Array, we will get an ArrayStoreException at run time.

What is the limitation of an array?

The most significant limitation of arrays is that they must be defined in advance. This is only possible if the maximum array size is known ahead of time, and it may result in memory waste.

Can the size of the array change at runtime?

Thus, the size of the array is determined at the time of its creation or initialization; once done, the size of the array cannot be changed.

Conclusion

In this blog, we have discussed the problem of finding the K-th Largest Sum Contiguous Subarray. We started with introducing array and subarray, problem statement, examples, two approaches, and their implementation in C++, and finally concluded with the time and space complexity of each approach.

We hope that this blog has helped you enhance your knowledge of how to find the K-th Largest Sum Contiguous Subarray, and if you would like to learn more, you may check out our other articles on Data Structures.

Recommended problems -

For peeps out there who want to learn more about Data Structures, Algorithms, Power programming, JavaScript, or any other upskilling, please refer to guided paths on Coding Ninjas Studio. Enroll in our courses, go for mock tests, solve problems available, and interview puzzles. Also, you can put your attention towards interview stuff- interview experiences and an interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Coding!