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.

#2780

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

合法分割的最小下标

如果在长度为 m 的整数数组 arr 中超过一半的元素值为 x ，那么我们称 x 是支配元素。给你一个下标从 0 开始长度为 n 的整数数组 nums ，数据保证它含有一个支配元素。你需要在下标 i 处将 nums 分割成两个数组 nums[0, ..., i] 和 nums[i +…

数组哈希表排序

题目描述

如果在长度为 m 的整数数组 arr 中 超过一半 的元素值为 x，那么我们称 x 是 支配元素 。

给你一个下标从 0 开始长度为 n 的整数数组 nums ，数据保证它含有一个支配元素。

你需要在下标 i 处将 nums 分割成两个数组 nums[0, ..., i] 和 nums[i + 1, ..., n - 1] ，如果一个分割满足以下条件，我们称它是合法的：

0 <= i < n - 1
nums[0, ..., i] 和 nums[i + 1, ..., n - 1] 的支配元素相同。

这里， nums[i, ..., j] 表示 nums 的一个子数组，它开始于下标 i ，结束于下标 j ，两个端点都包含在子数组内。特别地，如果 j < i ，那么 nums[i, ..., j] 表示一个空数组。

请你返回一个 合法分割 的最小下标。如果合法分割不存在，返回 -1 。

示例 1：

输入：nums = [1,2,2,2]
输出：2
解释：我们将数组在下标 2 处分割，得到 [1,2,2] 和 [2] 。
数组 [1,2,2] 中，元素 2 是支配元素，因为它在数组中出现了 2 次，且 2 * 2 > 3 。
数组 [2] 中，元素 2 是支配元素，因为它在数组中出现了 1 次，且 1 * 2 > 1 。
两个数组 [1,2,2] 和 [2] 都有与 nums 一样的支配元素，所以这是一个合法分割。
下标 2 是合法分割中的最小下标。

示例 2：

输入：nums = [2,1,3,1,1,1,7,1,2,1]
输出：4
解释：我们将数组在下标 4 处分割，得到 [2,1,3,1,1] 和 [1,7,1,2,1] 。
数组 [2,1,3,1,1] 中，元素 1 是支配元素，因为它在数组中出现了 3 次，且 3 * 2 > 5 。
数组 [1,7,1,2,1] 中，元素 1 是支配元素，因为它在数组中出现了 3 次，且 3 * 2 > 5 。
两个数组 [2,1,3,1,1] 和 [1,7,1,2,1] 都有与 nums 一样的支配元素，所以这是一个合法分割。
下标 4 是所有合法分割中的最小下标。

示例 3：

输入：nums = [3,3,3,3,7,2,2]
输出：-1
解释：没有合法分割。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
nums 有且只有一个支配元素。

lightbulb

解题思路

方法一：哈希表

我们用哈希表统计每个元素出现的次数，然后找出出现次数最多的元素 $x$ ，即为支配元素。要使得分割后的两个数组中都有支配元素，且支配元素相同，那么支配元素一定是 $x$ 。

接下来，我们只需要遍历数组 $nums$ ，累加前缀中 $x$ 的出现次数 $cur$ ，并判断 $x$ 在后缀中出现的次数是否满足要求即可。如果满足要求，那么当前下标 $i$ 就是一个可行的分割下标，我们只需要选择所有可行分割下标中最小的那个即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

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

speed

复杂度分析

指标	值
时间	O(N)
空间	O(1)

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2784 检查数组是否是好的 #2766 重新放置石块 #2747 统计没有收到请求的服务器数目