Abstract / Summary

Remove k digits from a number string to make the smallest possible number.

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% (2+ million submissions).

Typical patterns to solve this problem:

• Greedy
• Monotonic Stack
• Stack
• String

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 defines a method that receives a numeric string num and an integer k. Its goal is to delete exactly k characters from num so that the resulting string represents the smallest possible non-negative integer, with any leading zeros removed except when the result is exactly zero.

Input Validation

Before any processing, the function checks two special conditions. If the input string is exactly "0" it returns "0" immediately, because removing digits cannot produce a value smaller than zero. The second guard handles the situation where the number of deletions requested is greater than or equal to the length of the string; in that case the only valid minimal result is "0".

if num == "0":
    return "0"
if k >= len(num):
    return "0"

These early returns avoid unnecessary work for trivial inputs.

Main Loop - Greedy Removal

The core of the algorithm is a greedy scan that repeatedly looks for the first position where a digit is larger than the digit that follows it. When such a pair is found, the larger digit is removed, k is decremented, and the scan restarts from the beginning. The loop continues while deletions remain and at least one removal occurred in the previous pass.

again = True
while k > 0 and again:
    again = False
    for i in range(len(num) - 1):
        if num[i+1] < num[i]:
            num = num[0:i] + num[i+1:]
            k -= 1
            again = True
            break

The again flag ensures that the outer loop terminates as soon as a full pass finds no decreasing adjacent pair, indicating that the remaining digits are in non-decreasing order.

Post-Processing - Truncate Remaining Digits

If the greedy phase finishes while deletions are still pending (k > 0), the remaining removals are applied to the rightmost part of the string. Because the digits are already sorted in non-decreasing order, discarding the last k characters yields the smallest possible outcome.

if k > 0:
    num = num[0:-k]

This single slice operation replaces what would otherwise be a series of individual deletions, saving repeated scanning.

Leading Zero Trimming

After all deletions, the result may contain leading zeros (for example, removing a leading digit from "10200" yields "0200"). A loop strips these zeros while preserving a single zero when the entire number collapses to zero.

while len(num) > 1 and num[0] == "0":
    num = num[1:]

The condition len(num) > 1 guarantees that the algorithm never returns an empty string.

Edge Cases Handled

The code explicitly addresses several boundary situations. When the original number is "0" the early return prevents any further manipulation. When k equals or exceeds the length of num, the function returns "0" without attempting deletions. If the digits are already sorted in ascending order (e.g., "12345"), the greedy loop makes no removal; the remaining k deletions are then performed by the truncation step, correctly discarding the largest trailing digits. Finally, the leading-zero removal loop ensures that results such as "000" are collapsed to a single "0".

Performance Optimizations

Two notable optimizations are present. First, the algorithm stops the inner scan as soon as it finds the first decreasing pair, avoiding unnecessary comparisons for the rest of the string in that pass. Second, after the greedy phase, any leftover deletions are applied in one bulk slice rather than iterating one by one, which reduces the number of string reconstructions. The use of early return checks also prevents the main loop from executing for inputs that can be resolved instantly.

Imagine you have a long necklace made of number beads. You want to take away a few beads so that the remaining ones form the smallest number possible.

The code starts by looking at the necklace. If the necklace only has a zero, or if you are told to take away just as many beads as there are on the string, the result is always zero.

Otherwise, the code goes on a hunt for beads that are bigger than the ones right next to them. When it finds a bigger bead followed by a smaller bead, it tosses the bigger one away because getting rid of a high number early on helps make the final number smaller. It repeats this process over and over until it has tossed away the right amount of beads or until the beads are lined up from smallest to largest.

If there are still more beads left to remove after that, it simply takes them off from the end of the line. Sometimes, there might be zeros hiding right at the very front of the line, which makes the number look confusing. The code slides through the beads one last time to throw away those extra leading zeros until only the true, smallest number remains.

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

Time: polynomial
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	C++	Python		Java							TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java					Go		TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fartem								Ruby
	fengvyi	C++
	fpdjsns	C++
	halfrost									Go
	haoel	C++
	JoshCrozier			JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	martianoff						Scala
	ruoru							Rust
	sonugiri1043	C++
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
	vli02										C
	wisdompeak	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fpdjsns	C++
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
MacJim	C++
martianoff	Scala
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
wisdompeak	C++
YuriSpiridonov	Python
zfang399	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