Find K for every Array element such that at least K prefixes are ≥ K
Given an array arr[] consisting of N non-negative integers, the task is to find an integer K for every index such that at least K integers in the array till that index are greater or equal to K.
Note: Consider 1-based indexing
Examples:
Input: arr[] = {3, 0, 6, 1, 5}
Output: K = {1, 1, 2, 2, 3}
Explanation:
At index 1, there is 1 number greater than or equal to 1 in the array i.e. 3. So the K value for elements up to index 1 is 1.
At index 2, there is 1 number greater than or equal to 1 in the array i.e. 3. So the K value for elements up to index 2 is 1.
At index 3, there are 2 numbers greater than or equal to 2 in the array, i.e. 3 and 6. So the K value for elements up to index 3 is 2.
At index 4, there are 2 numbers greater than or equal to 2 in the array, i.e. 3 and 6. So the K value for elements up to index 4 is 2.
At index 5, there are 3 numbers greater than or equal to 3 in the array, i.e. 3, 6 and 5. So the K value for elements up to index 5 is 3.Input: arr[] = {9, 10, 7, 5, 0, 10, 2, 0}
Output: K = {1, 2, 3, 4, 4, 5, 5, 5}
Naive Approach:
The simplest approach is to find the value of K for all the elements of the array in the range [0, i], where i is the index of the array arr[], using the efficient approach used in the article link is given here.
Time Complexity: O(N2)
Space Complexity: O(N)
Efficient Approach:
The idea is to use Multiset(Red-Black Tree). Multiset stores the values in a sorted order which helps to check if the current minimum value in the multiset is greater than or equal to its size. If yes, then the value of the integer K will be the size of the multiset.
Below are the steps for the implementation:
- Traverse the array from index 0 to N-1.
- For each index, insert the element into the multiset and check if the smallest value in the multiset is less than the size of the multiset.
- If true, then erase the starting element and print the size of the multiset.
- If false, then simply print the size of the multiset.
- The size of the multiset is the required K value for every index i.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the K-value // for every index in the array int print_h_index( int arr[], int N) { // Multiset to store the array // in the form of red-black tree multiset< int > ms; // Iterating over the array for ( int i = 0; i < N; i++) { // Inserting the current // value in the multiset ms.insert(arr[i]); // Condition to check if // the smallest value // in the set is less than // it's size if (*ms.begin() < ms.size()) { // Erase the smallest // value ms.erase(ms.begin()); } // h-index value will be // the size of the multiset cout << ms.size() << " " ; } } // Driver Code int main() { // array int arr[] = { 9, 10, 7, 5, 0, 10, 2, 0 }; // Size of the array int N = sizeof (arr) / sizeof (arr[0]); // function call print_h_index(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the K-value // for every index in the array static void print_h_index( int arr[], int N) { // Multiset to store the array // in the form of red-black tree List<Integer> ms = new ArrayList<Integer>(); // Iterating over the array for ( int i = 0 ; i < N; i++) { // Inserting the current // value in the multiset ms.add(arr[i]); // Condition to check if // the smallest value // in the set is less than // it's size int t = Collections.min(ms); if (t < ms.size()) { // Erase the smallest // value ms.remove(ms.indexOf(t)); } // h-index value will be // the size of the multiset System.out.print(ms.size() + " " ); } } // Driver code public static void main(String[] args) { // Array int arr[] = { 9 , 10 , 7 , 5 , 0 , 10 , 2 , 0 }; // Size of the array int N = arr.length; // Function call print_h_index(arr, N); } } // This code is contributed by offbeat |
Python3
# Python3 program for the above approach # Function to find the K-value # for every index in the array def print_h_index(arr, N): # Multiset to store the array # in the form of red-black tree ms = [] # Iterating over the array for i in range (N): # Inserting the current # value in the multiset ms.append(arr[i]) ms.sort() # Condition to check if # the smallest value # in the set is less than # it's size if (ms[ 0 ] < len (ms)): # Erase the smallest # value ms.pop( 0 ) # h-index value will be # the size of the multiset print ( len (ms), end = ' ' ) # Driver Code if __name__ = = '__main__' : # Array arr = [ 9 , 10 , 7 , 5 , 0 , 10 , 2 , 0 ] # Size of the array N = len (arr) # Function call print_h_index(arr, N) # This code is contributed by pratham76 |
C#
// C# program for the above approach using System; using System.Collections; using System.Collections.Generic; class GFG{ // Function to find the K-value // for every index in the array static void print_h_index( int []arr, int N) { // Multiset to store the array // in the form of red-black tree ArrayList ms = new ArrayList(); // Iterating over the array for ( int i = 0; i < N; i++) { // Inserting the current // value in the multiset ms.Add(arr[i]); // Condition to check if // the smallest value // in the set is less than // it's size int t = int .MaxValue; foreach ( int x in ms) { if (x < t) { t = x; } } if (t < ms.Count) { // Erase the smallest // value ms.Remove(t); } // h-index value will be // the size of the multiset Console.Write(ms.Count + " " ); } } // Driver code public static void Main( string [] args) { // Array int []arr = { 9, 10, 7, 5, 0, 10, 2, 0 }; // Size of the array int N = arr.Length; // Function call print_h_index(arr, N); } } // This code is contributed by rutvik_56 |
Javascript
<script> // Javascript program for the above approach // Function to find the K-value // for every index in the array function print_h_index(arr, N) { // Multiset to store the array // in the form of red-black tree var ms = []; // Iterating over the array for ( var i = 0; i < N; i++) { // Inserting the current // value in the multiset ms.push(arr[i]); ms.sort((a,b)=> a-b) // Condition to check if // the smallest value // in the set is less than // it's size if (ms[0] < ms.length) { // Erase the smallest // value ms.shift(); } // h-index value will be // the size of the multiset document.write( ms.length + " " ); } } // Driver Code // array var arr = [9, 10, 7, 5, 0, 10, 2, 0 ]; // Size of the array var N = arr.length; // function call print_h_index(arr, N); </script> |
1 2 3 4 4 5 5 5
Time Complexity: O(N * log(N))
Auxiliary Space Complexity: O(N)