080. Remove K Digits

Why this mechanism works

Earlier digits have greater significance. If a larger retained digit precedes a smaller incoming one and deletion budget remains, removing the larger digit improves the earliest differing position. Keep a nondecreasing stack where budget permits. If budget remains after scanning, remove digits from the right, where they are least useful to retain.

State and boundaries

stack is the best retained prefix under deletions already spent. remaining is the number of required deletions still available.

Protocol

1. Pop larger trailing digits while budget remains.
2. Append the incoming digit.
3. After scanning remove remaining digits from the tail.
4. Strip representation-only leading zeros.
5. Return zero for an empty normalized result.

Visualization

1432219, k=3
4 removed by 3; 3 removed by 2
later 2 removed by 1
retained 1219

Python implementation

def remove_k_digits(number, k):
    stack = []
    remaining = k
    for digit in number:
        while remaining and stack and stack[-1] > digit:
            stack.pop()
            remaining -= 1
        stack.append(digit)
    if remaining:
        del stack[-remaining:]
    return ''.join(stack).lstrip('0') or '0'

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 remove_k_digits: stack = []
number='1432219'; k=3; stack=[]

L3 remove_k_digits: remaining = k
number='1432219'; k=3; stack=[]; remaining=3

L4 remove_k_digits: for digit in number:
number='1432219'; k=3; stack=[]; remaining=3; digit='1'

L8 remove_k_digits: stack.append(digit)
number='1432219'; k=3; stack=['1']; remaining=3; digit='1'

L4 remove_k_digits: for digit in number:
number='1432219'; k=3; stack=['1']; remaining=3; digit='4'

L8 remove_k_digits: stack.append(digit)
number='1432219'; k=3; stack=['1', '4']; remaining=3; digit='4'

L4 remove_k_digits: for digit in number:
number='1432219'; k=3; stack=['1', '4']; remaining=3; digit='3'

L6 remove_k_digits: stack.pop()
number='1432219'; k=3; stack=['1']; remaining=3; digit='3'

... 9 intermediate state changes omitted ...

L7 remove_k_digits: remaining -= 1
number='1432219'; k=3; stack=['1', '2']; remaining=0; digit='1'

L8 remove_k_digits: stack.append(digit)
number='1432219'; k=3; stack=['1', '2', '1']; remaining=0; digit='1'

L4 remove_k_digits: for digit in number:
number='1432219'; k=3; stack=['1', '2', '1']; remaining=0; digit='9'

L8 remove_k_digits: stack.append(digit)
number='1432219'; k=3; stack=['1', '2', '1', '9']; remaining=0; digit='9'

L2 remove_k_digits: stack = []
number='10200'; k=1; stack=[]

L3 remove_k_digits: remaining = k
number='10200'; k=1; stack=[]; remaining=1

L4 remove_k_digits: for digit in number:
number='10200'; k=1; stack=[]; remaining=1; digit='1'

L8 remove_k_digits: stack.append(digit)
number='10200'; k=1; stack=['1']; remaining=1; digit='1'

L4 remove_k_digits: for digit in number:
number='10200'; k=1; stack=['1']; remaining=1; digit='0'

L6 remove_k_digits: stack.pop()
number='10200'; k=1; stack=[]; remaining=1; digit='0'

L7 remove_k_digits: remaining -= 1
number='10200'; k=1; stack=[]; remaining=0; digit='0'

L8 remove_k_digits: stack.append(digit)
number='10200'; k=1; stack=['0']; remaining=0; digit='0'

... 1 intermediate state changes omitted ...

L8 remove_k_digits: stack.append(digit)
number='10200'; k=1; stack=['0', '2']; remaining=0; digit='2'

L4 remove_k_digits: for digit in number:
number='10200'; k=1; stack=['0', '2']; remaining=0; digit='0'

L8 remove_k_digits: stack.append(digit)
number='10200'; k=1; stack=['0', '2', '0']; remaining=0; digit='0'

L8 remove_k_digits: stack.append(digit)
number='10200'; k=1; stack=['0', '2', '0', '0']; remaining=0; digit='0'

Why the solution is correct

Replacing an earlier larger digit with a later smaller digit decreases the number at its first changed position, dominating all later choices. If no such descent remains, deleting from the suffix preserves the smallest available leading digits. Normalization changes representation, not the deletion choice.

Time and space

O(n) time and O(n) stack/output space.

Common mistakes

Using >= spends deletions unnecessarily on equal digits. Leading-zero normalization is separate from the exactly-k deletion budget.

Reasoning card

Transfer exercise

Maximize the number instead. Reverse the dominance comparison and justify the remaining-suffix deletion rule again.