How does binary search help in solving this problem?

Binary search helps by narrowing down the range of possible answers (the earliest second) and checking if it's feasible to mark all indices at that time.

What happens if it's impossible to mark all indices?

If it's impossible to mark all indices, the answer should be -1, which can be detected by simulating the process and checking if all indices are marked within the given time.

What is the time complexity of the solution?

The time complexity is O(n log m), where n is the length of nums and m is the length of changeIndices. Binary search narrows the search space, and the simulation takes O(n) time.

How do we handle edge cases like missing indices in changeIndices?

Edge cases where an index is missing in changeIndices should be handled by checking if all elements in nums can be decremented to zero, and if not, returning -1.

Can this problem be solved without binary search?

It is possible to solve the problem without binary search, but binary search significantly reduces the time complexity compared to a brute force approach, making it more efficient.

#3048

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

标记所有下标的最早秒数 I

给你两个下标从 1 开始的整数数组 nums 和 changeIndices ，数组的长度分别为 n 和 m 。一开始， nums 中所有下标都是未标记的，你的任务是标记 nums 中所有下标。从第 1 秒到第 m 秒（包括第 m 秒），对于每一秒 s ，你可以执行以下操作之一：选…

数组二分查找

题目描述

给你两个下标从 1 开始的整数数组 nums 和 changeIndices ，数组的长度分别为 n 和 m 。

一开始，nums 中所有下标都是未标记的，你的任务是标记 nums 中所有下标。

从第 1 秒到第 m 秒（包括第 m 秒），对于每一秒 s ，你可以执行以下操作之一：

选择范围 [1, n] 中的一个下标 i ，并且将 nums[i] 减少 1 。
如果 nums[changeIndices[s]] 等于 0 ，标记下标 changeIndices[s] 。
什么也不做。

请你返回范围 [1, m] 中的一个整数，表示最优操作下，标记 nums 中所有下标的 最早秒数 ，如果无法标记所有下标，返回 -1 。

示例 1：

输入：nums = [2,2,0], changeIndices = [2,2,2,2,3,2,2,1]
输出：8
解释：这个例子中，我们总共有 8 秒。按照以下操作标记所有下标：
第 1 秒：选择下标 1 ，将 nums[1] 减少 1 。nums 变为 [1,2,0] 。
第 2 秒：选择下标 1 ，将 nums[1] 减少 1 。nums 变为 [0,2,0] 。
第 3 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [0,1,0] 。
第 4 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [0,0,0] 。
第 5 秒，标记 changeIndices[5] ，也就是标记下标 3 ，因为 nums[3] 等于 0 。
第 6 秒，标记 changeIndices[6] ，也就是标记下标 2 ，因为 nums[2] 等于 0 。
第 7 秒，什么也不做。
第 8 秒，标记 changeIndices[8] ，也就是标记下标 1 ，因为 nums[1] 等于 0 。
现在所有下标已被标记。
最早可以在第 8 秒标记所有下标。
所以答案是 8 。

示例 2：

输入：nums = [1,3], changeIndices = [1,1,1,2,1,1,1]
输出：6
解释：这个例子中，我们总共有 7 秒。按照以下操作标记所有下标：
第 1 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [1,2] 。
第 2 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [1,1] 。
第 3 秒：选择下标 2 ，将 nums[2] 减少 1 。nums 变为 [1,0] 。
第 4 秒：标记 changeIndices[4] ，也就是标记下标 2 ，因为 nums[2] 等于 0 。
第 5 秒：选择下标 1 ，将 nums[1] 减少 1 。nums 变为 [0,0] 。
第 6 秒：标记 changeIndices[6] ，也就是标记下标 1 ，因为 nums[1] 等于 0 。
现在所有下标已被标记。
最早可以在第 6 秒标记所有下标。
所以答案是 6 。

示例 3：

Input: nums = [0,1], changeIndices = [2,2,2]
Output: -1
Explanation: 这个例子中，无法标记所有下标，因为下标 1 不在 changeIndices 中。
所以答案是 -1 。

提示：

1 <= n == nums.length <= 2000
0 <= nums[i] <= 10⁹
1 <= m == changeIndices.length <= 2000
1 <= changeIndices[i] <= n

lightbulb

解题思路

方法一：二分查找

我们注意到，如果我们能够在 $t$ 秒内标记所有下标，那么我们也能在 $t' \geq t$ 秒内标记所有下标。因此，我们可以使用二分查找的方法找到最早的秒数。

我们定义二分查找的左右边界分别为 $l = 1$ 和 $r = m + 1$ ，其中 $m$ 是数组 changeIndices 的长度。对于每一个 $t = \frac{l + r}{2}$ ，我们检查是否能在 $t$ 秒内标记所有下标。如果能，我们将右边界移动到 $t$ ，否则我们将左边界移动到 $t + 1$ 。最终，我们判定左边界是否大于 $m$ ，如果是则返回 $-1$ ，否则返回左边界。

题目的关键在于如何判断是否能在 $t$ 秒内标记所有下标。我们可以使用一个数组 $last$ 记录每一个下标最晚需要被标记的时间，用一个变量 $decrement$ 记录当前可以减少的次数，用一个变量 $marked$ 记录已经被标记的下标的数量。

我们遍历数组 changeIndices 的前 $t$ 个元素，对于每一个元素 $i$ ，如果 $last[i] = s$ ，那么我们需要检查 $decrement$ 是否大于等于 $nums[i - 1]$ ，如果是，我们将 $decrement$ 减去 $nums[i - 1]$ ，并且将 $marked$ 加一；否则，我们返回 False。如果 $last[i] \neq s$ ，那么我们可以暂时不标记下标，因此将 $decrement$ 加一。最后，我们检查 $marked$ 是否等于 $n$ ，如果是，我们返回 True，否则返回 False。

时间复杂度 $O(m \times \log m)$ ，空间复杂度 $O(n)$ 。其中 $n$ 和 $m$ 分别是数组 nums 和 changeIndices 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def earliestSecondToMarkIndices(
        self, nums: List[int], changeIndices: List[int]
    ) -> int:
        def check(t: int) -> bool:
            decrement = 0
            marked = 0
            last = {i: s for s, i in enumerate(changeIndices[:t])}
            for s, i in enumerate(changeIndices[:t]):
                if last[i] == s:
                    if decrement < nums[i - 1]:
                        return False
                    decrement -= nums[i - 1]
                    marked += 1
                else:
                    decrement += 1
            return marked == len(nums)

        m = len(changeIndices)
        l = bisect_left(range(1, m + 2), True, key=check) + 1
        return -1 if l > m else l

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate is expected to demonstrate understanding of binary search as a tool for narrowing down the solution space.
question_mark
The candidate should simulate the process to check for valid solutions at each time step, ensuring they can handle edge cases.
question_mark
The ability to analyze time complexity and use efficient algorithms (like binary search) is a key factor in evaluating the candidate.

warning

常见陷阱

外企场景

error
Failing to account for the edge case where it's impossible to mark all indices, which should return -1.
error
Not using binary search effectively and resorting to a brute force approach, which would not scale well with larger inputs.
error
Misunderstanding the marking mechanism, leading to incorrect simulations and premature conclusions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider variations where multiple indices can be marked in the same second.
arrow_right_alt
Handling larger arrays or larger values in nums could require adjustments in both time complexity and space complexity.
arrow_right_alt
Introducing constraints on the order of operations could lead to different approaches to binary search or simulation.

help

常见问题

外企场景

继续练习

#3049 标记所有下标的最早秒数 II #3113 边界元素是最大值的子数组数目 #3116 单面值组合的第 K 小金额