LeetCode 3048 - Earliest Second to Mark Indices I

LeetCode Problem 3048

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

We are given two 1-indexed arrays:

• nums, where nums[i] represents how many decrement operations index i still needs before it becomes zero.
• changeIndices, where changeIndices[s] tells us which index is eligible to be marked at second s.

Initially, every index is unmarked. At every second, we may perform exactly one action:

1. Decrement any nums[i] by 1
2. Mark changeIndices[s], but only if its current value is 0
3. Do nothing

The goal is to determine the earliest second when all indices can be marked.

The important detail is that marking opportunities are fixed in time. At second s, the only index that can be marked is changeIndices[s]. If that index is not zero at that moment, we lose that marking opportunity for that second.

This creates two kinds of requirements:

• Every index must eventually reach zero through decrement operations.
• Every index must also appear in changeIndices at some usable moment after it has become zero.

The constraints are:

• n <= 2000
• m <= 2000

This size is small enough for an O(n * m) or O(m log m) style solution, but too large for exponential search or heavy state-space dynamic programming.

Several edge cases are important:

• Some index may never appear in changeIndices, making the answer immediately impossible.
• Some indices may already start at 0, requiring no decrements.
• There may not be enough total seconds to both perform decrements and perform markings.
• A marking opportunity may occur before enough decrements have been completed.

The key challenge is balancing decrement time and marking time while respecting the chronological order of operations.

Approaches

Brute Force Approach

A brute-force solution would attempt to simulate every possible sequence of operations across all seconds.

At each second, we could choose among:

• decrementing any valid index,
• marking the current allowed index if possible,
• or doing nothing.

This creates a huge branching factor. Even with pruning, the number of possible states becomes exponential because every second introduces many choices.

The brute-force method is correct because it explores all valid operation sequences and eventually finds the earliest feasible time. However, it is far too slow. With up to 2000 seconds, exhaustive exploration is computationally impossible.

Key Insight

The critical observation is that we do not need to explicitly simulate every operation sequence.

Suppose we want to know whether it is possible to finish all markings within the first t seconds.

For each index, only its last appearance within the first t seconds matters. Earlier appearances are irrelevant because delaying the marking as late as possible gives us maximum time to finish decrements.

So for a candidate time t:

• Find the last occurrence of every index within the first t seconds.
• Those last occurrences become mandatory marking moments.
• Every other second before those moments can be used for decrement operations.

Now the problem becomes:

Can we finish all required decrements before each index's final marking time?

This feasibility check can be done greedily in linear time.

Since feasibility is monotonic:

• if we can finish by time t,
• then we can also finish by any later time,

we can binary search the earliest valid second.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all possible 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 earliest valid second lies somewhere in the range [1, m].

We binary search this range:

• If finishing within mid seconds is possible, try smaller values.
• Otherwise, try larger values.

This works because feasibility is monotonic.

Step 2: Build the last occurrence map

For a candidate time t, scan the first t seconds.

For every second s:

• let idx = changeIndices[s]
• record that index idx last appears at second s

At the end:

• every index must have a recorded last occurrence
• otherwise marking all indices is impossible

We store this in an array last.

Step 3: Simulate the timeline

Now iterate through the first t seconds again.

If second s is the last occurrence of some index:

• this second must be reserved for marking
• before this moment, we must already have completed all decrements for that index

Otherwise:

• this second can be used as a decrement operation
• increment a counter freeOps

Step 4: Spend decrement operations greedily

When we reach a mandatory marking second for index i:

• we need nums[i] decrement operations already completed
• if freeOps < nums[i], then feasibility fails
• otherwise subtract nums[i] from freeOps

This greedily allocates available decrement seconds.

Step 5: Continue binary search

If the feasibility check succeeds:

• record the candidate answer
• continue searching smaller times

Otherwise:

• search larger times

Why it works

The algorithm works because using the last occurrence of each index as its marking moment maximizes the available time for decrements.

Any earlier marking would only reduce flexibility.

The greedy simulation correctly tracks how many non-marking seconds are available for decrements. Every mandatory marking consumes one second, and all remaining seconds may be freely used for decrement operations.

If at any marking moment there are not enough decrement operations available, then no valid schedule exists for that candidate time.

Because feasibility is monotonic, binary search correctly finds the minimum valid second.

Python Solution

from typing import List

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

        # Convert to 0-indexed
        changeIndices = [x - 1 for x in changeIndices]

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

            # Record last occurrence within first limit seconds
            for second in range(limit):
                idx = changeIndices[second]
                last[idx] = second

            # Every index must appear at least once
            for idx in range(n):
                if last[idx] == -1:
                    return False

            free_ops = 0

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

                # Mandatory marking second
                if last[idx] == second:
                    needed = nums[idx]

                    if free_ops < needed:
                        return False

                    free_ops -= needed
                else:
                    # Free second usable for decrements
                    free_ops += 1

            return True

        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 into zero-based indexing because Python arrays are zero-indexed.

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

Inside this function:

• last[idx] stores the final appearance of index idx
• if any index never appears, the function immediately returns False

The simulation then processes each second:

• if the current second is the last occurrence of an index, that second must be used for marking
• otherwise the second becomes a free decrement operation

The variable free_ops tracks how many decrement operations are available.

When a mandatory marking second arrives, we check whether enough decrement operations have already been accumulated to reduce the corresponding value to zero.

