Minimum Index of a Valid Split — Problem & Solution
Minimum Index of a Valid Split solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Index of a Valid Split is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sorting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An element x is dominant in an array arr when it occurs more than half the time: 2 · freq(x) > arr.length. An array has at most one dominant element.
You are given an integer array nums (0-indexed) that is guaranteed to have a dominant element. Splitting at index i (0 <= i < n - 1) produces nums[0..i] and nums[i + 1..n - 1]; the split is valid if both parts have the same dominant element.
Return the minimum index of a valid split, or -1 if there is none.
Example 1
Input: nums = [1,2,2,2]
Output: 2
Explanation: Splitting after index 2 gives `[1,2,2]` and `[2]`, both dominated by 2. Splitting at 0 or 1 leaves a left part with no dominant element.
Example 2
Input: nums = [2,1,3,1,1,1,7,1,2,1]
Output: 4
Explanation: `[2,1,3,1,1]` and `[1,7,1,2,1]` are both dominated by 1.
Example 3
Input: nums = [3,3,3,3,7,2,2]
Output: -1
Explanation: Any left part dominated by 3 leaves too few 3s on the right.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^9nums has exactly one dominant element
Hints for Minimum Index of a Valid Split
Hint 1
If both halves share a dominant element
y, thenyoccurs more than half the time in the whole array — so it must be the array's own dominant element.Hint 2
Find that element
dand its total count first (a hash map, or Boyer–Moore voting).Hint 3
Scan the split point left to right, keeping how many copies of
dare on the left. The split atiis valid when2 · left > i + 1and2 · (total − left) > n − i − 1.
How to solve Minimum Index of a Valid Split
Only the array's dominant element d can dominate both halves: if y is more than half of each part, it is more than half of the whole. So count d once, then sweep the split point with a running prefix count of d.
Approach
- Find the dominant element
d(Boyer–Moore majority vote) and its total counttotal. - Sweep
ifrom 0 ton - 2, adding 1 toleftwhenevernums[i] == d. - Return the first
iwith2 · left > i + 1and2 · (total − left) > n − i − 1. - If no index qualifies, return −1.
Why it works
If both parts are dominated by y, then freq(y) > (i + 1)/2 + (n − i − 1)/2 = n/2, so y = d. Conversely the two inequalities say exactly that d is dominant on each side. The first index where they hold is the answer.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Recomputing each half's dominant element from scratch is O(n^2).
- The last valid split index is
n - 2; the right part must be non-empty. - Use strict inequalities — exactly half is not dominant.
Reference solution
Python
from typing import List
def minimumIndex(nums: List[int]) -> int:
d, votes = nums[0], 0
for v in nums:
if votes == 0:
d = v
votes += 1 if v == d else -1
total = nums.count(d)
n = len(nums)
left = 0
for i in range(n - 1):
if nums[i] == d:
left += 1
if 2 * left > i + 1 and 2 * (total - left) > n - i - 1:
return i
return -1Java
public static int minimumIndex(int[] nums) {
int n = nums.length;
int d = nums[0], votes = 0;
for (int v : nums) {
if (votes == 0) d = v;
votes += v == d ? 1 : -1;
}
int total = 0;
for (int v : nums) if (v == d) total++;
int left = 0;
for (int i = 0; i < n - 1; i++) {
if (nums[i] == d) left++;
if (2 * left > i + 1 && 2 * (total - left) > n - i - 1) return i;
}
return -1;
}C++
int minimumIndex(vector<int>& nums) {
int n = nums.size();
int d = nums[0], votes = 0;
for (int v : nums) {
if (votes == 0) d = v;
votes += v == d ? 1 : -1;
}
int total = 0;
for (int v : nums) if (v == d) total++;
int left = 0;
for (int i = 0; i < n - 1; i++) {
if (nums[i] == d) left++;
if (2 * left > i + 1 && 2 * (total - left) > n - i - 1) return i;
}
return -1;
}JavaScript
var minimumIndex = function(nums) {
var n = nums.length;
var d = nums[0], votes = 0;
for (var i = 0; i < n; i++) {
if (votes === 0) d = nums[i];
votes += nums[i] === d ? 1 : -1;
}
var total = 0;
for (var j = 0; j < n; j++) if (nums[j] === d) total++;
var left = 0;
for (var k = 0; k < n - 1; k++) {
if (nums[k] === d) left++;
if (2 * left > k + 1 && 2 * (total - left) > n - k - 1) return k;
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets