⚡Flashcard Drill➔
NeetCode #110LC-2780MediumArrays & Hashing
← Back to All Problems

#110 · #2780 · Minimum Index of a Valid Split(合法分割的最小下标)

📌 Problem Statement & Constraints

An element is dominant if it appears more than half the time in an array. Given nums with a dominant element, find the minimum index i such that the dominant element is still dominant in both nums[0..i] and nums[i+1..n-1]. Return -1 if no such split exists. Constraints: 1 <= nums.length <= 10^5.

💡 Core Algorithmic Approaches

  1. First identify the dominant element and its total count.
  2. Sweep the split point from left to right, maintaining how many dominant elements have appeared in the left part.
  3. The left part is valid when left_count * 2 > left_length; the right part is valid when (total - left_count) * 2 > right_length.
  4. Return the first index satisfying both, which is the minimum by construction. Note the split must leave both parts non-empty, so i runs to n - 2.

💻 Benchmark Python3 Implementation

class Solution:
    def minimumIndex(self, nums: List[int]) -> int:
        from collections import Counter
        total = Counter(nums)
        dom = max(total, key=total.get)     # dominant element
        n = len(nums)
        left = 0
        for i in range(n - 1):             # right part must be non-empty
            if nums[i] == dom:
                left += 1
            right = total[dom] - left
            if left * 2 > i + 1 and right * 2 > (n - i - 1):
                return i
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass to count, one pass to scan the split points.
💾 Space Complexity
O(n) for the counter.

⚠️ Interview Pitfalls & Follow-ups

  • Using >= for the majority test: dominance is strictly more than half, so the comparison must be * 2 >.
  • Forgetting that the right part is nums[i+1..n-1]: its length is n - i - 1, not n - i.
  • Allowing i == n - 1: the right part would be empty, which is not a valid split.
  • Assuming the dominant element of the whole array is dominant in both halves: that is exactly the condition being tested, so it must be verified for each split.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems