L14. Remove K Digits | Stack and Queue Playlist

This chapter explores how to solve the classic "Remove K Digits" algorithmic problem using a Monotonic Stack. The objective is to remove a specified number of digits ($K$) from a given numeric string such that the resulting integer is as small as possible.

1. Problem Statement & Objective

Given a string num containing numeric digits from 0 to 9 and an integer K, your goal is to remove exactly $K$ digits from num so that the remaining digits form the smallest possible number.

Example Walkthrough

• Input: num = "1432219", $K = 3$
• Possible Removals:
  • Removing 4, 3, and 1 yields 1229.
  • Removing 4, 3, and 2 yields 1219.
• Optimal Result: 1219 (Since $1219 < 1229$).

2. Core Mental Model & Greedy Intuition

To make a number as small as possible, the most significant digits (the digits at the very beginning / left side) must be as small as possible. If a larger digit appears before a smaller digit, keeping the larger digit at a higher place value makes the entire number unnecessarily large.

The Greedy Strategy

1. Prioritize the Leftmost Digits: Keep smaller digits at the start and aggressively get rid of larger digits.
2. Monotonic Increasing Stack: Maintain a stack of digits. Before pushing a new digit, compare it with the element at the top of the stack. If the stack's top element is greater than the current digit, pop it (remove the larger digit) and decrement $K$.
3. Stop Condition: Repeat this pop operation as long as $K > 0$ and the stack top is greater than the current digit.

3. Step-by-Step Evolution of the Algorithm

Let's trace num = "1432219" with $K = 3$:

Wait, let's look closer at the actual flow when processing the final sequence: If we continue standard iteration, after the stack holds [1, 2, 1] and we process 9, we reconstruct and reverse to get 1219.

4. Real-World Practical Edge Cases

Before writing production code, you must handle three critical edge cases:

1. $K$ Equals the Length of the String ($K == n$):
   • If you must remove every single digit, the stack will be completely empty.
   • Action: Return "0" instead of an empty string.
2. Leading Zeros After Reconstruction:
   • If the resulting number contains leading zeros (e.g., stack yields 0010), this is invalid.
   • Action: Trim off all leading zeros from the final string to leave a valid integer representation (10).
3. Exhaustion of $K$ with Monotonically Increasing Digits:
   • If the input string is strictly increasing (e.g., num = "123456", $K = 3$), the stack will never encounter a top element greater than the current digit. Thus, no elements will be popped during traversal.
   • Action: After the traversal loop, if $K > 0$, pop the remaining $K$ elements from the back (top) of the stack, because the largest digits are accumulated at the end of a strictly increasing sequence.

5. Complete Java Implementation

Here is the robust, production-grade code capturing all logic and edge cases discussed:

import java.util.Stack;

class Solution {
    public String removeKdigits(String num, int k) {
        int n = num.length();
        if (k == n) return "0";

        Stack<Character> stack = new Stack<>();

        // Step 1: Traverse through every digit in the string
        for (int i = 0; i < n; i++) {
            char current = num.charAt(i);

            // Pop elements from stack if top is greater than current digit
            // and we still have removals (k > 0) left.
            while (!stack.isEmpty() && k > 0 && stack.peek() > current) {
                stack.pop();
                k--;
            }
            stack.push(current);
        }

        // Step 2: If k is still > 0, remove remaining digits from the top
        while (k > 0 && !stack.isEmpty()) {
            stack.pop();
            k--;
        }

        // Step 3: Extract characters from stack into a StringBuilder
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        
        // Since stack outputs in reverse order, reverse to get correct sequence
        sb.reverse();

        // Step 4: Remove leading zeros
        while (sb.length() > 1 && sb.charAt(0) == '0') {
            sb.deleteCharAt(0);
        }

        // Step 5: Final sanity check if result is empty
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

6. Complete Flow Walkthrough (Code Execution)

7. Complexity Analysis

Summary and Key Takeaways

• Greedy Paradigm: To minimize a number, always eliminate larger digits that appear before smaller digits.
• Monotonic Stack: A stack is the ideal data structure for maintaining historical digit order while allowing efficient removals from the top.
• Constraint Management: Always check whether $K$ has been fully exhausted after the primary traversal loop.
• Edge Case Protection: Handle scenarios where $K$ equals the total string length by returning "0".
• Normalization: Clean up leading zeros post-reversal to ensure mathematical validity of the resulting string number.
• Linear Efficiency: Both time and space complexities scale efficiently at $O(N)$, making this optimal for large numeric strings.