Remove K Digits | Monotonic Stack | Stack

Overview

Remove k digits: given a non-negative integer as a string and k, remove k digits so the remaining number is as small as possible (order preserved). Monotonic stack: keep digits in increasing order; when the current digit is less than the top, popping the top is equivalent to removing that digit. Pop at most k times total; then append remaining digits. Trim leading zeros; return "0" if result is empty.

When to Use

Smallest number after removing k digits — monotonic increasing stack; pop when smaller digit appears.
Largest number after removing k — monotonic decreasing stack.
Build min/max sequence with limited removals — same pattern.

How It Works

Stack holds the "result so far" (digits in order). For each digit: while we still have removals left (k > 0) and stack non-empty and top > current, pop (remove that digit, k--). Then push current. After the scan, if k > 0, pop k times from the end (remove largest remaining). Join stack, trim leading zeros, return "0" if empty.

Example 1: Monotonic Stack (Standard)

function removeKdigits(num: string, k: number): string {
  const stack: string[] = [];
  let rem = k;
  for (const d of num) {
    while (rem > 0 && stack.length > 0 && stack[stack.length - 1] > d) {
      stack.pop(); rem--;
    }
    stack.push(d);
  }
  while (rem > 0) { stack.pop(); rem--; }
  const s = stack.join('').replace(/^0+/, '') || '0';
  return s;
}

Time: O(n). Space: O(n).

Example 2: Step-by-Step Trace

num = "1432219", k = 3. 1: [1]. 4: [1,4]. 3: 4>3, pop 4, rem=2 [1,3]. 2: 3>2, pop 3, rem=1 [1,2]. 2: [1,2,2]. 1: 2>1, pop 2, rem=0 [1,2,1]. 9: [1,2,1,9]. Join "1219". Trim zeros → "1219".

Example 3: Edge Cases

k >= len: remove all → "0".
Leading zeros: "10200", k=1 → "0200" → "200"; or "10", k=2 → "0".
Strictly increasing: "12345", k=2 → no pops during scan; pop 2 from end → "123".
All same: "1111", k=2 → "11".

Example 4: Remove K for Largest Number

Same idea, monotonic decreasing stack: pop while top < current and rem > 0. Then trim leading zeros only if needed (for largest, leading zeros rarely).

Example 5: Fixed Length (Smallest Number of Length n-k)

Equivalent: we must keep exactly n - k digits. So "remove k" and "keep n-k" are the same; the monotonic stack naturally keeps the smallest possible prefix of that length by greedily removing larger digits when a smaller one appears.

Summary

Remove k digits (smallest): monotonic increasing stack; pop while top > current and k > 0; then pop from end if k left; trim leading zeros. See Monotonic Stack.