Abstract / Summary

Given a list of numbers and a target value, find the earliest position where marking it lets another matching value appear later.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 37% (30k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of determining the earliest second at which all indices of an array can be marked, given a sequence of change operations. The algorithm works by modeling the marking process as a feasibility check for a candidate timestamp and then searching for the minimal timestamp that satisfies this condition. The core idea is to treat each element of nums as a resource that must be decremented to zero before it can be marked, while the changeIndices list dictates when each index is eligible for a decrement or a final marking step.

Core Workflow

Preparation of Input Size

The function begins by capturing the length of the input array nums. This size is used throughout the algorithm to allocate auxiliary structures and to interpret the 1-based indices supplied in changeIndices.

size = len(nums)

Feasibility Predicate

A nested function possible(when) is defined to answer the question: “Can all indices be marked by the end of second when?” The predicate constructs a mark array that records the last second each index appears in the prefix of changeIndices up to when. This information is crucial for distinguishing the final opportunity to mark an index from earlier opportunities that merely contribute a decrement step.

def possible(when):
    mark = [ -1 ] * size
    for i, c in enumerate(changeIndices[:when]):
        c -= 1
        mark[c] = i

The second loop iterates over the same prefix, applying the logic of decrement versus final marking. When the current iteration index i matches the stored last occurrence mark[c], the algorithm performs the decrement of the corresponding nums entry and checks whether the cumulative steps counter stays non-negative. A negative steps indicates that the required decrements exceed the available “free” steps, causing the predicate to reject the candidate timestamp.

    steps = 0
    for i, c in enumerate(changeIndices[:when]):
        c -= 1
        if i == mark[c]:
            steps -= nums[c]
            mark[c] = 0
            if steps < 0:
                return False
        else:
            steps += 1

After processing the prefix, the predicate verifies that every entry in mark has been cleared (i.e., all indices have been marked). The expression sum(mark) == 0 succeeds only when every element has been set to zero, confirming that the candidate timestamp is feasible.

    return sum(mark) == 0

Lower Bound on Required Seconds

Before launching the search, the algorithm computes a baseline lower bound need. Each element of nums must be decremented exactly nums[i] times, and each index requires an additional step for the final marking. Summing these requirements yields need = sum(nums) + size.

need = sum(nums) + size

Earliest Full Coverage of Indices

The algorithm also determines the earliest second at which every distinct index appears at least once in changeIndices. By iterating through changeIndices and tracking seen indices in a set, it updates need to the maximum of the previously computed lower bound and the index of the last newly seen element. This adjustment ensures that the search does not start before it is even possible for all indices to have been referenced.

seen = set()
for i, c in enumerate(changeIndices):
    seen.add(c)
    if len(seen) == size:
        need = max(need, i)
        break

Binary Search for the Minimal Feasible Timestamp

The final step employs a binary search over the range [need, last], where last is defined as one beyond the length of changeIndices. The bisect_left function is invoked with a custom key that evaluates the possible predicate. The search returns the smallest timestamp for which possible returns True. If this timestamp exceeds last, the function reports failure with -1; otherwise, it returns the found timestamp.

last = len(changeIndices) + 1
result = need + bisect_left(range(need, last + 1), True, key=possible)
return result if result <= last else -1

Edge Cases Handled

The implementation gracefully handles several boundary conditions:

• Empty nums: When nums is empty, size becomes zero, the mark array is empty, and the predicate trivially returns True. The lower bound need evaluates to zero, and the binary search quickly resolves to zero, indicating that no steps are required.

• Single-Element Arrays: For a single element, the algorithm correctly tracks the sole index’s last occurrence and ensures that the required number of decrements plus the final marking step are accounted for.

• Repeated Indices in changeIndices: The mark array always stores the latest occurrence of each index within the examined prefix. This design automatically accommodates any number of repetitions, treating earlier appearances as ordinary decrement steps and the final appearance as the marking opportunity.

• Insufficient Decrement Opportunities: If the cumulative decrement requirement exceeds the number of available non-final steps, the steps counter becomes negative, causing the predicate to reject the candidate timestamp. This mechanism captures scenarios where the sequence of changes does not provide enough decrement actions before the final marking.

• All Indices Appear Late: The early-coverage loop updates need to the moment when every distinct index has been seen at least once. This prevents the binary search from considering timestamps that are impossible because some indices have never been referenced.

Performance Optimizations

The code incorporates several techniques that reduce unnecessary work and improve runtime characteristics:

• Prefix Limiting: Both loops inside possible operate only on the prefix changeIndices[:when]. By restricting work to the candidate length, the predicate avoids scanning the entire list for each binary-search step.

• In-Place Index Conversion: The conversion from 1-based to 0-based indices (c -= 1) is performed directly on the loop variable, eliminating the need for auxiliary arrays or additional mapping structures.

• Early Termination on Negative Steps: As soon as the steps counter drops below zero, the predicate returns False without completing the remaining iterations. This early exit prevents wasted computation when a candidate timestamp is clearly infeasible.

• Set-Based Early Coverage Detection: The loop that determines the earliest moment all indices appear uses a set to achieve O(1) membership checks, ensuring that the detection runs in linear time relative to the length of changeIndices.

• Binary Search via bisect_left with Custom Key: Leveraging the standard library’s binary search routine abstracts the search logic and benefits from its highly optimized implementation. The custom key function integrates the feasibility predicate directly, avoiding manual loop control and reducing overhead.

• Avoidance of Redundant Summations: The final verification sum(mark) == 0 relies on the fact that mark entries are set to zero only when an index has been successfully marked. This single summation replaces a more expensive per-element check.

Collectively, these choices keep the algorithm’s work proportional to the logarithm of the search interval multiplied by the cost of evaluating possible, which itself scales linearly with the candidate timestamp. The design therefore balances thoroughness with efficiency, delivering a solution that scales well for large input sizes.

Imagine you have some piggy banks with different amounts of coins inside. Your goal is to empty all of them so they reach zero. You have a special list of boxes you are allowed to visit one by one. Each time you visit a box, you can either put a coin back into your pocket or use a special magic wand to empty that specific piggy bank.

To make this work, the piggy bank must already be empty before you use the wand. You are trying to find the very first moment in the day when you can finish emptying every single piggy bank.

The code looks at these boxes one by one. It creates a plan to see if it is possible to finish the job by a certain time. First, it figures out the last possible moment each piggy bank could be visited. Then, it walks through the boxes to see if there is enough time to collect the coins and still hit the piggy bank with the wand at the right moment. If you run out of time or collect too few coins, the code says that specific time does not work.

Finally, it searches for the smallest amount of time needed to get the job done properly. It checks different time limits until it finds the quickest way to empty all the piggy banks. If it cannot find a way to finish by the end of the list, it gives up and decides it is impossible.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python	TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++		Java	Go	Python	TS
	Progiez	C++		Java		Python
github	charles-wangkai			Java
	everthis		JS
	fsq	C++
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality