Minimum Index of a Valid Split
MedPrompt
An element x of an integer array arr of length m is dominant if more than half the elements of arr have a value of x.
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through every possible split index i. For each split, it independently calculates the dominant element for the left subarray nums[0...i] and the right subarray nums[i+1...n-1]. If both subarrays have a dominant element and they are the same, the index i is a valid split. The first such index found is the minimum.
Algorithm
- Loop for
ifrom0tonums.length - 2. - Define the left subarray from index
0toi. - Find the dominant element
dom_leftof the left subarray. This involves:- Creating a frequency map for elements in
nums[0...i]. - Checking if any element count
csatisfiesc * 2 > (i + 1).
- Creating a frequency map for elements in
- Define the right subarray from index
i + 1ton - 1. - Find the dominant element
dom_rightof the right subarray. This involves:- Creating a frequency map for elements in
nums[i+1...n-1]. - Checking if any element count
csatisfiesc * 2 > (n - 1 - i).
- Creating a frequency map for elements in
- If
dom_leftanddom_rightboth exist anddom_left == dom_right, returni. - If the loop finishes, return
-1.
Walkthrough
The algorithm iterates with an outer loop for i from 0 to n-2. Inside the loop, two helper functions are used: one to find the dominant element of the left part (nums[0...i]) and one for the right part (nums[i+1...n-1]). Each helper function would typically use a frequency map (like a HashMap) to count element occurrences within its given subarray range. It then iterates through the map to see if any element's count is more than half the subarray's length. If both helper functions return a dominant element and these elements are equal, we have found a valid split. Since we are iterating i from the beginning, the first valid split found is the minimum, so we return i. If the loop completes without finding any valid split, it means none exist, and we return -1.
import java.util.List;import java.util.Map;import java.util.HashMap; class Solution { // Helper to find dominant element in a subarray range private int findDominant(List<Integer> nums, int start, int end) { if (start > end) { return -1; // Empty subarray } Map<Integer, Integer> counts = new HashMap<>(); for (int i = start; i <= end; i++) { counts.put(nums.get(i), counts.getOrDefault(nums.get(i), 0) + 1); } int len = end - start + 1; for (Map.Entry<Integer, Integer> entry : counts.entrySet()) { if (entry.getValue() * 2 > len) { return entry.getKey(); } } return -1; // No dominant element } public int minimumIndex(List<Integer> nums) { int n = nums.size(); for (int i = 0; i < n - 1; i++) { int dom_left = findDominant(nums, 0, i); int dom_right = findDominant(nums, i + 1, n - 1); if (dom_left != -1 && dom_left == dom_right) { return i; } } return -1; }}Complexity
Time
O(n^2). The outer loop runs `n-1` times. Inside the loop, `findDominant` for the left part takes `O(i)` time and for the right part takes `O(n-i)` time. The total time for one iteration is `O(i + n - i) = O(n)`. Thus, the overall complexity is `O(n * n) = O(n^2)`.
Space
O(n). In each iteration, two HashMaps are created. The combined size of these maps can be up to O(n) in the worst case (when all elements are unique).
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem without relying on the pre-condition that the whole array has a dominant element.
Cons
Highly inefficient due to repeated calculations. The frequency of elements is recounted in every iteration.
Fails to leverage the crucial problem constraint that
numshas a dominant element, leading to unnecessary work.
Solutions
Solution
class Solution {public int minimumIndex(List<Integer> nums) { int x = 0, cnt = 0; Map<Integer, Integer> freq = new HashMap<>(); for (int v : nums) { int t = freq.merge(v, 1, Integer : : sum); if (cnt < t) { cnt = t; x = v; } } int cur = 0; for (int i = 1; i <= nums.size(); ++i) { if (nums.get(i - 1) == x) { ++cur; if (cur * 2 > i && (cnt - cur) * 2 > nums.size() - i) { return i - 1; } } } return -1; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.