Minimum Index of a Valid Split - Solution & Explanation
Problem Statement
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.
The solution involves identifying the dominant element with a frequency count and then using prefix and suffix counts to determine the valid split location.
Complexity
Time Complexity: O(n), where n is the size of the array as we iterate over the array twice.
Space Complexity: O(n), due to the space used by the frequency array.
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.
This approach immediately calculates the requirement as it receives the inputs, reducing extra iterations over the dataset.
Complexity
Time Complexity: O(n), processing each input once.
Space Complexity: O(1), no extra space except counters.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Two-Pass with Prefix Counts | Time Complexity: O(n), where n is the size of the array as we iterate over the array twice. |
| Approach 2: Single Pass with Dynamic Count Update | Time Complexity: O(n), processing each input once. |
| Default Approach | — |
Detailed 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 |
Video Solution
Minimum Index of a Valid Split - Leetcode 2780 - Python • NeetCodeIO • 7,601 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Index of a Valid Split easy or hard?
Minimum Index of a Valid Split Python/Java solution
How to solve Minimum Index of a Valid Split in O(n)?
What is the best approach for Minimum Index of a Valid Split?
Is Minimum Index of a Valid Split asked at Google/Amazon/Meta?
What data structure is used in Minimum Index of a Valid Split?
What is the time complexity of Minimum Index of a Valid Split?
Ready to solve this problem?
Practice Minimum Index of a Valid Split with our built-in code editor and test cases.
Practice on FleetCode