Remove K Digits

Explanation & Solution

Description

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

Input: num = "1432219", k = 3

Output: "1219"

Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Constraints

1 <= k <= num.length <= 10^5
num consists of only digits
num does not have any leading zeros except for the zero itself

Approach

Stacks pattern

1. Monotonic Increasing Stack

Build a stack that maintains digits in non-decreasing order from bottom to top
When a smaller digit arrives, remove larger digits above it (if removals remain)

2. Greedy Removal

For each digit in num:
While the stack's top is larger than the current digit and we still have removals left:
Pop the top (remove it) and decrement k
Push the current digit

3. Handle Remaining Removals

If we haven't used all k removals after processing all digits, remove from the end of the stack
This handles cases where the number is already in non-decreasing order

4. Clean Up

Strip leading zeros from the result
If the result is empty, return "0"

Key Insight

To minimize the number, we want the leftmost digits to be as small as possible
Removing a larger digit that precedes a smaller digit always produces a smaller number
The monotonic stack greedily ensures the smallest prefix at each step
Time: O(n), Space: O(n)

Solution Code

Validate Stack Sequences

Flatten Nested List Iterator