2780. Minimum Index of a Valid Split - Explanation

1. Brute Force

Intuition

A valid split requires that the same element is dominant in both the left and right subarrays. The dominant element must appear more than half the time in each part.

The straightforward approach is to try every possible split point and, for each one, count element frequencies in both halves. We then check if any element satisfies the dominance condition on both sides.

Algorithm

Iterate through each potential split index i from 0 to n-2.
For each split, build frequency maps for the left portion (0 to i) and right portion (i+1 to n-1).
For each element in the left map, check if its count exceeds half the left length AND its count in the right map exceeds half the right length.
Return the first index where both conditions are met.
If no valid split exists, return -1.

class Solution:
    def minimumIndex(self, nums: List[int]) -> int:
        n = len(nums)

        for i in range(n - 1):
            left_cnt = defaultdict(int)
            for l in range(i + 1):
                left_cnt[nums[l]] += 1

            right_cnt = defaultdict(int)
            for r in range(i + 1, n):
                right_cnt[nums[r]] += 1

            for num in left_cnt:
                if left_cnt[num] > (i + 1) // 2 and right_cnt[num] > (n - i - 1) // 2:
                    return i

        return -1

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Hash Map

Intuition

Instead of recounting from scratch at each split, we can maintain running counts. Start with all elements in the "right" map, then slide through the array moving one element at a time from right to left.

For each position, we only need to check if the current element is dominant in both parts. This works because if a valid split exists, the overall dominant element must be dominant on both sides.

Algorithm

Initialize a left frequency map (empty) and a right frequency map (containing all elements).
Iterate through each index i:
- Move nums[i] from right to left (increment left count, decrement right count).
- Check if nums[i] appears more than half the time in both the left segment (length i+1) and right segment (length n-i-1).
Return the first index where the condition holds.
Return -1 if no valid split is found.

class Solution:
    def minimumIndex(self, nums: List[int]) -> int:
        left = defaultdict(int)
        right = Counter(nums)

        for i in range(len(nums)):
            left[nums[i]] += 1
            right[nums[i]] -= 1

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

            if 2 * left[nums[i]] > left_len and 2 * right[nums[i]] > right_len:
                return i

        return -1

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Boyer-Moore Voting Algorithm

Intuition

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.

Algorithm

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

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

Time & Space Complexity

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

Common Pitfalls

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.