Given an array arr[] of N integers, and an array Q[] of M pairs, where a pair represents a query of the form {L, R}, the task is to find the maximum occurring element in the range [L, R] and its frequency for each query. If there are multiple elements with maximum frequency, then print the maximum element among them.
Examples:
Input: arr[] = {5, 7, 5, 5, 2, 7, 3, 2, 5, 2}, Q[] = {{0, 9}, {3, 6}, {4, 8}, {1, 5}}
Output: 5 Occurs 4 times
3 Occurs 1 times
2 Occurs 2 times
7 Occurs 2 times
Explanation:
The queries are performed as:
- Query(0, 9): The subarray over the range is {5, 7, 5, 5, 2, 7, 3, 2, 5, 2}. Elements 5, 7, 2, and 3 occur 4, 2, 3 and 1 times respectively. Therefore, print 5.
- Query(3, 6): The subarray over the range is {5, 2, 7, 3}. Every element occurs once. So print element 7.
- Query(4, 8): The subarray over the range is {2, 7, 3, 2, 5}. Element 2 occurs twice and the remaining all occurs once. Therefore, print 2.
- Query(1, 5): The subarray over the range is {7, 5, 5, 2, 7, 3}. Elements 7 and 5 occur twice and the remaining elements occur once. Therefore print 7.
Naive Approach: For each query, iterate over the given range [L, R] keep updating the frequency of every element in an auxiliary data structure (ex. map). After processing the entire range of the current query, iterate over all elements in the map, and find the element having the maximum frequency.
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 elements having// maximum frequency for the query rangevoid getMaxOccuringElement(int arr[], int N, int M, pair<int, int> Q[]){ // Iterate over all the queries for (int i = 0; i < M; ++i) { // Stores the frequency of each element // in the current query range [l, r] map<int, int> freq; int l = Q[i].first, r = Q[i].second; for (int j = l; j <= r; ++j) ++freq[arr[j]]; int maxFreqElement = -1; int maxFreq = -1; // Iterate over the map and find the // element having maximum frequency for (auto it : freq) { if (it.second >= maxFreq) { maxFreqElement = it.first; maxFreq = it.second; } } // Print the answer for current query cout << maxFreqElement << " Occurs " << maxFreq << " times" << endl; }}// Driver Codeint main(){ int arr[] = { 5, 7, 5, 5, 2, 7, 3, 2, 5, 2 }; pair<int, int> Q[] = { { 0, 9 }, { 3, 6 }, { 4, 8 }, { 1, 5 } }; int N = sizeof(arr) / sizeof(arr[0]); int M = sizeof(Q) / sizeof(Q[0]); getMaxOccuringElement(arr, N, M, Q); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ static class pair { int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to find the elements having// maximum frequency for the query rangestatic void getMaxOccuringElement(int arr[], int N, int M, pair Q[]){ // Iterate over all the queries for (int i = 0; i < M; ++i) { // Stores the frequency of each element // in the current query range [l, r] HashMap<Integer,Integer> freq = new HashMap<Integer,Integer>(); int l = Q[i].first, r = Q[i].second; for (int j = l; j <= r; ++j) { if(freq.containsKey(arr[j])) freq.put(arr[j], freq.get(arr[j])+1); else freq.put(arr[j], 1); } int maxFreqElement = -1; int maxFreq = -1; // Iterate over the map and find the // element having maximum frequency for (Map.Entry<Integer,Integer> it : freq.entrySet()) { if (it.getValue() >= maxFreq) { maxFreqElement = it.getKey(); maxFreq = it.getValue(); } } // Print the answer for current query System.out.print(maxFreqElement+ " Occurs " + maxFreq + " times" +"\n"); }}// Driver Codepublic static void main(String[] args){ int arr[] = { 5, 7, 5, 5, 2, 7, 3, 2, 5, 2 }; pair Q[] = { new pair( 0, 9 ), new pair( 3, 6 ), new pair( 4, 8 ), new pair( 1, 5 ) }; int N = arr.length; int M = Q.length; getMaxOccuringElement(arr, N, M, Q);}}// This code contributed by Princi Singh |
Python3
# Python program for the above approachdef getMaxOccuringElement(arr, N, M, Q): # Iterate over all the queries for i in range(M): # Stores the frequency of each element in the current query range [l, r] freq = {} l = Q[i][0] r = Q[i][1] for j in range(l, r+1): if arr[j] in freq: freq[arr[j]] += 1 else: freq[arr[j]] = 1 max_freq_element = -1 max_freq = -1 # Iterate over the map and find the element having maximum frequency for key, value in freq.items(): if value > max_freq: max_freq_element = key max_freq = value if value == max_freq: max_freq_element = max(max_freq_element,key) print(str(max_freq_element) + " Occurs " + str(max_freq) + " times")# Driver Codearr = [ 5, 7, 5, 5, 2, 7, 3, 2, 5, 2 ]Q = [(0, 9), (3, 6), (4, 8), (1, 5)]N = len(arr)M = len(Q)getMaxOccuringElement(arr, N, M, Q) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ class pair { public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to find the elements having// maximum frequency for the query rangestatic void getMaxOccuringElement(int []arr, int N, int M, pair []Q){ // Iterate over all the queries for (int i = 0; i < M; ++i) { // Stores the frequency of each element // in the current query range [l, r] Dictionary<int,int> freq = new Dictionary<int,int>(); int l = Q[i].first, r = Q[i].second; for (int j = l; j <= r; ++j) { if(freq.ContainsKey(arr[j])) freq[arr[j]] = freq[arr[j]]+1; else freq.Add(arr[j], 1); } int maxFreqElement = -1; int maxFreq = -1; // Iterate over the map and find the // element having maximum frequency foreach (KeyValuePair<int,int> it in freq) { if (it.Value >= maxFreq) { maxFreqElement = it.Key; maxFreq = it.Value; } } // Print the answer for current query Console.Write(maxFreqElement+ " Occurs " + maxFreq + " times" +"\n"); }}// Driver Codepublic static void Main(String[] args){ int []arr = { 5, 7, 5, 5, 2, 7, 3, 2, 5, 2 }; pair []Q = { new pair( 0, 9 ), new pair( 3, 6 ), new pair( 4, 8 ), new pair( 1, 5 ) }; int N = arr.Length; int M = Q.Length; getMaxOccuringElement(arr, N, M, Q);}}// This code is contributed by 29AjayKumar |
Javascript
// JavaScript program for the above approachfunction getMaxOccuringElement(arr, N, M, Q) { // Iterate over all the queries for (let i = 0; i < M; i++) { // Stores the frequency of each element in the current query range [l, r] const freq = {}; const l = Q[i][0]; const r = Q[i][1]; for (let j = l; j <= r; j++) { if (arr[j] in freq) { freq[arr[j]] += 1; } else { freq[arr[j]] = 1; } } let max_freq_element = -1; let max_freq = -1; // Iterate over the map and find the element having maximum frequency for (const [key, value] of Object.entries(freq)) { if (value > max_freq) { max_freq_element = key; max_freq = value; } if (value === max_freq) { max_freq_element = Math.max(max_freq_element, key); } } console.log(max_freq_element + " Occurs " + max_freq + " times"); }}// Driver Codeconst arr = [5, 7, 5, 5, 2, 7, 3, 2, 5, 2];const Q = [ [0, 9], [3, 6], [4, 8], [1, 5]];const N = arr.length;const M = Q.length;getMaxOccuringElement(arr, N, M, Q); |
Output
5 Occurs 4 times 7 Occurs 1 times 2 Occurs 2 times 7 Occurs 2 times
Time Complexity: O(M * N)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized by Mo’s Algorithm based on the concept of sqrt decomposition. Follow the steps below to solve the problem:
- The queries are sorted in non-decreasing order of the blocks in which their left index falls. If two or more queries have their left indexes in the same block, then order them based on their right indexes.
- Basically, compute the answer for all queries which have their left index in block 0, then block 1, and so on till the last block.
- Maintain a map data structure (num_freq) which stores the count of occurrence of each element in the current query range.
- Also, maintain a set data structure (freq_num), whose each element is a pair (the first element of the pair represents the count of occurrence of an element and the second element of the pair represents the element itself).
- The set(freq_num) stores the elements in non-decreasing order. The ordering of elements in the set is based on the first item of the pair, which represents the frequency.
- Thus, while answering the queries (i.e. the element having the maximum frequency), it can be done in O(1).
Below is the implementation of the above approach :
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;int BLOCK_SIZE;// Structure to represent a query range// and its indexstruct query { int l, r, idx;};// Custom comparatorbool comparator(query a, query b){ if ((a.l / BLOCK_SIZE) != (b.l / BLOCK_SIZE)) return (a.l / BLOCK_SIZE) < (b.l / BLOCK_SIZE); return ((a.l / BLOCK_SIZE) & 1) ? (a.r < b.r) : (a.r > b.r);}// Function to add elements to the current rangevoid expand(int idx, int* arr, map<int, int>& numFreq, set<pair<int, int> >& freqNum){ // Remove current element from the set freqNum.erase({ numFreq[arr[idx]], arr[idx] }); // Increment current element count in the // map ++numFreq[arr[idx]]; // Insert current element into the set freqNum.insert({ numFreq[arr[idx]], arr[idx] });}// Function to remove elements from the current rangevoid shrink(int idx, int* arr, map<int, int>& numFreq, set<pair<int, int> >& freqNum){ // Remove current element from the set freqNum.erase({ numFreq[arr[idx]], arr[idx] }); // Decrement current element count in the // map --numFreq[arr[idx]]; // Insert current element into the set freqNum.insert({ numFreq[arr[idx]], arr[idx] });}// Function for Mo's algorithmpair<int, int>sqrtDecomposition(int& L, int& R, int l, int r, int* arr, set<pair<int, int> >& freqNum, map<int, int>& numFreq){ // Iterate until L is greater than l while (L > l) { --L; expand(L, arr, numFreq, freqNum); } // Iterate until R is less than r while (R < r) { ++R; expand(R, arr, numFreq, freqNum); } // Iterate until L is less than l while (L < l) { shrink(L, arr, numFreq, freqNum); ++L; } // Iterate until R is greater than r while (R > r) { shrink(R, arr, numFreq, freqNum); --R; } // Stores the answer for current query pair<int, int> last = *prev(freqNum.end()); // Return the answer return last;}// Function to find the element having maximum// frequency and its frequency for all the queriesvoid getMaxOccuringElement(int arr[], int N, int M, pair<int, int> Q[]){ // Compute each block size BLOCK_SIZE = (int)sqrt(N + .0) + 1; // Stores the queries query queries[M]; for (int i = 0; i < M; ++i) { queries[i].l = Q[i].first; queries[i].r = Q[i].second; queries[i].idx = i; } // Sort all the queries sort(queries, queries + M, comparator); // Initiali ranges of Mos int L = 0, R = -1; // Stores the answer pair<int, int> ans[M]; set<pair<int, int> > freqNum; map<int, int> numFreq; // Traverse the query array for (int i = 0; i < M; ++i) { int l = queries[i].l; int r = queries[i].r; // Stores the answer for current // query ans[queries[i].idx] = sqrtDecomposition( L, R, l, r, arr, freqNum, numFreq); } // Print the answer for (int i = 0; i < M; ++i) { cout << ans[i].second << " Occurs " << ans[i].first << " times" << endl; }}// Driver Codeint main(){ int arr[] = { 5, 7, 5, 5, 2, 7, 3, 2, 5, 2 }; pair<int, int> Q[] = { { 0, 9 }, { 3, 6 }, { 4, 8 }, { 1, 5 } }; int N = sizeof(arr) / sizeof(arr[0]); int M = sizeof(Q) / sizeof(Q[0]); getMaxOccuringElement(arr, N, M, Q); return 0;} |
Output
5 Occurs 4 times 7 Occurs 1 times 2 Occurs 2 times 7 Occurs 2 times
Time Complexity: O((N+M) * log(N) * sqrt(N))
Auxiliary Space: O(N)
Approach: Hash Map with Subarray Frequency Counting
Here’s the approach in detail:
- Create a hash map to store the frequency of each element in the array.
- For each query {L, R}, initialize a new hash map to store the frequency of each element in the subarray arr[L…R].
- Iterate over the subarray arr[L…R] and update the frequency of each element in the subarray hash map.
- Find the element with a maximum frequency in the subarray hash map and its frequency.
- Print the element and its frequency.
C++
#include <iostream>#include <unordered_map>using namespace std;int main() { int arr[] = {5, 7, 5, 5, 2, 7, 3, 2, 5, 2}; int n = sizeof(arr)/sizeof(arr[0]); pair<int, int> queries[] = {{0, 9}, {3, 6}, {4, 8}, {1, 5}}; int m = sizeof(queries)/sizeof(queries[0]); unordered_map<int, int> freq; for(int i=0; i<n; i++) { freq[arr[i]]++; } for(int i=0; i<m; i++) { int l = queries[i].first; int r = queries[i].second; unordered_map<int, int> sub_freq; int max_freq = 0, max_elem = -1; for(int j=l; j<=r; j++) { sub_freq[arr[j]]++; if(sub_freq[arr[j]] > max_freq || (sub_freq[arr[j]] == max_freq && arr[j] > max_elem)) { max_freq = sub_freq[arr[j]]; max_elem = arr[j]; } } cout << max_elem << " Occurs " << max_freq << " times\n"; } return 0;} |
Java
import java.util.*;public class Main { // Driver Code public static void main(String[] args) { int[] arr = { 5, 7, 5, 5, 2, 7, 3, 2, 5, 2 }; int n = arr.length; int[][] queries = { { 0, 9 }, { 3, 6 }, { 4, 8 }, { 1, 5 } }; int m = queries.length; Map<Integer, Integer> freq = new HashMap<>(); for (int i = 0; i < n; i++) { freq.put(arr[i], freq.getOrDefault(arr[i], 0) + 1); } for (int i = 0; i < m; i++) { int l = queries[i][0]; int r = queries[i][1]; Map<Integer, Integer> subFreq = new HashMap<>(); int maxFreq = 0; int maxElem = -1; for (int j = l; j <= r; j++) { subFreq.put(arr[j], subFreq.getOrDefault(arr[j], 0) + 1); if (subFreq.get(arr[j]) > maxFreq || (subFreq.get(arr[j]) == maxFreq && arr[j] > maxElem)) { maxFreq = subFreq.get(arr[j]); maxElem = arr[j]; } } System.out.println(maxElem + " Occurs " + maxFreq + " times"); } }} |
Python3
from collections import defaultdictarr = [5, 7, 5, 5, 2, 7, 3, 2, 5, 2]n = len(arr)queries = [(0, 9), (3, 6), (4, 8), (1, 5)]m = len(queries)freq = defaultdict(int)for i in range(n): freq[arr[i]] += 1for i in range(m): l, r = queries[i] sub_freq = defaultdict(int) max_freq, max_elem = 0, -1 for j in range(l, r+1): sub_freq[arr[j]] += 1 if sub_freq[arr[j]] > max_freq or (sub_freq[arr[j]] == max_freq and arr[j] > max_elem): max_freq = sub_freq[arr[j]] max_elem = arr[j] print(max_elem, "Occurs", max_freq, "times") |
C#
using System;using System.Collections.Generic;class MainClass { public static void Main(string[] args) { int[] arr = {5, 7, 5, 5, 2, 7, 3, 2, 5, 2}; int n = arr.Length; Tuple<int, int>[] queries = {Tuple.Create(0, 9), Tuple.Create(3, 6), Tuple.Create(4, 8), Tuple.Create(1, 5)}; int m = queries.Length; Dictionary<int, int> freq = new Dictionary<int, int>(); for(int i=0; i<n; i++) { if(freq.ContainsKey(arr[i])) freq[arr[i]]++; else freq[arr[i]] = 1; } for(int i=0; i<m; i++) { int l = queries[i].Item1; int r = queries[i].Item2; Dictionary<int, int> sub_freq = new Dictionary<int, int>(); int max_freq = 0, max_elem = -1; for(int j=l; j<=r; j++) { if(sub_freq.ContainsKey(arr[j])) sub_freq[arr[j]]++; else sub_freq[arr[j]] = 1; if(sub_freq[arr[j]] > max_freq || (sub_freq[arr[j]] == max_freq && arr[j] > max_elem)) { max_freq = sub_freq[arr[j]]; max_elem = arr[j]; } } Console.WriteLine(max_elem + " Occurs " + max_freq + " times"); } Console.ReadLine(); }} |
Javascript
let arr = [5, 7, 5, 5, 2, 7, 3, 2, 5, 2];let n = arr.length;let queries = [[0, 9], [3, 6], [4, 8], [1, 5]];let m = queries.length;let freq = new Map();for (let i = 0; i < n; i++) { if (freq.has(arr[i])) freq.set(arr[i], freq.get(arr[i]) + 1); else freq.set(arr[i], 1);}for (let i = 0; i < m; i++) { let l = queries[i][0]; let r = queries[i][1]; let sub_freq = new Map(); let max_freq = 0, max_elem = -1; for (let j = l; j <= r; j++) { if (sub_freq.has(arr[j])) sub_freq.set(arr[j], sub_freq.get(arr[j]) + 1); else sub_freq.set(arr[j], 1); if (sub_freq.get(arr[j]) > max_freq || (sub_freq.get(arr[j]) === max_freq && arr[j] > max_elem)) { max_freq = sub_freq.get(arr[j]); max_elem = arr[j]; } } console.log(max_elem + " occurs " + max_freq + " times");} |
Output
5 Occurs 4 times 7 Occurs 1 times 2 Occurs 2 times 7 Occurs 2 times
Time Complexity: O(M*N) where M is the number of queries and N is the size of the array.
Auxiliary Space: O(N)
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!
