Minimum Index of a Valid Split solution and explanation
Google
9 more videos on this problem
Minimum Index of a Valid Split - Leetcode 2780 - PythonNeetCodeIO · 21:28 · 7K views
Minimum Index of a Valid Split | Leetcode 2780Techdose · 16:16 · 4K views
2780. Minimum Index of a Valid SplitAyush Rao · 6:03 · 461 views
2780. Minimum Index of a Valid Split (Leetcode Medium)Programming Live with Larry · 12:33 · 350 views
Daily Leetcode #1822: Mar 27, 2025 - 2780. Minimum Index of a Valid SplitProgramming Live with Larry · 9:28 · 303 views
LeetCode 2780 Minimum Index of a Valid Split | Moore Voting AlgorithmCode Harmony · 15:58 · 117 views
Leetcode 2780: Minimum Index of a Valid Split | Python Solution Explained Step-by-StepStatLearn Tech · 11:38 · 92 views
Cracking Minimum Index of a Valid Split Challenge | Boyer-Moore Voting in Action | LeetCode 2780vanAmsen · 6:12 · 43 views
2780. Minimum Index of a Valid Split | 2 Approaches Explained | Leetcode Daily ChallengeAlgoDuo · 19:34 · 34 views
2780. Minimum Index of a Valid Split | Leetcode Daily - PythonLeetcode Daily · 16:32 · 33 views
The problem
An element x of an integer array arr of length m is dominant if freq(x) * 2 > m, where freq(x) is the number of occurrences of x in arr. Note that this definition implies that arr can have at most one dominant element.
You are given a 0-indexed integer array nums of length n with one dominant element.
You can split nums at an index i into two arrays nums[0, ..., i] and nums[i + 1, ..., n - 1], but the split is only valid if:
0 <= i < n - 1nums[0, ..., i], andnums[i + 1, ..., n - 1]have the same dominant element.
Here, nums[i, ..., j] denotes the subarray of nums starting at index i and ending at index j, both ends being inclusive. Particularly, if j < i then nums[i, ..., j] denotes an empty subarray.
Return the minimum index of a valid split. If no valid split exists, return -1.
Example 1:
Input: nums = [1,2,2,2] Output: 2 Explanation: We can split the array at index 2 to obtain arrays [1,2,2] and [2]. In array [1,2,2], element 2 is dominant since it occurs twice in the array and 2 * 2 > 3. In array [2], element 2 is dominant since it occurs once in the array and 1 * 2 > 1. Both [1,2,2] and [2] have the same dominant element as nums, so this is a valid split. It can be shown that index 2 is the minimum index of a valid split.
Example 2:
Input: nums = [2,1,3,1,1,1,7,1,2,1] Output: 4 Explanation: We can split the array at index 4 to obtain arrays [2,1,3,1,1] and [1,7,1,2,1]. In array [2,1,3,1,1], element 1 is dominant since it occurs thrice in the array and 3 * 2 > 5. In array [1,7,1,2,1], element 1 is dominant since it occurs thrice in the array and 3 * 2 > 5. Both [2,1,3,1,1] and [1,7,1,2,1] have the same dominant element as nums, so this is a valid split. It can be shown that index 4 is the minimum index of a valid split.
Example 3:
Input: nums = [3,3,3,3,7,2,2] Output: -1 Explanation: It can be shown that there is no valid split.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109numshas exactly one dominant element.
Approach overview
Problem Overview: Given an integer array, find the smallest index i where splitting the array into [0..i] and [i+1..n-1] results in both parts having the same dominant element (an element that appears more than half of the subarray length). If no such index exists, return -1.
The key observation: if a valid split exists, the dominant element of both partitions must also be the dominant element of the entire array. This reduces the problem to tracking the frequency of that single value while scanning possible split points.
Approach 1: Two-Pass with Prefix Counts (Time: O(n), Space: O(n))
First compute the total frequency of each value using a hash map. The element with frequency greater than n / 2 becomes the global dominant element. During a second pass, iterate through the array and maintain a running count of this dominant value in the prefix. At index i, compute the prefix length i + 1 and suffix length n - i - 1. A split is valid if the dominant element appears more than half in both partitions: leftCount * 2 > prefixLen and (totalCount - leftCount) * 2 > suffixLen. The first index satisfying both conditions is the answer.
This approach is straightforward and easy to reason about because the global counts are known before evaluating splits. It relies on constant-time hash lookups and a linear scan. Problems involving frequency tracking like this often rely on hash table counting patterns and sequential iteration over an array.
Approach 2: Single Pass with Dynamic Count Update (Time: O(n), Space: O(1) or O(n))
The same logic can be implemented more compactly by identifying the dominant element first, then scanning the array once while dynamically updating counts. Once the dominant value and its total frequency are known, iterate from left to right and update the prefix frequency each step. For every index, recompute whether the prefix and suffix still satisfy the dominance condition using simple arithmetic comparisons.
The advantage is reduced bookkeeping and cleaner state updates during traversal. Only the running prefix count and remaining suffix count are required. This keeps the algorithm strictly linear and avoids storing additional prefix arrays. The method still relies on counting frequency relationships rather than sorting, though conceptually the dominance rule resembles majority-element reasoning sometimes discussed alongside sorting or selection problems.
Recommended for interviews: The single-pass counting strategy after identifying the dominant element is what most interviewers expect. It demonstrates that you recognized the key insight: a valid split must share the same global dominant value. Explaining the two-pass version first is still useful—it shows you understand the frequency conditions clearly before optimizing the implementation.
Approach 1: Approach 1: Two-Pass with Prefix Counts
This approach involves using a two-pass method where we first determine the dominant element, and then use prefix counts to identify the minimum valid split index.
def find_dominant(nums):
freq = {}
dominant = nums[0]
max_freq = 0
for num in nums:
freq[num] = freq.get(num, 0) + 1
if freq[num] > max_freq:
max_freq = freq[num]
dominant = num
return dominant
def minimum_valid_split(nums):
n = len(nums)
dominant = find_dominant(nums)
left_count, right_count = 0, 0
for num in nums:
if num == dominant:
right_count += 1
for i in range(n - 1):
if nums[i] == dominant:
left_count += 1
right_count -= 1
if left_count * 2 > (i + 1) and right_count * 2 > (n - i - 1):
return i
return -1
nums = [2,1,3,1,1,1,7,1,2,1]
index = minimum_valid_split(nums)
print(index)import java.util.HashMap;
import java.util.Map;
public class SplitIndex {
public static int findDominant(int[] nums) {
Map<Integer, Integer> freq = new HashMap<>();
int dominant = nums[0], maxFreq = 0;
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
if (freq.get(num) > maxFreq) {
maxFreq = freq.get(num);
dominant = num;
}
}
return dominant;
}
public static int minimumValidSplit(int[] nums) {
int n = nums.length;
int dominant = findDominant(nums);
int leftCount = 0, rightCount = 0;
for (int num : nums) {
if (num == dominant) rightCount++;
}
for (int i = 0; i < n - 1; ++i) {
if (nums[i] == dominant) {
leftCount++;
rightCount--;
}
if (leftCount * 2 > i + 1 && rightCount * 2 > n - i - 1) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] nums = {2,1,3,1,1,1,7,1,2,1};
int index = minimumValidSplit(nums);
System.out.println(index);
}
}#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int findDominant(const vector<int>& nums) {
unordered_map<int, int> freq;
int dominant = nums[0], maxFreq = 0;
for (int num : nums) {
freq[num]++;
if (freq[num] > maxFreq) {
maxFreq = freq[num];
dominant = num;
}
}
return dominant;
}
int minimumValidSplit(vector<int>& nums) {
int n = nums.size();
int dominant = findDominant(nums);
int leftCount = 0, rightCount = 0;
for (int num : nums) {
if (num == dominant) rightCount++;
}
for (int i = 0; i < n - 1; ++i) {
if (nums[i] == dominant) {
leftCount++;
rightCount--;
}
if (leftCount * 2 > i + 1 && rightCount * 2 > n - i - 1) {
return i;
}
}
return -1;
}
int main() {
vector<int> nums = {2,1,3,1,1,1,7,1,2,1};
int index = minimumValidSplit(nums);
cout << index << endl;
return 0;
}function findDominant(nums) {
const freq = {};
let dominant = nums[0], maxFreq = 0;
for (const num of nums) {
freq[num] = (freq[num] || 0) + 1;
if (freq[num] > maxFreq) {
maxFreq = freq[num];
dominant = num;
}
}
return dominant;
}
function minimumValidSplit(nums) {
const n = nums.length;
const dominant = findDominant(nums);
let leftCount = 0, rightCount = 0;
nums.forEach(num => {
if (num === dominant) rightCount++;
});
for (let i = 0; i < n - 1; i++) {
if (nums[i] === dominant) {
leftCount++;
rightCount--;
}
if (leftCount * 2 > i + 1 && rightCount * 2 > n - i - 1) {
return i;
}
}
return -1;
}
const nums = [2,1,3,1,1,1,7,1,2,1];
const index = minimumValidSplit(nums);
console.log(index);#include <stdio.h>
#include <stdlib.h>
int findDominant(int* nums, int n) {
int* freq = (int*)calloc(n, sizeof(int));
int dominant = nums[0], maxFreq = 1;
for (int i = 0; i < n; ++i) {
freq[nums[i]]++;
if (freq[nums[i]] > maxFreq) {
maxFreq = freq[nums[i]];
dominant = nums[i];
}
}
free(freq);
return dominant;
}
int minimumValidSplit(int* nums, int n) {
int dominant = findDominant(nums, n);
int leftCount = 0, rightCount = 0;
for (int i = 0; i < n; ++i) {
if (nums[i] == dominant) rightCount++;
}
for (int i = 0; i < n - 1; ++i) {
if (nums[i] == dominant) {
leftCount++;
rightCount--;
}
if (leftCount * 2 > i + 1 && rightCount * 2 > n - i - 1) {
return i;
}
}
return -1;
}
int main() {
int nums[] = {2,1,3,1,1,1,7,1,2,1};
int n = sizeof(nums) / sizeof(nums[0]);
int index = minimumValidSplit(nums, n);
printf("%d\n", index);
return 0;
}using System;
using System.Collections.Generic;
class SplitIndex {
public static int FindDominant(int[] nums) {
var freq = new Dictionary<int, int>();
int dominant = nums[0], maxFreq = 0;
foreach (int num in nums) {
if (!freq.ContainsKey(num)) {
freq[num] = 0;
}
freq[num]++;
if (freq[num] > maxFreq) {
maxFreq = freq[num];
dominant = num;
}
}
return dominant;
}
public static int MinimumValidSplit(int[] nums) {
int n = nums.Length;
int dominant = FindDominant(nums);
int leftCount = 0, rightCount = 0;
foreach (int num in nums) {
if (num == dominant) rightCount++;
}
for (int i = 0; i < n - 1; i++) {
if (nums[i] == dominant) {
leftCount++;
rightCount--;
}
if (leftCount * 2 > i + 1 && rightCount * 2 > n - i - 1) {
return i;
}
}
return -1;
}
public static void Main() {
int[] nums = {2,1,3,1,1,1,7,1,2,1};
int index = MinimumValidSplit(nums);
Console.WriteLine(index);
}
}The Python solution uses a dictionary to track counts and compute prefix balance for the dominant element to find the valid split.
Time Complexity: O(n), required for traversing the list twice.
Space Complexity: O(n), required for the frequency dictionary.
Approach 2: Approach 2: Single Pass with Dynamic Count Update
This approach uses a dynamic update of dominant element counts on both sides as we iterate through the array to determine valid split indices efficiently in a single pass.
def minimum_valid_split(nums):
freq = {}
dominant = nums[0]
max_freq = 0
for num in nums:
freq[num] = freq.get(num, 0) + 1
if freq[num] > max_freq:
max_freq = freq[num]
dominant = num
left_count = 0
right_count = max_freq
for i in range(len(nums) - 1):
if nums[i] == dominant:
left_count += 1
right_count -= 1
if left_count * 2 > (i + 1) and right_count * 2 > (len(nums) - i - 1):
return i
return -1
nums = [2,1,3,1,1,1,7,1,2,1]
index = minimum_valid_split(nums)
print(index)import java.util.HashMap;
import java.util.Map;
public class SplitIndex {
public static int minimumValidSplit(int[] nums) {
Map<Integer, Integer> freq = new HashMap<>();
int dominant = nums[0];
int maxFreq = 0;
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
if (freq.get(num) > maxFreq) {
maxFreq = freq.get(num);
dominant = num;
}
}
int leftCount = 0;
int rightCount = maxFreq;
for (int i = 0; i < nums.length - 1; ++i) {
if (nums[i] == dominant) {
leftCount++;
rightCount--;
}
if (leftCount * 2 > i + 1 && rightCount * 2 > nums.length - i - 1) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] nums = {2,1,3,1,1,1,7,1,2,1};
int index = minimumValidSplit(nums);
System.out.println(index);
}
}#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int minimumValidSplit(vector<int>& nums) {
unordered_map<int, int> freq;
int dominant = nums[0], maxFreq = 0;
for (int num : nums) {
freq[num]++;
if (freq[num] > maxFreq) {
maxFreq = freq[num];
dominant = num;
}
}
int leftCount = 0, rightCount = maxFreq;
for (int i = 0; i < nums.size() - 1; ++i) {
if (nums[i] == dominant) {
leftCount++;
rightCount--;
}
if (leftCount * 2 > i + 1 && rightCount * 2 > nums.size() - i - 1) {
return i;
}
}
return -1;
}
int main() {
vector<int> nums = {2,1,3,1,1,1,7,1,2,1};
int index = minimumValidSplit(nums);
cout << index << endl;
return 0;
}function minimumValidSplit(nums) {
const freq = {};
let dominant = nums[0], maxFreq = 0;
for (const num of nums) {
freq[num] = (freq[num] || 0) + 1;
if (freq[num] > maxFreq) {
maxFreq = freq[num];
dominant = num;
}
}
let leftCount = 0, rightCount = maxFreq;
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] === dominant) {
leftCount++;
rightCount--;
}
if (leftCount * 2 > i + 1 && rightCount * 2 > nums.length - i - 1) {
return i;
}
}
return -1;
}
const nums = [2,1,3,1,1,1,7,1,2,1];
const index = minimumValidSplit(nums);
console.log(index);#include <stdio.h>
int minimumValidSplit(int* nums, int n) {
int dominant = 0, maxFreq = 0, freq[n];
for (int i = 0; i < n; ++i) freq[i] = 0;
for (int i = 0; i < n; ++i) {
freq[nums[i]]++;
if (freq[nums[i]] > maxFreq) {
maxFreq = freq[nums[i]];
dominant = nums[i];
}
}
int leftCount = 0, rightCount = maxFreq;
for (int i = 0; i < n - 1; ++i) {
if (nums[i] == dominant) {
leftCount++;
rightCount--;
}
if (leftCount * 2 > i + 1 && rightCount * 2 > n - i - 1) {
return i;
}
}
return -1;
}
int main() {
int nums[] = {2,1,3,1,1,1,7,1,2,1};
int n = sizeof(nums) / sizeof(nums[0]);
int index = minimumValidSplit(nums, n);
printf("%d\n", index);
return 0;
}using System;
using System.Collections.Generic;
class SplitIndex {
public static int MinimumValidSplit(int[] nums) {
var freq = new Dictionary<int, int>();
int dominant = nums[0];
int maxFreq = 0;
foreach (int num in nums) {
if (!freq.ContainsKey(num)) freq[num] = 0;
freq[num]++;
if (freq[num] > maxFreq) {
maxFreq = freq[num];
dominant = num;
}
}
int leftCount = 0;
int rightCount = maxFreq;
for (int i = 0; i < nums.Length - 1; i++) {
if (nums[i] == dominant) {
leftCount++;
rightCount--;
}
if (leftCount * 2 > i + 1 && rightCount * 2 > nums.Length - i - 1) {
return i;
}
}
return -1;
}
public static void Main() {
int[] nums = {2,1,3,1,1,1,7,1,2,1};
int index = MinimumValidSplit(nums);
Console.WriteLine(index);
}
}In this Python solution, the elegant use of dictionary for frequency and dynamic update ensures a direct approach to identifying split indices.
Time Complexity: O(n), only one loop is needed.
Space Complexity: O(n), due to the dictionary required for frequencies.
Approach 3: Default Approach
function minimumIndex(nums: number[]): number {
let [x, cnt] = [0, 0];
const freq: Map<number, number> = new Map();
for (const v of nums) {
freq.set(v, (freq.get(v) ?? 0) + 1);
if (freq.get(v)! > cnt) {
[x, cnt] = [v, freq.get(v)!];
}
}
let cur = 0;
for (let i = 1; i <= nums.length; ++i) {
if (nums[i - 1] === x) {
++cur;
if (cur * 2 > i && (cnt - cur) * 2 > nums.length - i) {
return i - 1;
}
}
}
return -1;
}func minimumIndex(nums []int) int {
x, cnt := 0, 0
freq := map[int]int{}
for _, v := range nums {
freq[v]++
if freq[v] > cnt {
x, cnt = v, freq[v]
}
}
cur := 0
for i, v := range nums {
i++
if v == x {
cur++
if cur*2 > i && (cnt-cur)*2 > len(nums)-i {
return i - 1
}
}
}
return -1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Two-Pass with Prefix Counts | Time Complexity: O(n), required for traversing the list twice. |
| Approach 2: Single Pass with Dynamic Count Update | Time Complexity: O(n), only one loop is needed. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass with Prefix Counts | O(n) | O(n) | When you want a clear and easy-to-debug solution using hash map frequency counts |
| Single Pass with Dynamic Count Update | O(n) | O(1)–O(n) | Optimal interview solution with minimal state and a single linear traversal |
Frequently asked questions
Is Minimum Index of a Valid Split easy or hard?
Minimum Index of a Valid Split is rated Medium difficulty because the logic depends on recognizing the dominant-element property of the entire array. Once that insight is understood, the implementation becomes a straightforward linear scan with frequency checks.
Minimum Index of a Valid Split Python/Java solution
Python and Java implementations follow the same logic: compute the dominant element frequency, iterate through the array, update prefix counts, and validate the dominance condition for both partitions. Each implementation runs in O(n) time and requires only simple counters and array traversal.
How to solve Minimum Index of a Valid Split in O(n)?
First determine the dominant element of the entire array by counting frequencies. Then iterate through the array and maintain the number of times this element appears in the prefix. For each index, check if the prefix and suffix both satisfy the dominance condition using simple arithmetic comparisons. The first valid index is returned.
What is the best approach for Minimum Index of a Valid Split?
The best approach identifies the array's dominant element and then scans the array while tracking its frequency on both sides of a potential split. By checking whether the element remains dominant in both partitions, you can find the smallest valid index in O(n) time. This linear scan with prefix counting is the standard optimal solution.
Is Minimum Index of a Valid Split asked at Google/Amazon/Meta?
Dominant-element and frequency-based array problems frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact question may not always appear verbatim, the pattern of maintaining prefix counts and validating constraints during a linear scan is commonly tested.
What data structure is used in Minimum Index of a Valid Split?
The primary data structure is a hash table used to count element frequencies. After identifying the dominant value, the algorithm mainly relies on integer counters while iterating through the array.
What is the time complexity of Minimum Index of a Valid Split?
The optimal solution runs in O(n) time because the array is scanned at most twice—once to determine the dominant element and once to test split positions. Space complexity ranges from O(1) to O(n) depending on whether a hash map is used for counting frequencies.