Remove K Digits | Leetcode 402 | Optimal Stack Solution

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

Here’s the [Problem Link] to begin with.

Example 1:

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.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Constraints:

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

Optimal Approach: Greedy + Monotonic Increasing Stack

Intuition

• Traverse digits left to right.
• Maintain a stack of digits in non-decreasing order.
• For each digit:
  • While k > 0 and the last digit in stack > current digit, pop the stack (remove that larger digit) and decrement k.
  • Push the current digit.
• After traversal, if k > 0, remove the remaining digits from the end (they’re the largest tail).
• Finally, strip leading zeros. If the result is empty, return "0".

This guarantees the lexicographically smallest result for the given number of deletions.

Code

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        for digit in num:
            # Greedily remove larger preceding digits to minimize number
            while k > 0 and len(stack) != 0 and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)
        # If k > 0, remove from the end
        while k > 0:
            stack.pop()
            k -= 1
        # Build result and remove leading zeros
        result = "".join(stack).lstrip("0")
        if len(result) != 0:
            return result
        return "0"

How the Code Works (Conceptual Walkthrough)

• The while loop inside the traversal removes any descending pair (prev > current) while we still have deletions left, this is the greedy step ensuring earlier digits are as small as possible.
• If removals remain after scanning all digits, we trim from the right since the suffix holds the largest remaining digits.
• lstrip("0") ensures the result has no leading zeros; if stripped to empty, return "0".

Dry Run Examples

• Input: num = “1432219”, k = 3
  Steps: remove ‘4’ (since 1<4), then remove ‘3’ (after 12 vs 132…), then remove ‘2’ → result becomes “1219”.
• Input: num = “10200”, k = 1
  Remove ‘1’? No—‘1’ ≤ ‘0’ is false but next comparison pops ‘1’ when encountering ‘0’ (since 1>0). Stack builds → "0200" → strip leading zeros → “200”.
• Input: num = “10”, k = 2
  Remove both digits → empty → “0”.

Time and Space Complexity

• Time: O(n) – each digit is pushed at most once and popped at most once.
• Space: O(n) – for the stack and result string.

Common Pitfalls and Tips

• Don’t forget to handle the case where k remains after the main loop, remove from the end.
• Always strip leading zeros; return “0” if the result is empty.
• The stack must be non-decreasing to maintain the smallest possible prefix.

When to Use This Pattern

• Any problem where you need the smallest/lexicographically smallest result after removing k elements while preserving order often hints at a monotonic stack (e.g., “remove k digits,” “build smallest subsequence,” etc.).

This solution is concise, greedy-optimal, and linear time, perfect for interviews and production.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.