Remove k digits in Python with a list as a stack

Why this matters

Suppose a number is written as text, such as 1432219, and you must delete exactly three of its digits. You want the number that is left to be as small as possible. Which three digits should go?

This is a common interview question, and it teaches a pattern that shows up in many problems: a stack that keeps its contents in order, used to decide what to throw away as you read the input. The lesson uses that pattern, plus a greedy rule. A greedy method makes the choice that looks best right now and never changes it later. Here the greedy rule is simple: remove a digit when a smaller digit comes after it.

The lesson uses only a loop, a list, and a few string methods. The earlier lesson in this module, partition labels, also scans a string. This lesson does not repeat it.

Words you need

A digit is one of the characters 0 to 9. A number written with digits is compared from the left. The first digit counts most. 1999 is smaller than 2000, because the first digit 1 is less than 2. The later digits do not matter once the first digits differ.

A list in Python is an ordered collection of values. You write one with square brackets, such as [3, 1, 4]. Each value has a position called an index. The first index is 0. items[0] reads the first value, and items[-1] reads the last value. A negative index counts from the end, so -1 is the last item and -2 is the one before it.

A stack is a list where you add and remove items at one end only. The last item added is the first one taken out. People call this last in, first out. In Python a plain list does the job. append(x) adds x to the top, pop() removes the top and returns it, and stack[-1] reads the top without removing it. The standard library also has collections.deque, which is a faster choice when you remove items from the front. A list is enough here.

A monotonic stack is a stack whose items always go in one direction, either rising or falling, from the bottom to the top. This lesson keeps the digits in the stack rising, from smallest at the bottom to largest at the top. Each time a new digit arrives, the stack is changed just enough to keep this order.

A leading zero is a zero at the start of a number, such as the 0 in 0200. It has no value, so 0200 is the same number as 200.

A string is text, written in quotes. Each digit in this lesson is a string with one character, such as "3". Python compares strings letter by letter, so "1" < "2" is True. For single digits this gives the same order as the numbers.

The idea in plain words

Start with a short number, 1432, and remove one digit. There are four choices:

• Remove the 1: the result is 432.
• Remove the 4: the result is 132.
• Remove the 3: the result is 142.
• Remove the 2: the result is 143.

The smallest result is 132, which comes from removing the 4. Look at why. The 4 is bigger than the 3 that comes right after it. Removing the 4 puts the 3 in its place, and the 3 is smaller than a 4. The number gets smaller at the first place where it changes.

The rule for one removal is: find the first digit that is bigger than the digit after it, and remove it. If no digit is bigger than the one after it, the number is already rising, so remove the last digit.

The rule for several removals is the same, applied again and again. Once you remove one digit, the digit before the gap can now be compared with the digit after the gap. That is why a stack works. The stack holds the digits you have decided to keep so far. When a new digit arrives that is smaller than the top of the stack, the top digit should go, if you still have removals left.

Here is the full procedure, in plain words:

1. Go through the digits from left to right.
2. For each digit, while you still have removals left, and the stack is not empty, and the top of the stack is bigger than the new digit, pop the top. Each pop uses one removal.
3. Push the new digit onto the stack.
4. When you reach the end, if removals are still left, remove digits from the top of the stack. The stack is rising, so the largest digits are at the top.
5. Remove leading zeros. If nothing is left, the answer is 0.

Why the greedy rule is safe

The greedy rule removes the first place where a digit is bigger than the digit after it. Here is why that is the best choice.

The left-most digit matters most. If two candidate numbers have the same length, the one with the smaller first digit is smaller, no matter what comes after. So the first place to improve is the left end. Removing a digit at position p moves every digit after it one place left, and the digit that lands at position p decides the comparison. When the digit at p is bigger than the one after it, removing it puts a smaller digit at p. Doing this as early as it helps is the best use of a removal.

The stack keeps this property at every step. Everything in the stack is already the best choice for its place, given the removals used so far. When a new digit arrives and it is smaller than the top, the top is worse than the new digit in the same place, so removing it is the best move. When the stack is rising and removals are left, the digits at the top are the largest, so removing them makes the number smallest.

This is a plain argument, not a formal proof. You can also check the method by brute force, which a later section shows.

Worked example 1: 1432219 with three removals

Here is the scan step by step. "Removals left" starts at 3. The stack is shown with spaces between its digits, bottom first.

The scan ends with no removals left, and the stack holds 1219. That is the answer. The table shows why. The 4 was removed because the 3 after it was smaller. The 3 was removed because the 2 after it was smaller. The first 2 stayed, because the second 2 is the same size. The second 2 was removed because the 1 after it was smaller. The 9 at the end was kept, because nothing was left to remove.

Writing it in Python

Here is the full program. It uses a list as the stack. The function takes a string of digits and a number of removals, and it returns the smallest string it can make.

Save the file and run it with python3 file.py. Python reads the file top to bottom and runs the code under if __name__ == "__main__":. That line means the prints run only when you run the file directly. If another file imports remove_k_digits, the prints do not run.

The output is:

1219
12
200
0
4321
0

Some details matter here.

The while condition checks three things, in this order: there are removals left, the stack is not empty, and the top is bigger than the digit. The order matters. If the stack is empty, stack[-1] has no value to read, and Python stops the program with an error. The check stack comes before the comparison. An empty list counts as false in Python, so and stops at that point and never reads stack[-1]. The same rule is used in Java, where && also stops at the first false part.

The comparison stack[-1] > digit compares two one-character strings. Python compares them character by character, so "4" > "3" is True.

Strings cannot be changed in place. The answer is built with "".join(stack). The method join glues the items of a list together into one string. The text between the quotes is what goes between the items, here nothing.

The line stack = stack[:-to_remove] keeps every item except the last to_remove items. A slice like stack[:-2] means "from the start up to, but not including, the second item from the end". The if in front of it is needed. The mistakes section shows what happens without it.

The method lstrip("0") removes zeros from the left end of the text only. It stops at the first character that is not 0. Then result or "0" returns "0" when the text is empty. An empty string counts as false in Python, so or picks the right side.

The type hints num: str, k: int, and -> str say what type each value should be. Python does not check them when the program runs. They help people and editors read the code. The mistakes section shows a case where a wrong type causes an error anyway.

For a trace, here is a copy of the same loop that prints the stack after each digit. This trace code is not part of the program above.

The output shows the first case from worked example 1, and then the 10200 case from worked example 3:

digit 1: stack '1'          removals left 3
digit 4: stack '1 4'        removals left 3
digit 3: stack '1 3'        removals left 2
digit 2: stack '1 2'        removals left 1
digit 2: stack '1 2 2'      removals left 1
digit 1: stack '1 2 1'      removals left 0
digit 9: stack '1 2 1 9'    removals left 0
digit 1: stack '1'          removals left 1
digit 0: stack '0'          removals left 0
digit 2: stack '0 2'        removals left 0
digit 0: stack '0 2 0'      removals left 0
digit 0: stack '0 2 0 0'    removals left 0

Worked example 2: removals that come from the end

Take 1234 with two removals. Every digit is bigger than the one before it, so no pop happens during the scan. The stack ends up as 1 2 3 4, and there are two removals left.

The stack is rising, so the largest digits are at the end. The last two digits, 3 and 4, are removed from the top. The answer is 12.

This is the reason for the if block after the scan. A scan alone would give 1234, which still has four digits, not two. The slice removes the rest.

Worked example 3: a falling sequence and leading zeros

Take 7654321 with three removals. Each digit is smaller than the one before it, so each new digit pops the one below it.

• 7 is pushed. Removals left: 3.
• 6 pops 7, then 6 is pushed. Removals left: 2.
• 5 pops 6, then 5 is pushed. Removals left: 1.
• 4 pops 5, then 4 is pushed. Removals left: 0.
• 3, 2 and 1 are pushed, because no removals are left.

The stack holds 4 3 2 1, which is the answer 4321.

Now take 10200 with one removal. This example shows leading zeros.

• 1 is pushed.
• 0 pops 1, which uses the only removal. Then 0 is pushed. The stack is 0.
• 2 is pushed. The stack is 0 2.
• 0 is pushed. The stack is 0 2 0.
• 0 is pushed. The stack is 0 2 0 0.

The stack spells 0200. The leading 0 has no value, so lstrip("0") removes it, and the answer is 200.

Look at 10, with one removal. The 1 is popped by the 0, and the stack is 0. The lstrip call removes that 0, leaving an empty string. The or "0" part turns the empty string into "0", which is the answer when every digit is removed.

Common mistakes

The first mistake is forgetting to strip leading zeros. If you return the joined stack as it is, 10200 with one removal gives 0200. A version that skips the strip step looks like this:

def no_strip(num: str, k: int) -> str:
    stack = []
    to_remove = k
    for digit in num:
        while to_remove > 0 and stack and stack[-1] > digit:
            stack.pop()
            to_remove -= 1
        stack.append(digit)
    if to_remove > 0:
        stack = stack[:-to_remove]
    return "".join(stack)

Its output on 10200 with one removal is:

0200

That is wrong, because the number is 200. Leading zeros do not change the value, but they do change the text.

The second mistake is forgetting the final step that removes digits from the end. Take 1234 with two removals. The scan alone leaves 1234, which has four digits, and the method must return two. A version with the final step removed returns the wrong answer:

def no_final_step(num: str, k: int) -> str:
    stack = []
    to_remove = k
    for digit in num:
        while to_remove > 0 and stack and stack[-1] > digit:
            stack.pop()
            to_remove -= 1
        stack.append(digit)
    return "".join(stack).lstrip("0") or "0"

Its output on 1234 with two removals is:

1234

The third mistake is reading the top of an empty stack. Here is a short program with that bug:

stack = []
digit = "3"
if stack[-1] > digit:
    print("never")

The real output is:

Traceback (most recent call last):
  File "/home/chiranjeet/dev/anisha/scratch-offtmp/claude-port-greedy/k11_empty.py", line 3, in <module>
    if stack[-1] > digit:
       ~~~~~^^^^
IndexError: list index out of range

The last line gives the error type, IndexError, and the message. An index error means you asked for a position that is not in the list. The path and line number depend on where the file is saved. The fix is to check stack before the comparison, as the method above does.

The fourth mistake is removing the if before the slice. The slice stack[:-to_remove] is only correct when to_remove is at least 1. When to_remove is 0, the expression stack[:-0] means stack[:0], and that is an empty list. Here is the version without the if:

def slice_always(num: str, k: int) -> str:
    stack = []
    to_remove = k
    for digit in num:
        while to_remove > 0 and stack and stack[-1] > digit:
            stack.pop()
            to_remove -= 1
        stack.append(digit)
    stack = stack[:-to_remove]
    return "".join(stack).lstrip("0") or "0"

Its output on 1234 with zero removals is:

0

The answer should be 1234. The if block fixes this.

The fifth mistake is popping when the top is equal to the new digit. The rule uses a strict >, which means bigger. If you change it to >=, the method pops equal digits too. Take 112 with one removal. The method with >= returns 12, and the correct answer is 11. Exercise 5 below asks you to explain this case.

The sixth mistake is turning the answer into an int to remove the zeros. An int(...) call would remove leading zeros on its own, but it fails on long inputs. Python 3.11 and later limit how many digits an int can be made from text. In Python 3.14, the version used to check this lesson, the limit is 4300 digits. Here is a longer input:

int("1" * 5000)

The real output is:

Traceback (most recent call last):
  File "/home/chiranjeet/dev/anisha/scratch-offtmp/claude-port-greedy/k11_int.py", line 1, in <module>
    int("1" * 5000)
    ~~~^^^^^^^^^^^^
ValueError: Exceeds the limit (4300 digits) for integer string conversion: value has 5000 digits; use sys.set_int_max_str_digits() to increase the limit

The string methods used in the lesson have no such limit, so keep the answer as text.

Checking with brute force

A brute-force check tries every possible answer and keeps the best one. It is slow for long inputs, but it is simple enough to trust. For 1432219 with three removals, the number of digits to keep is four. The check tries every way to pick four positions out of seven. The standard library function itertools.combinations makes those picks for you.

from itertools import combinations
 
 
def brute(num: str, k: int) -> str:
    keep = len(num) - k
    candidates = []
    for positions in combinations(range(len(num)), keep):
        text = "".join(num[i] for i in positions).lstrip("0")
        candidates.append(text or "0")
    return min(candidates, key=lambda s: (len(s), s))

The key lambda s: (len(s), s) tells min how to compare two candidates. It compares the length first, so a shorter number is smaller. For two numbers of the same length, it compares the text, and that gives the same answer as comparing the numbers. The lambda is a small unnamed function.

A check ran both functions on 5000 random strings of digits. Each string had between 1 and 8 digits, and each removal count was between 0 and the length of the string. The random generator used a fixed seed, so the same cases come up each time.

import random
 
rng = random.Random(7)
mismatches = 0
for _ in range(5000):
    n = rng.randint(1, 8)
    num = "".join(rng.choice("0123456789") for _ in range(n))
    k = rng.randint(0, n)
    if remove_k_digits(num, k) != brute(num, k):
        mismatches += 1
print("all 5000 random cases match brute force" if mismatches == 0 else f"{mismatches} mismatches")

The output is:

all 5000 random cases match brute force

Practice

Exercise 1. Trace 5337 with two removals by hand. Write the stack after each digit and the removals left.

Show the answer

The 5 is pushed. The 3 pops 5, which leaves one removal, and then 3 is pushed. The next 3 is not smaller than the top 3, so it is pushed too, and the stack is 3 3. The 7 is pushed, so the stack is 3 3 7 with one removal left. The end of the scan removes the top digit, 7. The answer is 33.

Exercise 2. What does the method return for 100 with one removal? Explain the answer in terms of the stack.

Show the answer

The first 1 is pushed. The 0 pops it, using the one removal, and then the 0 is pushed. The next 0 is pushed too. The stack is 0 0. The leading zeros are removed, and nothing is left, so the answer is 0.

Exercise 3. What does the method return for 4321 with four removals?

Show the answer

Every digit is smaller than the one before it, so each digit after the first pops the one below. Three pops happen during the scan, leaving 1. The final step removes that digit, and the stack is empty. The strip step has nothing to strip, and the method returns the text 0, which is the answer when every digit is removed.

Exercise 4. Rewrite the method so that it uses a string as the stack instead of a list. Then run it on 1432219 with three removals and on 10200 with one removal.

Show the answer

A string cannot be changed in place, so each pop makes a new, shorter string with a slice. Here is the version:

def remove_k_digits_text(num: str, k: int) -> str:
    stack = ""
    to_remove = k
    for digit in num:
        while to_remove > 0 and stack and stack[-1] > digit:
            stack = stack[:-1]
            to_remove -= 1
        stack += digit
    if to_remove > 0:
        stack = stack[:-to_remove]
    return stack.lstrip("0") or "0"

The real output is 1219 for the first input and 200 for the second. The code is correct, but each pop copies the whole string. A list pop does not copy, so the list version is faster on long inputs.

Exercise 5. Change > to >= in the method, and explain, in plain words, why 112 with one removal should give 11, not 12.

Show the answer

The number 11 is smaller than 12, because the first digits are equal and the second digit 1 is less than 2. To get 11, remove one of the 2s. The rule with > does that, because it does not pop equal digits. It keeps both 1s and then removes the last digit 2 at the end. The rule with >= pops the first 1 when the second 1 arrives. It keeps the 2, and the result 12 is larger.

Summary

• Use a list as a stack that keeps its digits rising from bottom to top.
• For each new digit, pop the top while removals are left, the stack is not empty, and the top is bigger than the new digit.
• When the scan ends, remove the remaining removals from the top of the stack, using a slice guarded by an if.
• Strip leading zeros with lstrip("0"), and return "0" if nothing is left.
• Check the stack is not empty before reading stack[-1], or the program stops with an IndexError.