Minimum Index of a Valid Split

How it works

Since the problem guarantees a dominant element exists in the full array, we can first identify it using Boyer-Moore voting. This algorithm finds the majority element in O(n) time and O(1) space by maintaining a candidate and a counter.

Once we know the dominant element, we just need to track its count on each side as we scan through, checking if it remains dominant in both portions at each potential split.

Steps

1. Use Boyer-Moore voting to find the overall dominant element: maintain a candidate and increment/decrement a counter based on matches.
2. Count the total occurrences of this dominant element.
3. Scan through the array, tracking how many times the dominant element appears in the left portion.
4. At each index, check if 2 * leftCount > leftLength and 2 * rightCount > rightLength.
5. Return the first index satisfying both conditions, or -1 if none exists.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Confusing Majority with Most Frequent

The dominant element must appear more than half the time, not just be the most frequent. An element appearing exactly n/2 times is not dominant. The condition is strictly greater than, so always use count > length / 2 rather than >=.

Off-by-One Errors in Split Length Calculation

When splitting at index i, the left segment has length i + 1 and the right segment has length n - i - 1. Mixing up these lengths or using i instead of i + 1 for the left length leads to incorrect dominance checks and wrong answers.

Not Recognizing That Only the Global Dominant Can Work

A valid split requires the same element to dominate both halves. This element must also dominate the entire array. Checking all elements at each split point is wasteful; instead, identify the global dominant element first and only track its counts during the split search.

from typing import List

class Solution:
    def minimumIndex(self, nums: List[int]) -> int:
        majority = count = 0
        for num in nums:
            if count == 0:
                majority = num
            count += (1 if majority == num else -1)

        left_cnt, right_cnt = 0, nums.count(majority)

        for i in range(len(nums)):
            if nums[i] == majority:
                left_cnt += 1
                right_cnt -= 1

            left_len = i + 1
            right_len = len(nums) - i - 1

            if 2 * left_cnt > left_len and 2 * right_cnt > right_len:
                return i

        return -1

class Solution {
public:
    int minimumIndex(vector<int>& nums) {
        int majority = 0, count = 0;
        for (int num : nums) {
            if (count == 0) majority = num;
            count += (num == majority ? 1 : -1);
        }

        int leftCnt = 0, rightCnt = count_if(nums.begin(), nums.end(),
                                             [&](int x) { return x == majority; });

        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] == majority) {
                leftCnt++;
                rightCnt--;
            }

            int leftLen = i + 1;
            int rightLen = n - i - 1;

            if (2 * leftCnt > leftLen && 2 * rightCnt > rightLen) {
                return i;
            }
        }

        return -1;
    }
};