You are given two 1-indexed integer arrays, nums and, changeIndices, having lengths n and m, respectively.
Initially, all indices in nums are unmarked. Your task is to mark all indices in nums.
In each second, s, in order from 1 to m (inclusive), you can perform one of the following operations:
i in the range [1, n] and decrement nums[i] by 1.nums[changeIndices[s]] is equal to 0, mark the index changeIndices[s].Return an integer denoting the earliest second in the range [1, m] when all indices in nums can be marked by choosing operations optimally, or -1 if it is impossible.
Example 1:
Input: nums = [2,2,0], changeIndices = [2,2,2,2,3,2,2,1] Output: 8 Explanation: In this example, we have 8 seconds. The following operations can be performed to mark all indices: Second 1: Choose index 1 and decrement nums[1] by one. nums becomes [1,2,0]. Second 2: Choose index 1 and decrement nums[1] by one. nums becomes [0,2,0]. Second 3: Choose index 2 and decrement nums[2] by one. nums becomes [0,1,0]. Second 4: Choose index 2 and decrement nums[2] by one. nums becomes [0,0,0]. Second 5: Mark the index changeIndices[5], which is marking index 3, since nums[3] is equal to 0. Second 6: Mark the index changeIndices[6], which is marking index 2, since nums[2] is equal to 0. Second 7: Do nothing. Second 8: Mark the index changeIndices[8], which is marking index 1, since nums[1] is equal to 0. Now all indices have been marked. It can be shown that it is not possible to mark all indices earlier than the 8th second. Hence, the answer is 8.
Example 2:
Input: nums = [1,3], changeIndices = [1,1,1,2,1,1,1] Output: 6 Explanation: In this example, we have 7 seconds. The following operations can be performed to mark all indices: Second 1: Choose index 2 and decrement nums[2] by one. nums becomes [1,2]. Second 2: Choose index 2 and decrement nums[2] by one. nums becomes [1,1]. Second 3: Choose index 2 and decrement nums[2] by one. nums becomes [1,0]. Second 4: Mark the index changeIndices[4], which is marking index 2, since nums[2] is equal to 0. Second 5: Choose index 1 and decrement nums[1] by one. nums becomes [0,0]. Second 6: Mark the index changeIndices[6], which is marking index 1, since nums[1] is equal to 0. Now all indices have been marked. It can be shown that it is not possible to mark all indices earlier than the 6th second. Hence, the answer is 6.
Example 3:
Input: nums = [0,1], changeIndices = [2,2,2] Output: -1 Explanation: In this example, it is impossible to mark all indices because index 1 isn't in changeIndices. Hence, the answer is -1.
Constraints:
1 <= n == nums.length <= 20000 <= nums[i] <= 1091 <= m == changeIndices.length <= 20001 <= changeIndices[i] <= nIn #3048 Earliest Second to Mark Indices I, the goal is to determine the earliest second when all indices can be marked given the order in changeIndices and the preparation time required in nums. Each index must be reduced to zero before it can be marked, and marking can only occur when that index appears in the sequence.
A common strategy is to use binary search on time. Instead of simulating the entire process, we guess a candidate second t and check if it is possible to finish marking all indices by that time. For the feasibility check, track the last occurrence of each index within the first t seconds and schedule the required decrement operations before that moment.
A greedy validation using a priority queue or counters helps ensure enough time exists to perform the necessary decrements before each mark. If all indices can be prepared and marked within t, we try a smaller time; otherwise, we increase it.
This approach efficiently narrows the answer while keeping the validation step manageable.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search with Greedy Feasibility Check | O(m log n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Consider using binary search.
Suppose the <code>answer <= x</code>; we can mark each index as late as possible. Namely, mark each index at the last occurrence in the array <code>changeIndices[1..x]</code>.
When marking an index, which is the last occurrence at the second <code>i</code>, we check whether we have a sufficient number of decrement operations to mark all the previous indices whose last occurrences have already been marked, and the current index, i.e., <code>i - sum_of_marked_indices_values - cnt_of_marked_indices >= nums[changeIndices[i]]</code>.
The answer is the earliest second when all indices can be marked after running the binary search or <code>-1</code> if there is no such second.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Binary search is used because the answer is monotonic. If it is possible to mark all indices by time t, then it will also be possible for any time greater than t, allowing us to efficiently search for the earliest feasible second.
Yes, problems like this frequently appear in technical interviews because they test binary search on answers, greedy reasoning, and scheduling logic. Similar patterns are common in interviews at large tech companies.
The optimal approach combines binary search with a greedy feasibility check. Binary search helps determine the earliest second, while the greedy step verifies if all indices can be prepared and marked within the chosen time limit.
Priority queues or simple arrays are commonly used during the feasibility check to track required preparation operations and the last occurrence of each index. These structures help manage scheduling decisions efficiently.