18. Next Element with Greater Frequency

✅ GFG solution to find the next element with greater frequency using stack-based approach with frequency mapping for optimal performance. 🚀

The problem can be found at the following link: 🔗 Question Link

🧩 Problem Description

Given an array arr[] of integers, for each element, find the first element to its right that has a higher frequency than the current element. If no such element exists, return -1 for that position.

📘 Examples

Example 1

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], no element to the right has a higher frequency → -1.
For arr[3] = 3, the next element 2 has a higher frequency → 2.
For arr[4] = 2, the next element 1 has a higher frequency → 1.
For arr[5] = 1, no elements to the right → -1.

Example 2

Input: arr[] = [5, 1, 5, 6, 6]
Output: [-1, 5, -1, -1, -1]
Explanation: Frequencies: 1 → 1 time, 5 → 2 times, 6 → 2 times.
For arr[0] and arr[2], no element to the right has a higher frequency → -1.
For arr[1] = 1, the next element 5 has a higher frequency → 5.
For arr[3] and arr[4], no element to the right has a higher frequency → -1.

🔒 Constraints

$1 \le \text{arr.size()} \le 10^5$
$1 \le \text{arr}[i] \le 10^5$

✅ My Approach

The optimal approach combines Frequency Mapping with a Monotonic Stack technique to efficiently find the next greater frequency element:

Frequency Map + Monotonic Stack (Backward Traversal)

Build Frequency Map:
- Traverse the entire array once to count frequency of each element.
- Store frequencies in an unordered map for O(1) lookup.
Initialize Result and Stack:
- Create result vector initialized with -1 for all positions.
- Use stack to store indices in decreasing order of their frequencies.
Backward Traversal:
- Traverse array from right to left (n-1 to 0).
- For current index i, compare frequency of arr[i] with stack top frequencies.
Stack Maintenance:
- Pop indices from stack while their frequency is less than or equal to current element's frequency.
- If stack is not empty after popping, the top index gives the answer.
- Push current index onto stack for future comparisons.
Result Construction:
- When a valid next greater frequency element is found, store its value in result array.
- Otherwise, -1 remains as the default value.

📝 Time and Auxiliary Space Complexity

Expected Time Complexity: O(n), where n is the size of the array. The frequency map is built in O(n) time. Each element is pushed and popped from the stack at most once during the backward traversal, resulting in O(n) operations overall.
Expected Auxiliary Space Complexity: O(n), as we use a hash map to store frequencies of up to n distinct elements, a stack that can hold up to n indices in the worst case, and a result vector of size n.

🧑‍💻 Code (C++)

class Solution {
public:
    vector<int> nextFreqGreater(vector<int>& arr) {
        int n = arr.size();
        unordered_map<int, int> freq;
        for (int x : arr) freq[x]++;
        vector<int> res(n, -1);
        stack<int> st;
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && freq[arr[st.top()]] <= freq[arr[i]]) st.pop();
            if (!st.empty()) res[i] = arr[st.top()];
            st.push(i);
        }
        return res;
    }
};

⚡ View Alternative Approaches with Code and Analysis

📊 2️⃣ Forward Traversal Stack

💡 Algorithm Steps:

Build frequency map for all elements in the array.
Traverse array from left to right using stack to track indices.
For each element check if its frequency is greater than stack top frequency.
Pop stack and assign current element as next greater frequency element.

