LeetCode #3049 — HARD

Earliest Second to Mark Indices II

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

Solve on LeetCode
The Problem

Problem Statement

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:

  • Choose an index i in the range [1, n] and decrement nums[i] by 1.
  • Set nums[changeIndices[s]] to any non-negative value.
  • Choose an index i in the range [1, n], where nums[i] is equal to 0, and mark index i.
  • Do nothing.

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 = [3,2,3], changeIndices = [1,3,2,2,2,2,3]
Output: 6
Explanation: In this example, we have 7 seconds. The following operations can be performed to mark all indices:
Second 1: Set nums[changeIndices[1]] to 0. nums becomes [0,2,3].
Second 2: Set nums[changeIndices[2]] to 0. nums becomes [0,2,0].
Second 3: Set nums[changeIndices[3]] to 0. nums becomes [0,0,0].
Second 4: Mark index 1, since nums[1] is equal to 0.
Second 5: Mark index 2, since nums[2] is equal to 0.
Second 6: Mark index 3, since nums[3] 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 2:

Input: nums = [0,0,1,2], changeIndices = [1,2,1,2,1,2,1,2]
Output: 7
Explanation: In this example, we have 8 seconds. The following operations can be performed to mark all indices:
Second 1: Mark index 1, since nums[1] is equal to 0.
Second 2: Mark index 2, since nums[2] is equal to 0.
Second 3: Decrement index 4 by one. nums becomes [0,0,1,1].
Second 4: Decrement index 4 by one. nums becomes [0,0,1,0].
Second 5: Decrement index 3 by one. nums becomes [0,0,0,0].
Second 6: Mark index 3, since nums[3] is equal to 0.
Second 7: Mark index 4, since nums[4] 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 7th second.
Hence, the answer is 7.

Example 3:

Input: nums = [1,2,3], changeIndices = [1,2,3]
Output: -1
Explanation: In this example, it can be shown that it is impossible to mark all indices, as we don't have enough seconds. 
Hence, the answer is -1.

Constraints:

  • 1 <= n == nums.length <= 5000
  • 0 <= nums[i] <= 109
  • 1 <= m == changeIndices.length <= 5000
  • 1 <= changeIndices[i] <= n
Patterns Used
🔍Modified Binary Search→🎯Greedy→

Roadmap

  1. Brute Force Baseline
  2. Core Insight
  3. Algorithm Walkthrough
  4. Edge Cases
  5. Full Annotated Code
  6. Interactive Study Demo
  7. Complexity Analysis
Step 01

Brute Force Baseline

Problem summary: 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: Choose an index i in the range [1, n] and decrement nums[i] by 1. Set nums[changeIndices[s]] to any non-negative value. Choose an index i in the range [1, n], where nums[i] is equal to 0, and mark index i. Do nothing. 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Binary Search · Greedy

Example 1

[3,2,3]
[1,3,2,2,2,2,3]

Example 2

[0,0,1,2]
[1,2,1,2,1,2,1,2]

Example 3

[1,2,3]
[1,2,3]
Step 02

Core Insight

What unlocks the optimal approach

  • We need at least <code>n</code> seconds, and at most <code>sum(nums[i]) + n</code> seconds.
  • We can binary search the earliest second where all indices can be marked.
  • If there is an operation where we change <code>nums[changeIndices[i]]</code> to a non-negative value, it is best for it to satisfy the following constraints:<ul> <li><code>nums[changeIndices[i]]</code> should not be equal to <code>0</code>.</li> <li><code>nums[changeIndices[i]]</code> should be changed to <code>0</code>.</li> <li>It should be the first position where <code>changeIndices[i]</code> occurs in <code>changeIndices</code>.</li> <li>There should be another second, <code>j</code>, where <code>changeIndices[i]</code> will be marked. <code>j</code> is in the range <code>[i + 1, m]</code>.</li> </ul>
  • Let <code>time_needed = sum(nums[i]) + n</code>. To check if we can mark all indices at some second <code>x</code>, we need to make <code>time_needed <= x</code>, using non-negative change operations as described previously.
  • Using a non-negative change operation on some <code>nums[changeIndices[i]]</code> that satisfies the constraints described previously reduces <code>time_needed</code> by <code>nums[changeIndices[i]] - 1</code>. So, we need to maximize the sum of <code>(nums[changeIndices[i]] - 1)</code> while ensuring that the non-negative change operations still satisfy the constraints.
  • Maximizing the sum of <code>(nums[changeIndices[i]] - 1)</code> can be done greedily using a min-priority queue and going in reverse starting from second <code>x</code> to second <code>1</code>, maximizing the sum of the values in the priority queue and ensuring that for every non-negative change operation on <code>nums[changeIndices[i]]</code> chosen, there is another second <code>j</code> in the range <code>[i + 1, x]</code> where <code>changeIndices[i]</code> can be marked.
