Prefix with Equivalent Frequencies - Amazon Top Interview Questions

                        Solution in C++ :

int solve(vector<int>& nums) {
    // we use two hashmaps one to keep the track of the frequecny of elements and one to keep the
    // track of the of the frequecny of frequencies.
    map<int, int> f, fc;
    int ans = 0;

    for (int i = 0; i < nums.size(); i++) {
        // if we have already inserted the element inside our prefix window
        // we first remove old frequency contribution
        // if there is only one  element with this frequency than after the frequency change there
        // will be no element remaining with this frequency so we remove it's existance
        if (f.find(nums[i]) != f.end() and fc[f[nums[i]]]-- == 1) {
            fc.erase(f[nums[i]]);
        }

        // now we increase the frequency of the element and also the frequency count of f[nums[i]]
        // afterwards.
        fc[++f[nums[i]]]++;

        // now checking if the window so far is valid.
        if (fc.size() == 2) {
            if (fc.find(1) != fc.end()) {
                if (fc[1] == 1) ans = max(ans, i + 1);
            }
            if (fc.begin()->first == fc.rbegin()->first - 1) {
                if (fc.rbegin()->second == 1) ans = max(ans, i + 1);
            }
        } else if (fc.size() == 1 and (fc.begin()->first == 1 or f.size() == 1)) {
            ans = max(ans, i + 1);
        }
    }
    return ans;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[] nums) {
        // 1234567 remove one of them
        // 1111111 remove one of them
        // 111 222 333 4 remove 4
        // 111 222 333 4444 remove one of 4
        Map<Integer, List<Integer>> window = new HashMap<>();
        Map<Integer, Integer> freq = new HashMap<>();

        int len = nums.length;
        if (len == 2) {
            return 2;
        }
        int res = 0;

        for (int i = 0; i < len; i++) {
            int n = nums[i];
            freq.put(n, freq.getOrDefault(n, 0) + 1);
            int f = freq.get(n);

            if (window.containsKey(f - 1)) {
                window.get(f - 1).remove(new Integer(n));
                if (window.get(f - 1).size() == 0) {
                    window.remove(f - 1);
                }
            }
            window.putIfAbsent(f, new ArrayList<Integer>());
            window.get(f).add(n);

            // if frequency of all the elements is 1
            if (window.size() == 1 && window.containsKey(1)) {
                res = i + 1;
                // if all the elements are same inside the prefix window
            } else if (window.size() == 1) {
                for (int key : window.keySet()) {
                    if (window.get(key).size() == 1) {
                        res = i + 1;
                    }
                }
            } else if (window.size() == 2) {
                int first = -1;
                int second = -1;
                for (int key : window.keySet()) {
                    if (first == -1) {
                        first = key;
                    } else {
                        second = key;
                    }
                }
                if (first + 1 == second && window.get(second).size() == 1) {
                    res = i + 1;
                } else if (second + 1 == first && window.get(first).size() == 1) {
                    res = i + 1;
                } else if (window.containsKey(1) && window.get(1).size() == 1) {
                    res = i + 1;
                }
            } else {
                continue;
            }
        }
        return res;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, nums):
        freq = dict()  # stores the amount of different counts
        counts = dict()  # stores the count of each number

        for i, num in enumerate(nums):
            old_c, new_c = counts.get(num, 0), counts.get(num, 0) + 1

            if old_c in freq:  # remove previous frequency
                freq[old_c] -= 1
                if freq[old_c] == 0:
                    del freq[old_c]

            counts[num] = new_c  # add the new frequency
            freq[new_c] = freq.get(new_c, 0) + 1

            if len(freq) == 1:
                for k, v in freq.items():
                    if v == 1 or k == 1:
                        res = i + 1

            if len(freq) == 2:
                tmp = [(k, v) for k, v in freq.items()]
                (f1, c1), (f2, c2) = tmp[0], tmp[1]
                if (f1 == 1 and c1 == 1) or (f2 == 1 and c2 == 1):
                    res = i + 1
                if c1 == 1 and f1 - 1 == f2 or c2 == 1 and f2 - 1 == f1:
                    res = i + 1
        return res