What is a multiset in C++?

A multiset is an associative container available in C++ STL. It stores the data in sorted order. It is similar to a set except that multiple elements can have the same value.

How is multiset implemented?

A multiset is often implemented as a red-black tree, but almost any other balanced tree could be used like AVL, B-tree, etc.

Table of contents

Introduction

Approach

Efficient Approach

Algorithm

C++ Code

Algorithm Complexity

FAQs

Key Takeaways

Last Updated: Mar 27, 2024

Find the largest K for every Array element such that at least K prefixes are ≥ K.

Author Jaglike Makkar

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

Yes

Introduction

Problem:

Given an integer ‘N’ and an array ‘arr[]’ of length ‘N’ consisting of non-negative integers, find the largest integer ‘K’ for every index ‘i’ such that at least ‘K’ integers are greater than or equal to ‘K’ in the subarray from 0 to ‘i’.

Let’s understand the problem with the help of an example:

Input: N = 5, arr = [ 3, 1, 4, 1, 5 ]

Output: 1 1 2 2 3

Explanation:

For ‘i’=0, the answer is 1, as only one prefix greater than or equal to one, i.e., 3.
For ‘i’=1, the answer is 1. Here, there is a total of two prefixes - 3 and 1, but we can’t choose ‘K’=2 as there is only one prefix greater than or equal to two. So, the answer is still 1.
For ‘i’=2, there are a total of three prefixes - 3, 1, and 4. If we choose ‘K’=2, there are two prefixes greater than or equal to K. For K=3, there are only two prefixes greater than or equal to K, so the answer can’t be 3.
For ‘i’=3, there are four prefixes - 3,1,4 and 1. For ‘K’=2, there are two prefixes greater than or equal two. So, it is a valid answer. For ‘K’=3, there are only two prefixes greater than or equal to K, so the answer is 2.
For ‘i’=4, there are a total of five prefixes - 3,1,4,1,5. For ‘K’ = 3, there are three prefixes greater than or equal to K. For ‘K’=4, there are only two prefixes greater than or equal to K. So the answer is 3.

Approach

One approach is to iterate over every ‘K’ for every index ‘i’ and check if it is valid or not. A particular ‘K’ is valid if at least ‘K’ prefixes greater than or equal to K. We can check this by simply iterating and maintaining a ‘count’ variable that stores the number of prefixes greater than or equal to K. If the current ‘K’ is valid, we update the answer. Else we break the loop.

C++ Code

#include <bits/stdc++.h>
using namespace std;

void solve(int n, int arr[]){

    // Iterating over every index
    for (int i = 0; i < n; i++){

        // Initializing answer as 0
        int ans = 0;

        // Iterating over every K and checking if it is valid
        for (int k = 1; k <= n; k++){
            int count = 0;

            // Finding count of numbers >= K
            for (int j = 0; j <= i; j++){
                if (arr[j] >= k){
                    count++;
                }
            }

            // If K is valid, updating the answer
            if (count >= k){
                ans = k;
            }
        }

        // Printing the answer
        cout<<ans<<' ';
    }
    cout<<endl;
}


// Driver code
int main(){
    int n = 5;
    int arr[] = {3, 1, 4, 1, 5};
    solve(n, arr);
    return 0;
}

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

Run Code

Output:

1 1 2 2 3

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

Run Code

Time Complexity = O(N ^ 3)

For every index ‘i’ from 0 to ‘N’, we use a nested loop for ‘K’ from 1 to ‘N’ and for ‘j’ from 0 to ‘i’. So the time taken for a single index is O(N^2). Therefore the total time complexity of the approach is O(N^3).

Space Complexity = O(1)

We have just created some variables in our above approach. Therefore the space complexity of our approach is O(1).

Efficient Approach

One thing to note in this problem is that for two indexes, ‘i’ and ‘j’ where ‘j’ > ’i’, the answer for the jth index will be greater than or equal to ith index. The answer will either increase or stay the same as we move ahead in the array. Therefore, if an element was once rejected, i.e., it was less than ‘K’, it will remain rejected.

We can use the above fact to solve the problem in an efficient way. We can maintain a multiset of elements. It will help us to store the prefixes in sorted order. Now, pop that element out if the smallest element in the multiset is less than the size of the multiset. The answer for any index ‘i’ will now be the size of the multiset as there are a ‘size’ number of prefixes greater than or equal to K.

Algorithm

Create a multiset ‘ms’.
Iterate, ‘i’ from 0 to N and insert the current element in ‘ms’.
Now check if the smallest element of the multiset is smaller than the size of the multiset.
1. If it is true, then pop the smallest element.
Print the size of the multiset.

C++ Code

#include <bits/stdc++.h>
using namespace std;

void solve(int n, int arr[]){

    // Initializing the multiset
    multiset<int> ms;

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

        // Inserting current element in the multiset
        ms.insert(arr[i]);

        // Checking if the smallest element is smaller than size.
        if (*ms.begin() < ms.size()) {

            // Erasing the smallest element
            ms.erase(ms.begin());
        }

        // Printing the size of the multiset.
        Cout << ms.size() <<' ';
    }
    Cout << endl;
}


// Driver code
int main(){
    int n = 5;
    int arr[] = {3, 1, 4, 1, 5};
    solve(n, arr);
    return 0;
}

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

Run Code

Output:

1 1 2 2 3

Algorithm Complexity

Time Complexity = O(NlogN)

For every index, we are inserting the current element in the multiset which takes O(logN) time, and we are popping out the smallest element, which is again O(logN). So the time complexity of the above approach is O(NlogN).

Space Complexity = O(N)

We are creating a new multiset ‘ms’, whose size can go till ‘N’ in the worst case. Therefore the space complexity of the above approach is O(N).

Check out this problem - Subarray With 0 Sum

FAQs

What is a multiset in C++?
A multiset is an associative container available in C++ STL. It stores the data in sorted order. It is similar to a set except that multiple elements can have the same value.
How is multiset implemented?
A multiset is often implemented as a red-black tree, but almost any other balanced tree could be used like AVL, B-tree, etc.

Key Takeaways

In this article, we discussed how to find the largest K for every index such that there is at least K number of prefixes greater than or equal to K. We also discussed the time and space complexity of our solution. If you want to solve more such problems, you can visit Coding Ninjas Studio.

If you think that this blog helped you share it with your friends!. To be more confident in data structures and algorithms, try out our DS and Algo Course.

Until then, All the best for your future endeavors, and Keep Coding.