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