Pattern visualizer
Remove K Digits
Trying every set of k removals is exponential, but position beats value here: the leading digit is worth ten times the next one, so the very first place where a digit is followed by something smaller is always the best place to cut. Sweeping left to right with a stack turns that into one pass — before pushing a digit, pop every larger digit still on top while removals remain, because each pop shrinks an earlier and therefore heavier position. What survives is a non-decreasing run, which is the smallest arrangement reachable. Two loose ends the loop does not cover: if the digits ran uphill the whole way no pop ever fired, so the leftover removals come off the tail where they cost least, and a stack that now starts with zeros needs them stripped, since a number is not written with leading zeros. Each index is pushed once and popped at most once, so the pass is linear. Animated on: num = "10432219", k = 3. Remove exactly 3 digits so the remaining number is as small as possible. Answer: "2219"..
Monotonic non-decreasing stack, greedy from the left
num=10432219, k=3, so 8 - 3 = 5 digits survive. The leftmost digit weighs the most, so the number shrinks fastest by killing the earliest digit that is bigger than the one right after it. Sweep left to right keeping a stack of digits that never goes downhill.
1FUNCTION removeKDigits(num, k):2 stack <- EMPTY3 FOR i <- 0 TO LENGTH(num) - 1:4 WHILE stack NOT EMPTY AND k > 0 AND TOP(stack) > num[i]:5 POP stack6 k <- k - 17 PUSH num[i] ONTO stack8 WHILE k > 0:9 POP stack10 k <- k - 111 STRIP LEADING ZEROS FROM stack12 RETURN JOIN(stack)
← / → step · space play · Home restart