Remove K Digits — Monotonic Stack Visualization

The Problem

Given a string num representing a non-negative integer and an integer k, remove k digits from the number so that the resulting number is the smallest possible.

Return the smallest number as a string. The result must not contain leading zeros (except when the result is "0").

Interactive Visualization

Number String

K (removals)

Preset

Speed:

Removals remaining: 3

Digit Array

Monotonic Stack

Empty — digits will be pushed here

bottom

Result

—

Status & Log

Press Step or Play to begin.

Code

fun removeKdigits(num: String, k: Int): String {    val stack = mutableListOf<Char>()    var k = k    for (digit in num) {        while (k > 0 && stack.isNotEmpty() && stack.last() > digit) {            stack.removeLast()            k-- }        stack.add(digit) }    // Remove remaining from end    val result = stack.subList(0, stack.size - k)    return result.joinToString("").trimStart('0').ifEmpty { "0" } }

def removeKdigits(num, k):    stack = []    for digit in num:        while k > 0 and stack and stack[-1] > digit:            stack.pop()            k -= 1        stack.append(digit)    # Remove remaining from end    stack = stack[:-k] if k else stack    return ''.join(stack).lstrip('0') or '0'

How It Works

Greedy Strategy

The key insight is that to make the resulting number as small as possible, we want the most significant positions (leftmost digits) to be as small as possible. Whenever we encounter a digit that is smaller than the previous digit on the stack, we should remove that previous larger digit — it occupies a more significant position and makes the number larger.

Monotonic Increasing Stack

We maintain a monotonic increasing stack. As we iterate through each digit of the input number, we compare it with the top of the stack. If the stack top is greater than the current digit and we still have removals left (k > 0), we pop the stack top (removing that digit) and decrement k. We repeat this while the condition holds. Then we push the current digit.

Algorithm Steps

Initialize an empty stack and iterate through each digit in the number string.
While k > 0, the stack is not empty, and the stack top is greater than the current digit: pop from the stack and decrement k.
Push the current digit onto the stack.
After the loop: If k > 0 removals remain, trim k digits from the end of the stack (these are the largest trailing digits).
Strip leading zeros and return the result (or "0" if the result is empty).

Complexity

Time O(n)

Space O(n)

Each digit is pushed and popped from the stack at most once, giving O(n) total operations. The stack can hold at most n digits, so space is O(n). This is optimal since we must examine every digit at least once.