The O(n) Club: Remove K Digits with Stack-Fueled Schadenfreude

The O(n) Club: Remove K Digits with Stack-Fueled Schadenfreude

⚡ TL;DR

Want to turn a big, ugly number into its smallest possible self by deleting exactly k digits (while keeping the order)? Resist the brute-force urge—it’s your CPU’s worst nightmare. The savvy fix: Use a stack, pop the loudmouth digits, and keep the meek ones up front. Here’s the quick gist:

// Initialize an empty stack
// For each digit:
//   Pop while (k > 0 & stack.top > digit)
//   Push current digit
// After, remove k digits from end if k remains
// Chop off leading zeros
// If nothing left, return "0"

🧠 How Devs Usually Mess This Up

The classic rookie move? Ripping out the k biggest digits wherever you see them, or doing a single pass pretending each cut is independent. Unfortunately, numbers aren’t a buffet; order is the fussy maître d’. One wrong chop and ‘1432219’ becomes ‘1132219’—not what the algorithm gods demand. Also, please don’t try to brute-force every combination unless you want to set new records on LeetCode’s timeout leaderboard.

🔍 What’s Actually Going On

Think of each digit as a contestant in a ruthless popularity contest—the leftmost digits are the influencers here. Whenever a humble, smaller digit arrives, and you’re still allowed to boot some digits (k > 0), throw out every bigger digit you’ve already kept. This is last-in-first-out greed, powered by the mighty stack. Once the fanfare is over and you’ve traversed all digits, slice off extras from the tail so your number is as sleek as possible. And, of course, leading zeros are fashion faux pas—ditch them unless you’re literally at zero.

🛠️ PseudoCode

• Start with an empty stack:

  StringBuilder stack = new StringBuilder();

• For every digit in the input:
  • While k > 0 and the top of the stack is bigger, pop off the top (ruthless, I know).
  • Add the current digit to the stack.
• If k removals left after the dust settles, delete digits from the end.
• Trim off those pesky leading zeros to look presentable.
• If you erased everything, return “0”—no shame, just minimalism.

💻 The Code

public String removeKDigits(String num, int k) {
    StringBuilder stack = new StringBuilder();
    for (char digit : num.toCharArray()) {
        while (k > 0 && stack.length() > 0 && stack.charAt(stack.length() - 1) > digit) {
            stack.deleteCharAt(stack.length() - 1);
            k--;
        }
        stack.append(digit);
    }
    // If extra removals remain, do some end-of-stack spring cleaning
    stack.setLength(stack.length() - k > 0 ? stack.length() - k : 0);
    // Remove the leading zeros like it's spring cleaning
    int idx = 0;
    while (idx < stack.length() && stack.charAt(idx) == '0') idx++;
    String result = stack.substring(idx);
    return result.length() == 0 ? "0" : result;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Leading zeros: Trust me, nobody wants to see ‘000123’.
• Remove from the end if you run out of better ideas (aka, left with k > 0).
• If you delete every digit, the answer is not existential dread—it’s just ‘0’.
• Efficiency: O(n) time, O(n) space. Your interviewer will not sigh heavily here.

🧠 Interviewer Brain-Tattoo

“If you want to see brute force cry, give it this problem. Stacks: for when being greedy is actually a virtue.”