27_Minimum_Index_of_a_Valid_Split.cpp

// 2780. Minimum Index of a Valid Split

// An element x of an integer array arr of length m is dominant if more than half the elements of arr have a value of x.

// 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.

// Example 1:

// Input: nums = [1,2,2,2]
// Output: 2
// Explanation: We can split the array at index 2 to obtain arrays [1,2,2] and [2].
// In array [1,2,2], element 2 is dominant since it occurs twice in the array and 2 * 2 > 3.
// In array [2], element 2 is dominant since it occurs once in the array and 1 * 2 > 1.
// Both [1,2,2] and [2] have the same dominant element as nums, so this is a valid split.
// It can be shown that index 2 is the minimum index of a valid split.
// Example 2:

// Input: nums = [2,1,3,1,1,1,7,1,2,1]
// Output: 4
// Explanation: We can split the array at index 4 to obtain arrays [2,1,3,1,1] and [1,7,1,2,1].
// In array [2,1,3,1,1], element 1 is dominant since it occurs thrice in the array and 3 * 2 > 5.
// In array [1,7,1,2,1], element 1 is dominant since it occurs thrice in the array and 3 * 2 > 5.
// Both [2,1,3,1,1] and [1,7,1,2,1] have the same dominant element as nums, so this is a valid split.
// It can be shown that index 4 is the minimum index of a valid split.
// Example 3:

// Input: nums = [3,3,3,3,7,2,2]
// Output: -1
// Explanation: It can be shown that there is no valid split.

// Constraints:

// 1 <= nums.length <= 105
// 1 <= nums[i] <= 109
// nums has exactly one dominant element

class Solution
{
public:
    int minimumIndex(vector<int> &nums)
    {
        unordered_map<int, int> freq;
        int dom = 0, count = 0, n = nums.size();

        for (int num : nums)
        {
            freq[num]++;
        }

        for (auto &[num, c] : freq)
        {
            if (c > n / 2)
            {
                dom = num;
                count = c;
                break;
            }
        }

        int leftCount = 0;
        for (int i = 0; i < n - 1; i++)
        {
            if (nums[i] == dom)
                leftCount++;
            int leftSize = i + 1;
            int rightSize = n - leftSize;
            int rightCount = count - leftCount;

            if (leftCount > leftSize / 2 && rightCount > rightSize / 2)
            {
                return i;
            }
        }

        return -1;
    }
};

/*
This solution finds the minimum index where we can split the array such that both parts have the same dominant element.

1. First, we count frequencies of all elements using an unordered_map
2. Find the dominant element (dom) and its total count in the array
3. Iterate through possible split points (0 to n-2):
 - Track count of dominant element in left part
 - Calculate sizes and counts for both parts
 - If dominant element is dominant in both parts, return current index
4. If no valid split found, return -1

Time Complexity: O(n) where n is length of input array
- O(n) for counting frequencies
- O(n) for finding dominant element
- O(n) for checking split points

Space Complexity: O(k) where k is number of unique elements
- Uses unordered_map to store element frequencies
*/