LeetCode 3049 - Earliest Second to Mark Indices II

We are given two arrays: - nums, where nums[i] represents the initial value associated with index i + 1 - changeIndices, where at second s, we are allowed to perform a special operation on index changeIndices[s] Every index in nums starts as unmarked.

leetcodehardarraybinary-searchgreedyheap-(priority-queue)

LeetCode Problem 3049

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Greedy, Heap (Priority Queue)

Solution

Problem Understanding

We are given two arrays:

  • nums, where nums[i] represents the initial value associated with index i + 1
  • changeIndices, where at second s, we are allowed to perform a special operation on index changeIndices[s]

Every index in nums starts as unmarked. Our goal is to mark every index as early as possible.

At each second, exactly one action may be performed:

  1. Decrement some nums[i] by 1
  2. Set nums[changeIndices[s]] to any non-negative value
  3. Mark an index whose current value is 0
  4. Do nothing

The key detail is that the "set" operation is only available for the index specified by changeIndices[s] at that second.

The objective is to determine the earliest second t such that it is possible to mark every index using only the first t seconds. If it is impossible even after all m seconds, we return -1.

The constraints are important:

  • n, m <= 5000
  • nums[i] can be as large as 10^9

The large values inside nums immediately suggest that directly simulating decrements is not feasible. We need a strategy that avoids operating one decrement at a time whenever possible.

The most important observation is that the special "set to any non-negative value" operation can instantly reduce an element to 0. This can completely bypass the need for many decrement operations.

However, each index can only use this special reset at moments where it appears in changeIndices.

An important edge case is when some index never appears in changeIndices. In that case, the only way to reduce it to zero is through decrements, which may require too many seconds.

Another tricky case is that marking itself consumes one second. Even if all values become zero, we still need one separate second per index to mark them.

A naive implementation can easily fail by greedily using reset operations at the wrong times or by forgetting that reset operations also consume time.

Approaches

Brute Force

A brute force approach would try every possible sequence of operations second by second.

For each second, we could explore:

  • decrementing some index
  • using the reset operation
  • marking an index
  • doing nothing

This creates an enormous branching factor. Since there are up to 5000 seconds, the number of possible operation sequences becomes exponential.

Even if we attempt dynamic programming over states, the values inside nums can be extremely large, making the state space infeasible.

The brute force approach is correct because it explores all possible valid action sequences, but it is far too slow.

Key Insight

The core observation is that we do not need to explicitly simulate operations.

Instead, we can binary search the earliest feasible second.

Suppose we ask:

Can we mark all indices within the first t seconds?

If we can answer this efficiently, then binary search becomes possible.

Now we need a feasibility check.

For each index, we have two choices:

  1. Reduce it to zero manually using decrements
  2. Use one reset operation at some occurrence in changeIndices

Using a reset is extremely valuable for large values because it replaces many decrement operations with a single second.

The optimal strategy is therefore:

  • Choose some indices to reset
  • Manually decrement the others
  • Ensure enough total seconds remain for marking

The feasibility check is implemented greedily using a min heap.

We process the first t seconds from left to right and identify the last occurrence of each index. If we decide to use a reset for an index, we should use its last occurrence, because earlier occurrences are less flexible.

We greedily keep the most beneficial reset operations, where the benefit of resetting index i is saving nums[i] decrement operations.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Explores all operation sequences
Optimal O((n + m) log m) O(n) Binary search with greedy feasibility check

Algorithm Walkthrough

Step 1: Binary search the answer

The answer lies between 1 and m.

For each midpoint mid, we check whether all indices can be marked within the first mid seconds.

If feasible, we try earlier seconds.

If not feasible, we try later seconds.

Step 2: Record the last occurrence of every index

Inside the feasibility check, we only care about the first mid seconds.

For every index, we record its last appearance within those seconds.

Why the last occurrence?

Because if we plan to use the reset operation for an index, delaying it as late as possible leaves earlier seconds available for other work.

Step 3: Process seconds left to right

We iterate through the first mid seconds.

Whenever we encounter the last occurrence of some index, we have a decision:

  • use this second as the reset operation for that index
  • or ignore it

Using the reset operation saves nums[i] decrement operations.

We greedily want the most valuable resets.

Step 4: Use a min heap to keep best resets

Suppose we have already selected several reset operations.

Each selected reset costs:

  • one second for the reset itself
  • one second later for marking

However, it saves nums[i] decrement operations.

