Practice Earliest Second to Mark Indices II
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Earliest Second to Mark Indices II
Problem Statement
Both arrays use 1-based indices. At second s, perform ONE action: decrease any nums value by one; replace nums[changeIndices[s]] with any nonnegative integer; mark any zero-valued unmarked position; or wait. All positions start unmarked. Return the earliest second when all are marked, or -1 if impossible. Unlike part I, changeIndices restricts the reset action, not which position can be marked. A reset can set a large value directly to zero, but its marking consumes a separate later second. Compare that two-action option with value + 1 decrement-and-mark actions. A deadline check must account for both reset opportunities and later marking slots before binary search can choose the earliest feasible deadline.
Source: Earliest Second to Mark Indices II on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
nums = [5,0], changeIndices = [1,2,2]
3
Reset index 1 at second 1, then mark indices 1 and 2 in separate seconds. Two seconds cannot finish three required actions.
# Example 2
nums = [0,0], changeIndices = [1,1]
2
Both values are already zero, so mark one index each second; index 2 need not appear in changeIndices.
Constraints
How to solve Earliest Second to Mark Indices II
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
Each index is finished either by nums[i] + 1 flexible seconds of decrements plus a mark, or by 2 seconds: a reset at its earliest appearance in changeIndices plus a later mark. A reset saves nums[i] - 1 seconds, so for a fixed deadline you want the maximum-saving set of resets whose reset seconds can each be matched to a distinct later marking second, which a backward scan with a min-heap finds.
Why brute force is not enough
Trying every subset of indices to reset and checking whether a schedule exists is exponential in n, up to 5000, and simulating single-unit decrements is impossible with values up to 10^9.
Approach
- Binary search the deadline T in 1..m after confirming T = m is feasible, returning -1 otherwise; feasibility is monotone because spare seconds can be spent waiting.
- For a given T, record each index's earliest appearance within the first T seconds. A reset is worth considering only there and only when nums[i] is at least 2.
- Scan seconds from T down to 1, tracking free seconds after the current one. A second that is not a useful earliest appearance adds one free second. At a useful one with a free later second available, commit the reset: push nums[i] onto a min-heap and consume one free second for its mark.
- If no free second remains, swap when nums[i] exceeds the heap minimum: dropping the smaller reset releases its two later seconds, and committing the new one leaves exactly one free. The heap always holds a maximum-saving feasible set for the suffix scanned so far.
- Finally sum 2 for each heap index and nums[i] + 1 for every other index; T is feasible when the total is at most T.
Walkthrough of Example 1
nums = [5,0], changeIndices = [1,2,2] → 3
- Check T = 3 with changeIndices = [1,2,2]: index 1 first appears at second 1, index 2 at second 2.
- Second 3 is not an earliest appearance, so one free second. Second 2 is index 2's earliest appearance but nums[2] = 0 saves nothing, so two free seconds.
- Second 1 is index 1's earliest appearance with nums[1] = 5; a free later second exists, so commit the reset, leaving one free second.
- Cost is 2 for index 1 plus 0 + 1 for index 2, total 3, which fits T = 3.
- Check T = 2: second 2 is free, second 1 commits the reset; cost 3 exceeds 2, so T = 2 fails. The answer is 3.
Time and space
Time O((n + m log n) log m) · Space O(n + m). Each check scans m seconds with at most one heap operation over at most n entries, then sums over n indices; binary search adds a log m factor. The earliest-appearance table and heap are linear in n.
Interview pitfalls
- Reusing the part I rule that changeIndices governs marking; here any zero-valued index can be marked at any second.
- Resetting at the last appearance rather than the first; the mark must follow the reset, so the earliest leaves the most room.
- Resetting indices with nums[i] of 0 or 1, which wastes a fixed second a flexible decrement could have used.
- Counting a reset as one action and forgetting its separate later mark.
- Summing nums[i] + 1 in 32-bit arithmetic when values reach 10^9 and n reaches 5000.
Follow-up questions interviewers ask
- Why does the backward scan with a min-heap find the maximum-saving feasible set, and how does it relate to scheduling jobs with deadlines?
- How would the check change if a reset could only halve the current value?
- Can you reconstruct an explicit second-by-second schedule once the deadline is known?
Further reading on the technique: Binary search algorithm
Related LeetCode Problems
Practice more problems similar to Earliest Second to Mark Indices II.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.