Interview move: turn each hint into an invariant you can check after every iteration/recursion step.
Step 03

Algorithm Walkthrough

Iteration Checklist

  1. Define state (indices, window, stack, map, DP cell, or recursion frame).
  2. Apply one transition step and update the invariant.
  3. Record answer candidate when condition is met.
  4. Continue until all input is consumed.
Use the first example testcase as your mental trace to verify each transition.
Step 04

Edge Cases

Minimum Input
Single element / shortest valid input
Validate boundary behavior before entering the main loop or recursion.
Duplicates & Repeats
Repeated values / repeated states
Decide whether duplicates should be merged, skipped, or counted explicitly.
Extreme Constraints
Largest constraint values
Re-check complexity target against constraints to avoid time-limit issues.
Invalid / Corner Shape
Empty collections, zeros, or disconnected structures
Handle special-case structure before the core algorithm path.
Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3049: Earliest Second to Mark Indices II
class Solution {
  public int earliestSecondToMarkIndices(int[] nums, int[] changeIndices) {
    final long numsSum = Arrays.stream(nums).asLongStream().sum();
    // {the second: the index of nums can be zeroed at the current second}
    Map<Integer, Integer> secondToIndex = getSecondToIndex(nums, changeIndices);
    int l = 0;
    int r = changeIndices.length + 1;

    while (l < r) {
      final int m = (l + r) / 2;
      if (canMark(nums, secondToIndex, m))
        r = m;
      else
        l = m + 1;
    }

    return l <= changeIndices.length ? l : -1;
  }

  // Returns true if all indices of `nums` can be marked within `maxSecond`.
  private boolean canMark(int[] nums, Map<Integer, Integer> secondToIndex, int maxSecond,
                          final long numsSum) {
    // Use a min-heap to greedily pop out the minimum number, which yields the
    // least saving.
    Queue<Integer> minHeap = new PriorityQueue<>();
    int marks = 0;

    for (int second = maxSecond - 1; second >= 0; --second) {
      if (secondToIndex.containsKey(second)) {
        // The number mapped by the index is a candidate to be zeroed out.
        final int index = secondToIndex.get(second);
        minHeap.offer(nums[index]);
        if (marks == 0) {
          // Running out of marks, so need to pop out the minimum number.
          // So, the current second will be used to mark an index.
          minHeap.poll();
          ++marks;
        } else {
          // There're enough marks.
          // So, the current second will be used to zero out a number.
          --marks;
        }
      } else {
        // There's no candidate to be zeroed out.
        // So, the current second will be used to mark an index.
        ++marks;
      }
    }

    final int heapSize = minHeap.size();
    final long decrementAndMarkCost = numsSum - getHeapSum(minHeap) + (nums.length - heapSize);
    final long zeroAndMarkCost = heapSize + heapSize;
    return decrementAndMarkCost + zeroAndMarkCost <= maxSecond;
  }

  private long getHeapSum(Queue<Integer> minHeap) {
    long sum = 0;
    while (!minHeap.isEmpty())
      sum += minHeap.poll();
    return sum;
  }

  private Map<Integer, Integer> getSecondToIndex(int[] nums, int[] changeIndices) {
    // {the `index` of nums: the earliest second to zero out nums[index]}
    Map<Integer, Integer> indexToFirstSecond = new HashMap<>();
    Map<Integer, Integer> secondToIndex = new HashMap<>();
    for (int zeroIndexedSecond = 0; zeroIndexedSecond < changeIndices.length; ++zeroIndexedSecond) {
      // Convert to 0-indexed.
      final int index = changeIndices[zeroIndexedSecond] - 1;
      if (nums[index] > 0)
        indexToFirstSecond.putIfAbsent(index, zeroIndexedSecond);
    }
    for (Map.Entry<Integer, Integer> entry : indexToFirstSecond.entrySet()) {
      final int index = entry.getKey();
      final int second = entry.getValue();
      secondToIndex.put(second, index);
    }
    return secondToIndex;
  }
}
Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Press Step or Run All to begin.
Step 07

Complexity Analysis

Time
O(log n)
Space
O(1)

Approach Breakdown

LINEAR SCAN
O(n) time
O(1) space

Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.

BINARY SEARCH
O(log n) time
O(1) space

Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).

Shortcut: Halving the input each step → O(log n). Works on any monotonic condition, not just sorted arrays.
Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Boundary update without `+1` / `-1`

Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.

Usually fails on: Two-element ranges never converge.

Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.

Using greedy without proof

Wrong move: Locally optimal choices may fail globally.

Usually fails on: Counterexamples appear on crafted input orderings.

Fix: Verify with exchange argument or monotonic objective before committing.

Related Problems
#410Split Array Largest Sumhard→#611Valid Triangle Numbermedium→#826Most Profit Assigning Workmedium→#1488Avoid Flood in The Citymedium→#1648Sell Diminishing-Valued Colored Ballsmedium→