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 indexesvector<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 codeint 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 approachclass 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 indexesdef 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 arrayarr = [1, 2, 20, 8, 8, 1, 2, 5, 8, 0, 6, 8, 2]M = 1query = [100, 4, 2]# Function callans = findindexes(arr, M, query)print(" ".join(map(str, ans)))# This code is contributed by phasing17 |
C#
// C# program to implement above approachusing 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 indexesfunction 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 arraylet arr = [1, 2, 20, 8, 8, 1, 2, 5, 8, 0, 6, 8, 2];let M = 1;let query = [100, 4, 2];// Function calllet ans = findindexes(arr, M, query);console.log(ans.join(" "));// This code is contributed by phasing17 |
Output
-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.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
