DSA Removing K Digits

The problem

Remove K Digits asks for the smallest number left after deleting exactly k digits from a digit string. The remaining digits keep their original order. No digit may move.

The answer is a string, not a number. Leading zeros are stripped at the end. A result with nothing left is reported as the single digit zero.

cases = [
    ("1432219", 3, "1219"),
    ("10200", 1, "200"),
    ("10", 2, "0"),
    ("12345", 2, "123"),
]
for num, k, expected in cases:
    print("num", num, "remove", k, "->", expected)

Read one row at a time. The first row deletes three digits and keeps 1219. The second row deletes the 1, and the zero that surfaces at the front is stripped later.

Intuition: an early digit outweighs a later one

A digit near the front shapes the value far more than a digit near the back. Deleting a large early digit helps more than deleting a large late digit. Position matters as much as size.

That fact breaks the first idea many readers try. The idea deletes the k largest digits wherever they sit. Size alone ignores position, and the code below shows the cost.

num = "1432219"
k = 3
biggest = sorted(num, reverse=True)[:k]
rest = list(num)
for d in biggest:
    rest.remove(d)
by_size = "".join(rest)
print("deleted the largest:", biggest)
print("result by size:", by_size)
print("best possible result: 1219")
print("by size is bigger:", int(by_size) > 1219)

Deleting 9, 4 and 3 leaves 1221. The winning answer keeps the 9 and deletes 4, 3 and a 2 instead. An early small digit is worth more than a late large deletion.

Brute force: try every choice of digits to delete

The brute force lists every set of k positions to delete. Each choice leaves one candidate string. The smallest candidate wins.

Candidates are compared as numbers, not as raw strings. Stripping leading zeros first makes the comparison fair. Two candidates then compare by length, and equal lengths compare digit by digit.

from itertools import combinations

def smallest_after_removal(num, k):
    checked = 0
    best = None
    positions = range(len(num))
    for drop in combinations(positions, k):
        checked += 1
        kept = "".join(num[i] for i in positions if i not in drop)
        kept = kept.lstrip("0") or "0"
        if best is None or (len(kept), kept) < (len(best), best):
            best = kept
    return best, checked

result, checked = smallest_after_removal("1432219", 3)
print("result:", result)
print("choices checked:", checked)
result, checked = smallest_after_removal("10200", 1)
print("result:", result)
print("choices checked:", checked)

Seven digits with three deletions hold 35 choices. Ten digits with five deletions hold 252. The choice count explodes long before the digit count looks large.

The optimal solution: a stack that drops a larger digit before a smaller one

The method in one sentence: walk the digits once with a stack, and whenever a smaller digit arrives, pop larger digits off the stack while deletions remain. The stack is monotonic, which means its digits never fall from one entry to the next.

A pop is safe because the arriving digit sits earlier in the final number than the popped digit did. Swapping a larger digit out for a smaller one in an earlier place always lowers the value. Digits left over at the end, when deletions remain, come off the end of the stack.

def remove_k(num, k):
    stack = []
    for d in num:
        while stack and k and stack[-1] > d:
            stack.pop()
            k -= 1
        stack.append(d)
    while k:
        stack.pop()
        k -= 1
    result = "".join(stack).lstrip("0")
    return result or "0"

cases = [
    ("1432219", 3, "1219"),
    ("10200", 1, "200"),
    ("10", 2, "0"),
    ("12345", 2, "123"),
]
for num, k, expected in cases:
    result = remove_k(num, k)
    print("num", num, "remove", k, "->", result, "expected:", expected, "match:", result == expected)

All four cases pass. The rising number 12345 never triggers a pop during the walk. Its two deletions come off the end, which is why its answer is 123.

Walkthrough: 1432219 with three deletions

The walk reads one digit at a time. The state is the stack plus the deletions still available. Each step prints both after the digit is handled.

num = "1432219"
k = 3
stack = []
for d in num:
    while stack and k and stack[-1] > d:
        stack.pop()
        k -= 1
    stack.append(d)
    print("digit", d, "- stack:", "".join(stack), "- deletions left:", k)
print("answer:", "".join(stack).lstrip("0") or "0")

The digit 3 pops the 4. The first 2 pops the 3. The digit 1 pops one 2 and spends the last deletion. The 9 arrives with no deletions left, so it simply joins the stack.

Complexity

The brute force checks every choice of k positions out of n, and building each candidate costs n steps, so its time grows with the choice count times n. The stack walk touches each digit a constant number of times, so its time is O(n).

The brute force stores one candidate at a time, so its extra space is O(n) for that candidate. The stack stores at most n digits, so its space is O(n).

from math import comb

for n, k in ((7, 3), (10, 5), (14, 7)):
    print("digits", n, "delete", k, "- brute choices:", comb(n, k), " stack steps at most:", 2 * n)

Counts beat clocks here. At 14 digits the brute force faces 3432 choices. The stack faces at most 28 pushes and pops, because each digit enters once and leaves once.

Edge cases and pitfalls

Equal digits never pop each other. The pop test is strictly greater, so the first of two equal digits stays. Popping on equal would waste a deletion that a later drop could use better.

Deleting every digit is legal input. The empty stack then answers zero. A k of zero deletes nothing, and only the zero stripping still applies.

def remove_k(num, k):
    stack = []
    for d in num:
        while stack and k and stack[-1] > d:
            stack.pop()
            k -= 1
        stack.append(d)
    while k:
        stack.pop()
        k -= 1
    result = "".join(stack).lstrip("0")
    return result or "0"

print("delete all:", remove_k("10", 2))
print("delete none:", remove_k("100", 0))
print("only zeros left:", remove_k("1000", 1))
print("equal digits, one deletion:", remove_k("221", 1))
print("single digit kept:", remove_k("9", 0))
print("single digit deleted:", remove_k("9", 1))

The 1000 row deletes its 1 during the walk. Three zeros remain, the stripping empties the string, and the fallback answers zero.