2780. Minimum Index of a Valid Split

An element x of an integer array arr of length m is dominant if freq(x) * 2 > m, where freq(x) is the number of occurrences of x in arr. Note that this definition implies that arr can have at most one dominant element.

You are given a 0-indexed integer array nums of length n with one dominant element.

You can split nums at an index i into two arrays nums[0, ..., i] and nums[i + 1, ..., n - 1], but the split is only valid if:

• 0 <= i < n - 1
• nums[0, ..., i], and nums[i + 1, ..., n - 1] have the same dominant element.

Here, nums[i, ..., j] denotes the subarray of nums starting at index i and ending at index j, both ends being inclusive. Particularly, if j < i then nums[i, ..., j] denotes an empty subarray.

Return the minimum index of a valid split. If no valid split exists, return -1.

class Solution {
public:
    int minimumIndex(vector<int>& nums) {
        vector<int> le(nums.size(), -1), ri(nums.size(), -1);
        unordered_map<int, int> fle, fri;
        for(int i = 0, best = 0; i < nums.size(); i++) {
            fle[nums[i]] += 1;
            if(fle[nums[i]] > fle[best]) best = nums[i];
            if(fle[best] * 2 > (i + 1)) le[i] = best;
        }
        for(int i = nums.size() - 1, best = 0; i >= 0; i--) {
            fri[nums[i]] += 1;
            if(fri[nums[i]] > fri[best]) best = nums[i];
            if(fri[best] * 2 > (nums.size() - i)) ri[i] = best;
        }
        for(int i = 0; i < nums.size() - 1; i++) {
            if(le[i] == -1) continue;
            if(le[i] == ri[i+1]) return i;
        }
        return -1;
    }
};