Given an array arr[], integer M and an array query[] containing Q queries, the task is to find the query[i]th occurrence of Mth most frequent element of the array.
Examples:
Input: arr[] = {1, 2, 20, 8, 8, 1, 2, 5, 8, 0, 6, 8, 2}, M = 1, query[] = {100, 4, 2}
Output: -1, 12, 5
Explanation: Here most frequent Integer = 8, with frequency = 4
Thus for Query
1) For k = 100, Output-> -1 (100th element not available)
2) For k = 4, Output -> 12 (4th occurrence of 8 is at 12th index)
3) For k = 2, Output -> 5 (2nd occurrence of 8 is at 5th index)Input: arr[] = {2, 2, 20, 8, 8, 1, 2, 5}, M = 2, query[] = {2, 3}
Output: 4, -1
Approach: The solution to the problem is based on the following idea:
Find the Mth most frequent element. Then store all the occurrences of the integers and find the query[i]th occurrence of the Mth most frequent element.
Follow the steps mentioned below to implement the idea:
- Declare map for integer and vector.
- Traverse through the input array and store the unique elements in the map as keys.
- Then push the index of the occurrences of that element into the vector.
- Store the unique elements with their frequency and find the Mth most frequent element.
- Again traverse through the queries.
- For each query, check if K < vector size then return -1.
- Else store the indexes of the element.
Follow the below illustration for a better understanding
Illustration:
arr[] = {1, 2, 20, 8, 8, 1, 2, 5, 8, 0, 6, 8, 2}, M = 1
Query_val = {100, 4, 2}Now for Each element the frequency and occurred indexes are:
1 -> 1, 6 frequency : 2
2 -> 2, 7, 13 frequency : 3
20 -> 3 frequency : 1
8 -> 4, 5, 9, 12 frequency : 4
5 -> 8 frequency : 1
0 -> 10 frequency : 1
6 -> 11 frequency : 1Thus maximum frequency element = 8 with frequency 4
Now for queries
For k = 100, -> -1 (k > maxfre)
For K = 4, -> 12 ((K-1) index of vector)
For K = 2, -> 5 ((K-1) index of vector)
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // Function for finding indexes vector< int > findindexes(vector< int > arr, int M, vector< int > query) { // Unordered map to store the unique // element as keys and vector as value // to store indexes unordered_map< int , vector< int > > fre; int n = arr.size(); // Ans vector to store and return // indexes occurred vector< int > ans; for ( int i = 0; i < n; i++) { // For each key push that particular // index+1 1-bases indexing fre[arr[i]].push_back(i + 1); } set<pair< int , int > > st; for ( auto it = fre.begin(); it != fre.end(); it++) { st.insert({ it->second.size(), it->first }); } int maxelement, i = 0; for ( auto it = st.rbegin(); it != st.rend() and i < M; it--, i++) { maxelement = (*it).second; } for ( int i = 0; i < query.size(); i++) { // If kth index is not available if (fre[maxelement].size() < query[i]) ans.push_back(-1); else { // Storing the indexes // of maxfre element ans.push_back( fre[maxelement][query[i] - 1]); } } return ans; } // Driver code int main() { // Input array vector< int > arr = { 1, 2, 20, 8, 8, 1, 2, 5, 8, 0, 6, 8, 2 }; int M = 1; vector< int > query = { 100, 4, 2 }; // Function call vector< int > ans = findindexes(arr, M, query); for ( int i = 0; i < ans.size(); i++) { cout << ans[i] << " " ; } return 0; } |
Java
import java.util.*; import java.io.*; // Java program for the above approach class GFG{ // Function for finding indexes public static ArrayList<Integer> findindexes(ArrayList<Integer> arr, int M, ArrayList<Integer> query) { // Unordered map to store the unique // element as keys and vector as value // to store indexes HashMap<Integer, ArrayList<Integer>> fre = new HashMap<Integer, ArrayList<Integer>>(); int n = arr.size(); // Ans vector to store and return // indexes occurred ArrayList<Integer> ans = new ArrayList<Integer>(); int i; for (i = 0 ; i < n ; i++) { // For each key push that particular // index+1 1-bases indexing if (!fre.containsKey(arr.get(i))){ fre.put(arr.get(i), new ArrayList<Integer>()); } fre.get(arr.get(i)).add(i + 1 ); } TreeSet<pair> st = new TreeSet<pair>( new Comp()); for (Map.Entry<Integer, ArrayList<Integer>> it : fre.entrySet()){ st.add( new pair(it.getValue().size(), it.getKey())); } int maxelement = 0 ; i = 0 ; for (pair it : st) { if (i >= M) break ; maxelement = it.second; i++; } for (i = 0 ; i < query.size() ; i++) { // If kth index is not available if (!fre.containsKey(maxelement)) { ans.add(- 1 ); } else { if (fre.get(maxelement).size() < query.get(i)) ans.add(- 1 ); else { // Storing the indexes // of maxfre element ans.add(fre.get(maxelement).get(query.get(i) - 1 )); } } } return ans; } // Driver Code public static void main(String args[]) { // Input array ArrayList<Integer> arr = new ArrayList<Integer>( List.of( 1 , 2 , 20 , 8 , 8 , 1 , 2 , 5 , 8 , 0 , 6 , 8 , 2 ) ); int M = 1 ; ArrayList<Integer> query = new ArrayList<Integer>( List.of( 100 , 4 , 2 ) ); // Function call ArrayList<Integer> ans = findindexes(arr, M, query); for ( int i = 0 ; i < ans.size() ; i++) { System.out.print(ans.get(i) + " " ); } } } public class pair{ public int first; public int second; public pair( int first, int second){ this .first = first; this .second = second; } } class Comp implements Comparator<pair>{ public int compare(pair o2, pair o1){ if (o1.first == o2.first){ return o1.second - o2.second; } return o1.first - o2.first; } } // This code is contributed by entertin2022. |
Python3
# Python3 code to implement the above approach # Function for finding indexes def findindexes(arr, M, query): # Unordered map to store the unique # element as keys and vector as value # to store indexes fre = dict () n = len (arr) # Ans vector to store and return # indexes occurred ans = [] for i in range (n): # For each key push that particular # index+1 1-bases indexing if arr[i] not in fre: fre[arr[i]] = [] fre[arr[i]].append(i + 1 ) st = set () for it in fre: st.add(( len (fre[it]), it)) # sorting the st in reverse st = sorted (st, reverse = True ) i = 0 for it in st: if i > = M: break maxelement = it[ 1 ] i + = 1 for i in range ( len (query)): # If kth index is not available if len (fre[maxelement]) < query[i]: ans.append( - 1 ) else : # Storing the indexes # of maxfre element ans.append(fre[maxelement][query[i] - 1 ]) return ans # Driver code # Input array arr = [ 1 , 2 , 20 , 8 , 8 , 1 , 2 , 5 , 8 , 0 , 6 , 8 , 2 ] M = 1 query = [ 100 , 4 , 2 ] # Function call ans = findindexes(arr, M, query) print ( " " .join( map ( str , ans))) # This code is contributed by phasing17 |
C#
// C# program to implement above approach using System; using System.Collections; using System.Collections.Generic; class GFG { // Function for finding indexes public static List< int > findindexes(List< int > arr, int M, List< int > query) { // Unordered map to store the unique // element as keys and vector as value // to store indexes Dictionary< int , List< int >> fre = new Dictionary< int , List< int >>(); int n = arr.Count; // Ans vector to store and return // indexes occurred List< int > ans = new List< int >(); int i; for (i = 0 ; i < n ; i++) { // For each key push that particular // index+1 1-bases indexing if (!fre.ContainsKey(arr[i])){ fre.Add(arr[i], new List< int >()); } fre[arr[i]].Add(i + 1); } SortedSet<pair> st = new SortedSet<pair>( new Comp()); foreach (KeyValuePair< int , List< int >> it in fre){ st.Add( new pair(it.Value.Count, it.Key)); } int maxelement = 0; i = 0; foreach (pair it in st) { if (i >= M) break ; maxelement = it.second; i++; } for (i = 0 ; i < query.Count ; i++) { // If kth index is not available if (!fre.ContainsKey(maxelement)) { ans.Add(-1); } else { if (fre[maxelement].Count < query[i]) ans.Add(-1); else { // Storing the indexes // of maxfre element ans.Add(fre[maxelement][query[i] - 1]); } } } return ans; } // Driver Code public static void Main( string [] args){ // Input array List< int > arr = new List< int >{ 1, 2, 20, 8, 8, 1, 2, 5, 8, 0, 6, 8, 2 }; int M = 1; List< int > query = new List< int >{ 100, 4, 2 }; // Function call List< int > ans = findindexes(arr, M, query); for ( int i = 0 ; i < ans.Count ; i++) { Console.Write(ans[i] + " " ); } } } public class pair{ public int first{ get ; set ; } public int second{ get ; set ; } public pair( int first, int second){ this .first = first; this .second = second; } } class Comp : IComparer<pair>{ public int Compare(pair o2,pair o1){ if (o1.first == o2.first){ return o1.second - o2.second; } return o1.first - o2.first; } } |
Javascript
//JavaScript code to implement the above approach // Function for finding indexes function findindexes(arr, M, query) { // Unordered map to store the unique // element as keys and vector as value // to store indexes let fre = {}; let n = arr.length; // Ans vector to store and return // indexes occurred let ans = []; for ( var i = 0; i < n; i++) { // For each key push that particular // index+1 1-bases indexing if (!fre.hasOwnProperty(arr[i])) fre[arr[i]] = []; fre[arr[i]].push(i + 1); } let st = []; for (const [it, val] of Object.entries(fre)) { st.push([fre[it].length, parseInt(it)]); } // sorting the st in reverse st.sort(); st.reverse(); i = 0; let maxelement; for ( var it of st) { if (i >= M) break ; maxelement = it[1]; i += 1; } for ( var i = 0; i < query.length; i++) { // If kth index is not available if (fre[maxelement].length < query[i]) ans.push(-1); else { // Storing the indexes // of maxfre element ans.push(fre[maxelement][query[i] - 1]); } } return ans; } // Driver code // Input array let arr = [1, 2, 20, 8, 8, 1, 2, 5, 8, 0, 6, 8, 2]; let M = 1; let query = [100, 4, 2]; // Function call let ans = findindexes(arr, M, query); console.log(ans.join( " " )); // This code is contributed by phasing17 |
-1 12 5
Time Complexity: O(N + Q + K * logK) Q = Number of queries, K = number of unique elements.
Auxiliary Space: O(N) where N is extra space as we are using unordered map to store element.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!