Minimum Index of a Valid Split
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
2Splitting at index 2 gives [1,2,2] and [2], and 2 is dominant in both arrays; this is the minimum valid split index.
Example 2
Input
nums = [2,1,3,1,1,1,7,1,2,1]Output
4Splitting at index 4 gives [2,1,3,1,1] and [1,7,1,2,1], and 1 is dominant in both arrays; this is the minimum valid split index.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- nums has exactly one dominant element.
Asked at 3 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.