class Solution {
public:
    vector<int> nextFreqGreater(vector<int>& arr) {
        unordered_map<int, int> freq;
        for (int x : arr) freq[x]++;
        vector<int> res(arr.size(), -1);
        stack<int> st;
        for (int i = 0; i < arr.size(); i++) {
            while (!st.empty() && freq[arr[i]] > freq[arr[st.top()]]) {
                res[st.top()] = arr[i];
                st.pop();
            }
            st.push(i);
        }
        return res;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n) - Single pass with stack operations
Auxiliary Space: 💾 O(n) - Stack and frequency map storage

✅ Why This Approach?

Natural left to right processing
Clear monotonic stack pattern
Easy to understand and debug

📊 3️⃣ Pair-Based Stack Tracking

💡 Algorithm Steps:

Create frequency map and store element-frequency pairs in stack.
Process array from right to left maintaining decreasing frequency order.
Pop all elements with frequency less than or equal to current element.
Top of stack gives next greater frequency element for current position.

class Solution {
public:
    vector<int> nextFreqGreater(vector<int>& arr) {
        unordered_map<int, int> freq;
        for (int x : arr) freq[x]++;
        vector<int> res(arr.size(), -1);
        stack<pair<int, int>> st;
        for (int i = arr.size() - 1; i >= 0; i--) {
            while (!st.empty() && st.top().second <= freq[arr[i]]) st.pop();
            if (!st.empty()) res[i] = st.top().first;
            st.push({arr[i], freq[arr[i]]});
        }
        return res;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n) - Linear time traversal
Auxiliary Space: 💾 O(n) - Stack with pairs and map

✅ Why This Approach?

Stores both element and frequency together
Avoids repeated map lookups during comparison
More cache-friendly for large datasets

📊 4️⃣ Optimized Map Lookup

💡 Algorithm Steps:

Precompute frequencies and store in map for quick access.
Use stack to maintain indices in order of processing.
Compare frequencies directly using array indices stored in stack.
Update result array when greater frequency element is found.

class Solution {
public:
    vector<int> nextFreqGreater(vector<int>& arr) {
        unordered_map<int, int> freq;
        for (int x : arr) freq[x]++;
        int n = arr.size();
        vector<int> res(n, -1);
        stack<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && freq[arr[st.top()]] < freq[arr[i]]) {
                res[st.top()] = arr[i];
                st.pop();
            }
            st.push(i);
        }
        return res;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n) - Each element processed once
Auxiliary Space: 💾 O(n) - Stack and map storage

✅ Why This Approach?

Minimal code with optimal performance
Standard monotonic stack implementation
Efficient for competitive programming

🆚 🔍 Comparison of Approaches

🚀 Approach

⏱️ Time Complexity

💾 Space Complexity

✅ Pros

⚠️ Cons

🏷️ Backward Traversal

🟢 O(n)

🟡 O(n)

🚀 Right to left intuition

🔧 Less common pattern

🔍 Forward Traversal

🟢 O(n)

🟡 O(n)

📖 Standard stack approach

💾 Same space as others

📊 Pair-Based Stack

🟢 O(n)

🟡 O(n)

🎯 Reduces map lookups

🐌 Extra pair storage overhead

🔄 Optimized Lookup

🟢 O(n)

🟡 O(n)

⭐ Clean minimal code

🔧 Similar to forward traversal

🏆 Best Choice Recommendation

🎯 Scenario

🎖️ Recommended Approach

🔥 Performance Rating

🏅 Optimal performance needed

🥇 Backward Traversal

★★★★★

📖 Readability priority

🥈 Forward Traversal

★★★★★

🔧 Cache optimization

🥉 Pair-Based Stack

★★★★☆

🎯 Interview/Competitive

🏅 Optimized Lookup

★★★★★

☕ Code (Java)

class Solution {
    public ArrayList<Integer> nextFreqGreater(int[] arr) {
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int x : arr) freq.put(x, freq.getOrDefault(x, 0) + 1);
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) res.add(-1);
        Stack<Integer> st = new Stack<>();
        for (int i = arr.length - 1; i >= 0; i--) {
            while (!st.isEmpty() && freq.get(arr[st.peek()]) <= freq.get(arr[i])) st.pop();
            if (!st.isEmpty()) res.set(i, arr[st.peek()]);
            st.push(i);
        }
        return res;
    }
}

🐍 Code (Python)

class Solution:
    def nextFreqGreater(self, arr):
        freq = {}
        for x in arr: freq[x] = freq.get(x, 0) + 1
        res = [-1] * len(arr)
        st = []
        for i in range(len(arr) - 1, -1, -1):
            while st and freq[arr[st[-1]]] <= freq[arr[i]]: st.pop()
            if st: res[i] = arr[st[-1]]
            st.append(i)
        return res

🧠 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

📍Visitor Count

Previous17. Expression Contains Redundant Bracket or Not NextJuly 2024 GFG SOLUTION

Last updated 8 minutes ago

hashtag🧩 Problem Description

hashtag📘 Examples

hashtagExample 1

hashtagExample 2

hashtag🔒 Constraints

hashtag✅ My Approach

hashtagFrequency Map + Monotonic Stack (Backward Traversal)

hashtag📝 Time and Auxiliary Space Complexity

hashtag🧑‍💻 Code (C++)

hashtag📊 2️⃣ Forward Traversal Stack

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 3️⃣ Pair-Based Stack Tracking

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 4️⃣ Optimized Map Lookup

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag🆚 🔍 Comparison of Approaches

hashtag🏆 Best Choice Recommendation

hashtag☕ Code (Java)

hashtag🐍 Code (Python)

hashtag🧠 Contribution and Support

hashtag📍Visitor Count

🧩 Problem Description

📘 Examples

Example 1

Example 2

🔒 Constraints

✅ My Approach

Frequency Map + Monotonic Stack (Backward Traversal)

📝 Time and Auxiliary Space Complexity

🧑‍💻 Code (C++)

📊 2️⃣ Forward Traversal Stack

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 3️⃣ Pair-Based Stack Tracking

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 4️⃣ Optimized Map Lookup

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

🆚 🔍 Comparison of Approaches

🏆 Best Choice Recommendation

☕ Code (Java)

🐍 Code (Python)

🧠 Contribution and Support

📍Visitor Count