We maintain a min heap of selected reset benefits.

If we do not have enough available time, we remove the least beneficial reset.

This guarantees that we keep only the most valuable reset operations.

Step 5: Compute total required operations

After selecting reset operations:

  • indices using reset require:

  • one reset second

  • one marking second

  • indices without reset require:

  • nums[i] decrement seconds

  • one marking second

We check whether the total fits within mid.

If yes, the prefix is feasible.

Why it works

The greedy strategy is optimal because reset operations have independent benefits.

Whenever time becomes insufficient, removing the reset with the smallest benefit loses the least amount of saved work.

Using the last occurrence of each index is also optimal because earlier occurrences provide no additional advantage.

Binary search is valid because feasibility is monotonic:

  • if marking is possible within t seconds, it is also possible within any larger number of seconds.

Python Solution

from typing import List
import heapq

class Solution:
    def earliestSecondToMarkIndices(
        self,
        nums: List[int],
        changeIndices: List[int]
    ) -> int:

        n = len(nums)
        m = len(changeIndices)

        changeIndices = [x - 1 for x in changeIndices]

        def can_finish(limit: int) -> bool:
            last = [-1] * n

            for second in range(limit):
                last[changeIndices[second]] = second

            if -1 in last:
                return False

            heap = []
            used_time = 0

            for second in range(limit):
                idx = changeIndices[second]

                if last[idx] != second:
                    continue

                benefit = nums[idx]

                heapq.heappush(heap, benefit)
                used_time += 1

                available_before = second + 1 - used_time

                if available_before < sum(heap):
                    removed = heapq.heappop(heap)
                    used_time -= 1

            reset_used = len(heap)

            total_manual = sum(nums) - sum(heap)

            required = total_manual + n + reset_used

            return required <= limit

        left = 1
        right = m
        answer = -1

        while left <= right:
            mid = (left + right) // 2

            if can_finish(mid):
                answer = mid
                right = mid - 1
            else:
                left = mid + 1

        return answer

The implementation begins by converting changeIndices to zero-based indexing so that array access becomes simpler.

The helper function can_finish(limit) determines whether all indices can be marked within the first limit seconds.

We first compute the last occurrence of every index inside the prefix. If any index never appears, then we cannot use the reset operation for that index. Since marking still requires time, feasibility may fail immediately.

We then iterate through the prefix and process only last occurrences. These are the only moments worth considering for reset operations.

The min heap stores the benefits of chosen resets. The heap allows us to efficiently remove the least valuable reset whenever we exceed available time.

At the end, we compute the total number of operations required:

  • manual decrements for indices not reset
  • one marking operation per index
  • one reset operation per chosen reset

If this total fits inside the prefix length, the prefix is feasible.

Finally, binary search finds the smallest feasible prefix.

Go Solution

package main

import (
	"container/heap"
)

type MinHeap []int

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	value := old[n-1]
	*h = old[:n-1]
	return value
}

