Minimum Index of a Valid Split

Leetcode Problem:

• Minimum Index of a Valid Split

Summary

• Finding the minimum index of a valid split in an array where more than half of the elements have the same value.

Approach

• The approach used is to iterate over the array and maintain two maps, left and right, to store the count of each number
• We then iterate over the array again, pushing the current number to the right map and popping it from the left map
• If the count of the current number in both maps is more than half of the remaining elements, we return the current index
• If no valid split is found, we return -1.

Complexity

• O(n log n) due to the use of maps and the nested loop structure

Explanation

• The solution uses two maps, left and right, to store the count of each number in the array
• We iterate over the array twice, once to populate the maps and once to find the valid split
• In the first iteration, we push the current number to the right map and pop it from the left map
• In the second iteration, we check if the count of the current number in both maps is more than half of the remaining elements
• If it is, we return the current index
• If not, we continue to the next iteration
• If no valid split is found, we return -1.

Solution Code:

struct _node{
    int num;
    int cnt;
};

struct _map{
    vector<_node> m[10000];
    void push(int num){
        int idx = num % 10000;
        for(int i = 0 ; i < m[idx].size(); i++){
            if(m[idx][i].num == num){
                m[idx][i].cnt++;
                return;
            }
        }
        m[idx].push_back({num, 1});
    }
    int getCnt(int num){
        int idx = num % 10000;
        for(int i = 0 ; i < m[idx].size(); i++){
            if(m[idx][i].num == num){
                return m[idx][i].cnt;
            }
        }
        return -1;
    }
    void pop(int num){
        int idx = num% 10000;
        for(int i = 0 ; i < m[idx].size(); i++){
            if(m[idx][i].num == num){
                m[idx][i].cnt--;
                if(m[idx][i].cnt == 0){
                    m[idx][i] = m[idx][m[idx].size() - 1];
                    m[idx].pop_back();
                }
            }
        }
    }
};

class Solution {
public:
    _map left;
    _map right;
    int minimumIndex(vector& nums) {
        for(int i = 0 ; i < nums.size(); i++){
            right.push(nums[nums.size() - i - 1]);
        }
        for(int i = 0 ; i < nums.size(); i++){
            left.push(nums[i]);
            right.pop(nums[i]);
            int n = left.getCnt(nums[i]);
            if(n * 2 <= (i + 1)){
                continue;
            }
            n = right.getCnt(nums[i]);
            if(n == -1) continue;
            if((n * 2) > (nums.size() - i - 1)){
                return i;
            }
        }
        return -1;
    }
};