#2780

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Minimum Index of a Valid Split

Find the minimum index to split an array such that both subarrays have the same dominant element.

Problem Statement

You are given a 0-indexed integer array nums of length n. The array contains exactly one dominant element, which means one element occurs more than half the times in the array.

You are to split the array at some index i into two subarrays nums[0,...,i] and nums[i+1,...,n-1], such that both subarrays have the same dominant element as the original array. Your goal is to find the smallest valid index i, or return -1 if no valid split exists.

Examples

Example 1

Input: nums = [1,2,2,2]

Output: 2

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

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

It can be shown that there is no valid split.

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 109
nums has exactly one dominant element.

Solution Approach

Find the Dominant Element

First, scan the entire array using a hashmap to count the frequency of each element. The element with a frequency greater than half the array length is identified as the dominant element.

Use Prefix Sum to Track Frequency

As you traverse the array to find a valid split, maintain a running frequency count of the dominant element in the left subarray. This allows you to compare it with the frequency in the right subarray at each potential split.

Check Validity of the Split

For each index i, verify that the frequency of the dominant element in the left subarray (nums[0,...,i]) satisfies the condition, and check if the right subarray (nums[i+1,...,n-1]) also has the same dominant element.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

The time complexity of the solution is O(N) because we scan the array once to find the dominant element and once more to check each possible split. The space complexity is O(1) since we only use a constant amount of extra space for frequency counts and calculations.

What Interviewers Usually Probe

Can the candidate handle array scanning efficiently with hashmap lookups?
Does the candidate identify the importance of maintaining frequency counts for the dominant element?
How well does the candidate handle edge cases like when no valid split exists?

Common Pitfalls or Variants

Common pitfalls

Not tracking frequencies accurately across the split.
Overcomplicating the solution with unnecessary data structures.
Failing to recognize when no valid split is possible and returning an incorrect result.

Follow-up variants

What if the dominant element appears at the beginning or end of the array?
How would the solution change if there were multiple dominant elements?
What if the array was sorted? Does it affect the solution?

FAQ

What is the minimum index of a valid split in the Minimum Index of a Valid Split problem?

The minimum index is the smallest index i where the array can be split into two subarrays with the same dominant element. If no valid split exists, the result is -1.

How do I identify the dominant element in an array?

The dominant element occurs more than half the time in the array. You can identify it by counting the frequency of each element using a hashmap.

What is the time complexity of the Minimum Index of a Valid Split solution?

The time complexity is O(N) because the array is scanned twice: once to find the dominant element and once to check each potential split.

Can the solution handle arrays with no valid splits?

Yes, the solution returns -1 when no valid split exists where both subarrays have the same dominant element.

What happens if the dominant element appears at the start or end of the array?

The solution will still correctly identify the split point, as it checks all potential split indices and verifies the frequency of the dominant element in both subarrays.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def minimumIndex(self, nums: List[int]) -> int:
        x, cnt = Counter(nums).most_common(1)[0]
        cur = 0
        for i, v in enumerate(nums, 1):
            if v == x:
                cur += 1
                if cur * 2 > i and (cnt - cur) * 2 > len(nums) - i:
                    return i - 1
        return -1

Continue Practicing

#2784 check if array is good #2766 relocate marbles #2747 count zero request servers