Next Greater Frequency Element
Last Updated : 12 Sep, 2025
Given an array arr[], for each element, find the first element to its right that appears more times in the array than the current element. If no such element exists, assign -1.
Examples:
Input: arr[] = [2, 1, 1, 3, 2, 1]
Output: [1, -1, -1, 2, 1, -1]
Explanation: Frequencies: 1 → 3 times, 2 → 2 times, 3 → 1 time.
For arr[0] = 2, the next element 1 has a higher frequency → 1.
For arr[1] and arr[2] (1), no element to the right has a higher frequency → -1.
For arr[3] = 3, the next 2 has a higher frequency → 2.
For arr[4] = 2, the next 1 has a higher frequency → 1.
For arr[5] = 1, no elements to the right → -1.
Input: arr[] = [1, 2, 1]
Output: [-1, 1, -1]
Explanation: Frequencies: 1 → 2, 2 → 1.
2→1 (higher freq), others have no higher freq on right → [-1, 1, -1]
[Naive approach] Frequency Count and Nested Loop - O(n2) Time and O(n) Space
The idea is to find, for each element, the next element to its right that has a higher frequency using a frequency map and a nested loop. If none exists, return -1.
C++ #include <iostream> #include <vector> #include <unordered_map> using namespace std; vector<int> nextFreqGreater(vector<int>& arr) { // calculate frequency of each element // using a hash map (unordered_map). unordered_map<int, int> freq; for (int num : arr) { freq[num]++; } vector<int> result; for (int i = 0; i < arr.size(); i++) { bool found = false; // inner loop to find the first element // with a greater frequency for (int j = i + 1; j < arr.size(); j++) { if (freq[arr[j]] > freq[arr[i]]) { result.push_back(arr[j]); found = true; break; } } // if no element with a greater frequency // is found, push -1 if (!found) { result.push_back(-1); } } return result; } int main() { vector<int> arr = {2, 1, 1, 3, 2, 1}; vector<int> result = nextFreqGreater(arr); for (int num : result) { cout << num << " "; } cout << endl; return 0; } import java.util.HashMap; import java.util.Map; import java.util.ArrayList; class GfG { public static ArrayList<Integer> nextFreqGreater(int[] arr) { // calculate frequency of // each element using a hash map. Map<Integer, Integer> freq = new HashMap<>(); for (int num : arr) { freq.put(num, freq.getOrDefault(num, 0) + 1); } ArrayList<Integer> result = new ArrayList<>(); for (int i = 0; i < arr.length; i++) { boolean found = false; // inner loop to find the first // element with a greater frequency for (int j = i + 1; j < arr.length; j++) { if (freq.get(arr[j]) > freq.get(arr[i])) { result.add(arr[j]); found = true; break; } } // if no element with a greater // frequency is found, set -1 if (!found) { result.add(-1); } } return result; } public static void main(String[] args) { int[] arr = {2, 1, 1, 3, 2, 1}; ArrayList<Integer> result = nextFreqGreater(arr); for (int num : result) { System.out.print(num + " "); } System.out.println(); } } from collections import Counter def nextFreqGreater(arr): # calculate frequency of each # element using Counter. freq = Counter(arr) result = [] for i in range(len(arr)): found = False # inner loop to find the first element # with a greater frequency for j in range(i + 1, len(arr)): if freq[arr[j]] > freq[arr[i]]: result.append(arr[j]) found = True break # if no element with a greater frequency # is found, append -1 if not found: result.append(-1) return result if __name__ == "__main__": arr = [2, 1, 1, 3, 2, 1] result = nextFreqGreater(arr) print(' '.join(map(str, result))) using System; using System.Collections.Generic; class GfG { public static List<int> nextFreqGreater(int[] arr) { // calculate frequency of // each element using a dictionary Dictionary<int, int> freq = new Dictionary<int, int>(); foreach (int num in arr) { if (freq.ContainsKey(num)) { freq[num]++; } else { freq[num] = 1; } } List<int> result = new List<int>(); for (int i = 0; i < arr.Length; i++) { bool found = false; // inner loop to find the first // element with a greater frequency for (int j = i + 1; j < arr.Length; j++) { if (freq[arr[j]] > freq[arr[i]]) { result.Add(arr[j]); found = true; break; } } // if no element with a greater // frequency is found, add -1 if (!found) { result.Add(-1); } } return result; } static void Main() { int[] arr = {2, 1, 1, 3, 2, 1}; List<int> result = nextFreqGreater(arr); Console.WriteLine(string.Join(" ", result)); } } function nextFreqGreater(arr) { // calculate frequency of // each element using an object. const freq = {}; arr.forEach(num => { freq[num] = (freq[num] || 0) + 1; }); const result = []; for (let i = 0; i < arr.length; i++) { let found = false; // inner loop to find the first // element with a greater frequency for (let j = i + 1; j < arr.length; j++) { if (freq[arr[j]] > freq[arr[i]]) { result.push(arr[j]); found = true; break; } } // if no element with a greater // frequency is found, push -1 if (!found) { result.push(-1); } } return result; } // Driver Code const arr = [2, 1, 1, 3, 2, 1]; const result = nextFreqGreater(arr); console.log(result.join(' ')); [Efficient Approach] Frequency Counting and Stack - O(n) Time and O(n) Space
The idea is to use a frequency map to count occurrences, then apply a stack-based approach (similar to "Next Greater Element") to efficiently find the next element with a higher frequency for each position. For each element, we compare its frequency with elements tracked in the stack and update the result when a higher frequency is found.
C++ #include <iostream> #include <stack> #include <vector> #include <unordered_map> using namespace std; vector<int> nextFreqGreater(vector<int>& arr) { int n = arr.size(); unordered_map<int, int> freq; // Building Frequency Map for (int i = 0; i < arr.size(); ++i) { freq[arr[i]]++; } vector<int> res(n, -1); stack<int> st; for (int i = 0; i < n; i++) { // While current frequency is // greater than frequency at stack top while (!st.empty() && freq[arr[i]] > freq[arr[st.top()]]) { res[st.top()] = arr[i]; st.pop(); } st.push(i); } return res; } int main() { vector<int> arr = {2, 1, 1, 3, 2, 1}; vector<int> result = nextFreqGreater(arr); for (int x : result) { cout << x << " "; } return 0; } import java.util.Stack; import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.ArrayList; class GfG { public static ArrayList<Integer> nextFreqGreater(int[] arr) { int n = arr.length; Map<Integer, Integer> freq = new HashMap<>(); for (int num : arr) { freq.put(num, freq.getOrDefault(num, 0) + 1); } int[] res = new int[n]; Arrays.fill(res, -1); Stack<Integer> st = new Stack<>(); for (int i = 0; i < n; i++) { // While current frequency is greater // than frequency at stack top while (!st.isEmpty() && freq.get(arr[i]) > freq.get(arr[st.peek()])) { res[st.pop()] = arr[i]; } st.push(i); } // Convert array to ArrayList and return ArrayList<Integer> result = new ArrayList<>(); for (int x : res) { result.add(x); } return result; } public static void main(String[] args) { int[] arr = {2, 1, 1, 3, 2, 1}; ArrayList<Integer> result = nextFreqGreater(arr); for (int x : result) { System.out.print(x + " "); } } } def nextFreqGreater(arr): n = len(arr) freq = {} # Build frequency map for num in arr: freq[num] = freq.get(num, 0) + 1 res = [-1] * n st = [] for i in range(n): # While current frequency is # greater than frequency at stack top while st and freq[arr[i]] > freq[arr[st[-1]]]: res[st.pop()] = arr[i] st.append(i) return res if __name__ == "__main__": arr = [2, 1, 1, 3, 2, 1] result = nextFreqGreater(arr) print(' '.join(map(str, result))) using System; using System.Collections.Generic; class GfG { public static List<int> nextFreqGreater(int[] arr) { int n = arr.Length; Dictionary<int, int> freq = new Dictionary<int, int>(); // Build frequency map foreach (var num in arr) { if (freq.ContainsKey(num)) freq[num]++; else freq[num] = 1; } int[] res = new int[n]; Array.Fill(res, -1); Stack<int> st = new Stack<int>(); for (int i = 0; i < n; i++) { // While current frequency is // greater than frequency at stack top while (st.Count > 0 && freq[arr[i]] > freq[arr[st.Peek()]]) { res[st.Pop()] = arr[i]; } st.Push(i); } // Convert array to List<int> and return List<int> result = new List<int>(); foreach (int x in res) { result.Add(x); } return result; } static void Main() { int[] arr = {2, 1, 1, 3, 2, 1}; List<int> result = nextFreqGreater(arr); Console.WriteLine(string.Join(" ", result)); } } function nextFreqGreater(arr) { let n = arr.length; let freq = {}; // Build frequency map for (let num of arr) { freq[num] = (freq[num] || 0) + 1; } let res = new Array(n).fill(-1); let st = []; for (let i = 0; i < n; i++) { // While current frequency is // greater than frequency at stack top while (st.length > 0 && freq[arr[i]] > freq[arr[st[st.length - 1]]]) { res[st.pop()] = arr[i]; } st.push(i); } return res; } // Driver Code let arr = [2, 1, 1, 3, 2, 1]; let result = nextFreqGreater(arr); console.log(result.join(' '));
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem
My Profile