Skip to content

Practice Earliest Second to Mark Indices I

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Medium#3048
LeetCode Problem

Earliest Second to Mark Indices I

Problem Statement

nums and changeIndices use 1-based indices. Initially every nums position is unmarked. At second s, choose ONE action: decrease any nums value by one; mark position changeIndices[s] if its value is zero; or wait. Find the earliest second when all positions can be marked, or -1 if the schedule cannot achieve this. Approach: Binary-search a deadline. In its prefix, reserve the last occurrence of each index for marking. Scan forward, treating other seconds as available decrements. Each reserved marking requires enough earlier free seconds to reduce that index to zero. Missing indices or insufficient earlier work make the deadline infeasible. This check takes O(n + m) time; binary search adds a log m factor.

Source: Earliest Second to Mark Indices I on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
nums = [1,0], changeIndices = [1,2,1]
Output
3
Explanation

Decrease index 1 at second 1, mark index 2 at second 2, and mark index 1 at second 3.

# Example 2

Input
nums = [0,0], changeIndices = [1,1]
Output
-1
Explanation

Index 2 never appears in the marking schedule.

Constraints

1 <= nums.length, changeIndices.length <= 2000
0 <= nums[i] <= 1000000000
Every changeIndices value is between 1 and nums.length.

How to solve Earliest Second to Mark Indices I

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

Feasibility is monotone in the deadline, since a finished schedule can simply wait, and for a fixed deadline the best moment to mark an index is its last appearance within that deadline, because marking later leaves more earlier seconds for decrements. That yields a binary search over deadlines with a linear greedy check.

Why brute force is not enough

Trying every deadline and exploring all assignments of seconds to decrement, mark or wait is exponential, and simulating decrements one unit per second is hopeless with values up to 10^9 even though n and m are only 2000.

Approach

  1. Test the full deadline m first; if it fails, return -1. Otherwise binary search the smallest feasible deadline between 1 and m.
  2. For a candidate T, record the last second at which each index appears within the first T seconds; an index that never appears makes T infeasible.
  3. Scan seconds 1 through T with a count of free seconds. A second that is not a last appearance is free and increments the count; the invariant is that the count equals the earlier seconds still available for decrements.
  4. At the last appearance of index i, require the count to be at least nums[i]; consume that many and mark i, otherwise T fails. Marking at the last appearance only enlarges the pool of earlier seconds, and decrements are interchangeable, so the greedy is optimal.

Walkthrough of Example 1

nums = [1,0], changeIndices = [1,2,1] → 3

  1. Check T = 3 with changeIndices = [1,2,1]: index 1 last appears at second 3 and index 2 at second 2.
  2. Second 1 is not a last appearance, so free count becomes 1. Second 2 marks index 2, which needs 0 decrements; count stays 1.
  3. Second 3 marks index 1, which needs 1 decrement; the count covers it. T = 3 is feasible.
  4. Check T = 2: index 1 last appears at second 1, but the free count is 0 while it needs 1, so T = 2 fails.
  5. The earliest feasible second is 3.

Time and space

Time O((n + m) log m) · Space O(n). Each check scans the m seconds and n indices once, binary search runs about log m checks, and the last-appearance table has one entry per index.

Interview pitfalls

  • Marking at the first appearance instead of the last within the deadline, which starves later indices of decrement seconds and rejects feasible deadlines.
  • Treating nums[i] = 0 as free: such an index still needs an appearance and one second to be marked.
  • Letting seconds after an index's last appearance count toward its decrements; decrements must precede the mark.
  • Searching beyond m; the schedule has exactly m seconds, and -1 is the answer when m itself fails.

Follow-up questions interviewers ask

  • What changes in part II, where changeIndices gates a reset-to-any-value action instead of marking?
  • How would the check adapt if a single second could subtract up to d units?
  • Can you reuse work across many nums arrays that share one changeIndices?

Further reading on the technique: Binary search algorithm

Related LeetCode Problems

Practice more problems similar to Earliest Second to Mark Indices I.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.