The outer binary search repeatedly calls this feasibility checker to locate the minimum valid second.

Go Solution

package main

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

	// Convert to 0-indexed
	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
		}

		// Record last occurrence
		for second := 0; second < limit; second++ {
			idx := changeIndices[second]
			last[idx] = second
		}

		// Every index must appear
		for i := 0; i < n; i++ {
			if last[i] == -1 {
				return false
			}
		}

		freeOps := 0

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

			// Mandatory marking second
			if last[idx] == second {
				needed := nums[idx]

				if freeOps < needed {
					return false
				}

				freeOps -= needed
			} else {
				// Free second for decrements
				freeOps++
			}
		}

		return true
	}

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

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

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

	return answer
}

The Go implementation closely mirrors the Python version.

The main differences are:

• slices are used instead of Python lists
• arrays must be manually initialized with -1
• integer division uses standard Go integer semantics
• closures are used for the feasibility function

There are no integer overflow concerns because values only involve counts up to roughly 2000 plus nums[i], which easily fit inside Go's int.

Worked Examples

Example 1

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

After converting to zero-based indexing:

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

We binary search.

Try t = 8.

Last occurrences

Index	Last Occurrence
0	7
1	6
2	4

Timeline simulation

Second	Index	Last Occurrence?	Action	freeOps
0	1	No	Free decrement	1
1	1	No	Free decrement	2
2	1	No	Free decrement	3
3	1	No	Free decrement	4
4	2	Yes	Mark index 2, need 0	4
5	1	No	Free decrement	5
6	1	Yes	Mark index 1, need 2	3
7	0	Yes	Mark index 0, need 2	1

Feasible, so answer may be 8.

Trying smaller values fails because index 0 does not appear early enough.

Final answer is 8.

Example 2

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

Zero-based:

changeIndices = [0,0,0,1,0,0,0]

Try t = 6.

Last occurrences

Index	Last Occurrence
0	5
1	3

Timeline simulation

Second	Index	Last Occurrence?	Action	freeOps
0	0	No	Free decrement	1
1	0	No	Free decrement	2
2	0	No	Free decrement	3
3	1	Yes	Mark index 1, need 3	0
4	0	No	Free decrement	1
5	0	Yes	Mark index 0, need 1	0

Feasible.

Trying t = 5 fails because there is not enough time to complete all decrements before the final markings.

Final answer is 6.

Example 3

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

Zero-based:

changeIndices = [1,1,1]

Index 0 never appears.

Therefore marking all indices is impossible.

Answer is -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + m) log m)	Binary search over m candidates, each feasibility check scans arrays linearly
Space	O(n)	Stores last occurrence information

Each feasibility check processes at most m seconds and stores an array of size n.

Since binary search performs O(log m) checks, the total complexity becomes O((n + m) log m).

With n, m <= 2000, this easily fits within limits.

Test Cases

sol = Solution()

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

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

assert sol.earliestSecondToMarkIndices(
    [0, 1],
    [2, 2, 2]
) == -1  # missing index entirely

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

# Single element needing decrements
assert sol.earliestSecondToMarkIndices(
    [2],
    [1, 1, 1]
) == 3  # two decrements then mark

# Impossible because not enough total time
assert sol.earliestSecondToMarkIndices(
    [5],
    [1, 1, 1, 1, 1]
) == -1  # no time left to mark

# Multiple zeros
assert sol.earliestSecondToMarkIndices(
    [0, 0],
    [1, 2]
) == 2  # both can be marked immediately

# Late appearance of an index
assert sol.earliestSecondToMarkIndices(
    [1, 0],
    [1, 1, 2]
) == 3  # index 2 only appears at end

# Tight scheduling
assert sol.earliestSecondToMarkIndices(
    [1, 1],
    [1, 2, 1, 2]
) == 4  # every second matters

# Large values but enough time
assert sol.earliestSecondToMarkIndices(
    [3, 2],
    [1, 1, 1, 2, 2, 1, 2]
) == 7  # exact fit

Test	Why
[2,2,0]	Validates standard scheduling behavior
[1,3]	Tests interleaving decrements and markings
[0,1] missing index	Confirms impossible detection
Single zero element	Tests immediate marking
Single positive element	Tests decrement counting
Insufficient total time	Ensures impossible schedules fail
Multiple zeros	Confirms no unnecessary decrements
Late appearance	Tests delayed marking opportunities
Tight schedule	Validates precise operation accounting
Larger decrement counts	Stresses greedy allocation

Edge Cases

An index never appears in changeIndices

This is the most important impossible case.

Even if an index can be reduced to zero, it can never be marked unless it appears in changeIndices.

A naive implementation might only track decrement feasibility and forget the marking requirement entirely.

The solution handles this by verifying that every index has a valid last occurrence within the candidate time window.

An index already starts at zero

If nums[i] == 0, no decrement operations are needed before marking.

A buggy implementation might incorrectly reserve decrement operations anyway.

In this solution, such indices simply require needed = 0, so the feasibility check succeeds immediately at their marking time.

Very tight schedules

Sometimes the total number of free decrement seconds exactly equals the required decrement count.

For example:

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

There is no extra room for wasted operations.

An incorrect greedy strategy could mark too early or misuse decrement seconds.

Using the last occurrence of every index guarantees maximal flexibility and ensures tight schedules are handled correctly.