func earliestSecondToMarkIndices(nums []int, changeIndices []int) int {
	n := len(nums)
	m := len(changeIndices)

	for i := 0; i < m; i++ {
		changeIndices[i]--
	}

	canFinish := func(limit int) bool {
		last := make([]int, n)

		for i := 0; i < n; i++ {
			last[i] = -1
		}

		for second := 0; second < limit; second++ {
			last[changeIndices[second]] = second
		}

		for i := 0; i < n; i++ {
			if last[i] == -1 {
				return false
			}
		}

		h := &MinHeap{}
		heap.Init(h)

		usedTime := 0
		sumHeap := 0

		for second := 0; second < limit; second++ {
			idx := changeIndices[second]

			if last[idx] != second {
				continue
			}

			benefit := nums[idx]

			heap.Push(h, benefit)
			sumHeap += benefit
			usedTime++

			availableBefore := second + 1 - usedTime

			if availableBefore < sumHeap {
				removed := heap.Pop(h).(int)
				sumHeap -= removed
				usedTime--
			}
		}

		resetUsed := h.Len()

		totalNums := 0
		for _, value := range nums {
			totalNums += value
		}

		required := (totalNums - sumHeap) + n + resetUsed

		return required <= limit
	}

	left := 1
	right := m
	answer := -1

	for left <= right {
		mid := (left + right) / 2

		if canFinish(mid) {
			answer = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python solution.

Since Go does not provide a built-in heap abstraction for integers, we implement a custom MinHeap type using the container/heap package.

Another important difference is that Go requires explicit maintenance of the heap sum, so sumHeap is updated manually whenever elements are pushed or popped.

The algorithm uses only integer arithmetic, and the constraints fit safely within Go's int type on LeetCode platforms.

Worked Examples

Example 1

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

We binary search.

Check t = 6.

Last occurrences inside first 6 seconds:

Index Last Occurrence
1 1
2 6
3 2

Process seconds:

Second Index Action
1 1 consider reset benefit 3
2 3 consider reset benefit 3
3 2 skipped
4 2 skipped
5 2 skipped
6 2 consider reset benefit 2

Heap becomes [2,3,3].

Using all three resets means:

  • 3 reset seconds
  • 3 marking seconds

Total = 6.

Feasible.

Check t = 5.

Not enough time to both reset and mark all indices.

Answer = 6.

Example 2

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

Binary search checks t = 7.

We only need manual decrements for indices 3 and 4.

Required work:

  • decrement index 4 twice
  • decrement index 3 once
  • 4 marking operations

Total = 7.

Feasible.

Earlier times are impossible.

Answer = 7.

Example 3

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

There are only 3 seconds total.

Even if every second is used as a reset, we still need 3 additional marking seconds.

Impossible.

Answer = -1.

Complexity Analysis

Measure Complexity Explanation
Time O((n + m) log m) Binary search with heap-based feasibility checks
Space O(n) Last occurrence array and heap

The binary search performs O(log m) iterations.

Each feasibility check scans at most m seconds and performs heap operations costing O(log n).

Since n, m <= 5000, this solution easily fits within limits.

Test Cases

sol = Solution()

# Provided examples
assert sol.earliestSecondToMarkIndices(
    [3, 2, 3],
    [1, 3, 2, 2, 2, 2, 3]
) == 6  # example 1

assert sol.earliestSecondToMarkIndices(
    [0, 0, 1, 2],
    [1, 2, 1, 2, 1, 2, 1, 2]
) == 7  # example 2

assert sol.earliestSecondToMarkIndices(
    [1, 2, 3],
    [1, 2, 3]
) == -1  # example 3

# Single element already zero
assert sol.earliestSecondToMarkIndices(
    [0],
    [1]
) == 1  # immediate mark

# Single element requiring reset
assert sol.earliestSecondToMarkIndices(
    [100],
    [1, 1]
) == 2  # reset then mark

# Impossible because no time to mark
assert sol.earliestSecondToMarkIndices(
    [1],
    [1]
) == -1  # only one second available

# All zeros
assert sol.earliestSecondToMarkIndices(
    [0, 0, 0],
    [1, 2, 3]
) == 3  # just mark all

# Large values requiring resets
assert sol.earliestSecondToMarkIndices(
    [10**9, 10**9],
    [1, 2, 1, 2]
) == 4  # resets mandatory

# Missing index in changeIndices
assert sol.earliestSecondToMarkIndices(
    [5, 0],
    [1, 1, 1]
) == -1  # index 2 never appears

# Repeated appearances
assert sol.earliestSecondToMarkIndices(
    [2, 2],
    [1, 1, 2, 2, 1, 2]
) == 6  # careful scheduling

Test Summary

Test Why
[3,2,3] example Basic mixed reset usage
[0,0,1,2] example Mostly decrement operations
[1,2,3] example Impossible scenario
Single zero element Minimal valid case
Single large value Reset necessity
One second only Insufficient marking time
All zeros Only marking operations needed
Large values Stress reset optimization
Missing index Unreachable state
Repeated appearances Greedy heap behavior

Edge Cases

One important edge case occurs when an index never appears in changeIndices. Since reset operations are only available when the index appears, such an index can only be reduced manually through decrements. If the required decrements plus marking operations exceed the available time, the answer becomes impossible. The implementation detects this by checking whether every index has a valid last occurrence.

Another tricky case happens when values are already zero. A naive implementation might assume these indices are already complete, but they still require separate marking operations. The solution always includes n marking operations in the required total, ensuring correctness.

A third important edge case is extremely large values such as 10^9. Direct decrement simulation would be infeasible. The implementation avoids this entirely by reasoning about total work mathematically and using reset operations greedily.

A subtle scheduling edge case arises when an index appears many times in changeIndices. Using an early reset is never better than using the last occurrence because earlier seconds are more flexible. The algorithm explicitly uses only last occurrences, which guarantees optimal scheduling flexibility.