Abstract / Summary

You must move through an array to collect all required elements using the fewest steps possible.

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 62% (70k+ submissions).

Typical patterns to solve this problem:

• Array
• Bit Manipulation
• Hash Table

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 minOperations method determines the smallest number of removal operations required to guarantee that the integers 1 through k all appear among the elements that have been removed from the end of the input list nums. Each operation discards the last element of nums. The method returns the count of such operations once every value in the target range has been observed.

Key Steps

Initialization

The algorithm begins by establishing a counter for performed operations and a set containing the required values.

result = 0
need = set(range(1, k + 1))

result tracks how many elements have been removed. need holds the numbers that have not yet been seen; using a set enables constant-time membership checks and deletions.

Loop Execution

The core of the method repeatedly removes the last element of nums until the need set becomes empty.

while need:
    need.discard(nums.pop())
    result += 1

nums.pop() extracts the element at the end of the list in O(1) time. need.discard(...) attempts to delete the popped value from the set; if the value is not present, the operation has no effect, avoiding the need for an explicit containment test. The loop condition while need ensures that iteration stops precisely when all required numbers have been encountered, preventing unnecessary work.

Return

After the loop terminates, the method yields the total number of removals performed.

return result

The returned integer represents the minimal count of end-removals needed to collect the full range 1…k.

Edge Cases Handled

When k equals 0, the need set is initially empty, causing the loop to be bypassed entirely; the method correctly returns 0, indicating that no operations are required.

If the required numbers already appear among the trailing elements of nums, the loop exits as soon as the last missing value is popped, potentially after only a few iterations rather than scanning the entire list.

The use of set.discard gracefully handles cases where a popped element is not part of the target range, eliminating the need for separate existence checks and ensuring the algorithm proceeds without interruption.

Performance Optimizations

The implementation leverages two primary optimizations. First, the target values are stored in a hash-based set, granting O(1) average-case performance for removal operations and eliminating linear searches. Second, the algorithm removes elements from the end of the list using pop(), which operates in constant time for Python lists. Together, these choices ensure that each iteration incurs minimal overhead and that the loop terminates as soon as the condition is satisfied, avoiding unnecessary processing of the remaining list elements.

Imagine you have a big treasure box full of colorful building blocks with numbers written on them. You want to make sure you have every single block from number one all the way up to some special number called k. Some of these blocks are already inside your box, but you do not know which ones are there yet.

To solve this, you start looking inside your box one by one, picking up the last block you see. Each time you pick up a block, you check if it is one of the numbers you need to collect. If it is a number you were waiting for, you put it in your collection pile and cross it off your list of things to find. You keep doing this over and over again, counting every single time you pick up a block until your list of needed numbers is completely empty. Once you have found all the numbers from one to k, you stop picking up blocks. The total count shows how many times you had to reach into the box.

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

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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	Java		C++		Python	TS
	WalkCCC	Java		C++		Python
	leetcode.ca	Java		C++	Go	Python	TS
	Progiez	Java		C++		Python
github	charles-wangkai	Java
	fsq			C++
	JoshCrozier		JS
	varunu28	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
varunu28	Java

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