121. Remove K Digits

🔗 LeetCode Problem: 402. Remove K Digits
📊 Difficulty: Medium
🏷️ Topics: String, Stack, Greedy, Monotonic Stack

Problem Statement

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

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 zero.

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 <= 10^5 - num consists of only digits - num does not have any leading zeros except for the zero itself

---

🌟 Understanding the Problem

What Are We Really Asking?

Given a number, remove k digits to make it SMALLEST.

Example: num = "1432219", k = 3

Some options after removing 3 digits:
  Remove 1,4,3 → "32219"
  Remove 4,3,2 → "12219"
  Remove 4,2,2 → "13219"
  Remove 4,3,1 → "2229"
  Remove 4,3,9 → "12212"
  ...many more!

Which gives SMALLEST number?
  "1219" (remove 4, 3, 2)

Key Insight: We want the SMALLEST number, not just any number!

---

💡 Building Intuition

Question 1: What Makes a Number Smaller?

Compare two numbers of same length:
  "5432" vs "1234"

Which is smaller? "1234"
Why? First digit matters most!

In "5432":
  If we can make first digit smaller, whole number becomes smaller!

Question 2: When Should We Remove a Digit?

Think about this:

Number: "1432"

Look at each digit:
  1: Next digit is 4 (1 < 4) → Keep 1
  4: Next digit is 3 (4 > 3) → Remove 4! ← Peak!
  3: Next digit is 2 (3 > 2) → Remove 3! ← Peak!
  2: No next digit

Pattern: Remove digit when it's GREATER than next digit!

Another example:

Number: "12345"

1 < 2 → Keep
2 < 3 → Keep
3 < 4 → Keep
4 < 5 → Keep

All increasing! No removals yet!
What if k=2?
  Remove from end: "123"

The Key Pattern:

Greedy approach from left to right:
  If current digit > next digit:
    Remove current digit (it's a "peak")

  This ensures leftmost digits are as small as possible!

Question 3: What About Leading Zeros?

Number: "10200", k = 1

Remove '1' → "0200"
But "0200" is actually "200" (remove leading zeros)

Number: "10", k = 2
Remove all → "" (empty)
But we need to return "0" for empty!

---

🎯 Approach 1: Try All Combinations (Brute Force)

The Idea

Try removing all possible k digits.
Find which gives smallest number.

Implementation

public String removeKdigits(String num, int k) {
    // This would require trying C(n, k) combinations
    // Generate all subsets of size (n - k)
    // Find minimum

    // Too slow! Not practical to implement
    // Just for understanding

    return ""; // Placeholder
}

Complexity Analysis

⏰ Time: O(C(n, k) × n) = Exponential!

💾 Space: O(n)

The Problem

For num.length = 100, k = 50:
  C(100, 50) ≈ 10^29 combinations!

Completely impractical!

---

🎯 Approach 2: Greedy with StringBuilder (Better)

The Idea

Build result greedily from left to right:
  - For each digit, remove previous digits if they're larger
  - Keep track of how many we've removed
  - Handle leading zeros

Implementation

public String removeKdigits(String num, int k) {
    int n = num.length();

    // Edge case: remove all digits
    if (k == n) return "0";

    StringBuilder result = new StringBuilder();
    int toRemove = k;

    for (int i = 0; i < n; i++) {
        char digit = num.charAt(i);

        // Remove digits from result while:
        // 1. We still need to remove digits (toRemove > 0)
        // 2. Result is not empty
        // 3. Last digit in result > current digit
        while (toRemove > 0 && result.length() > 0 && 
               result.charAt(result.length() - 1) > digit) {
            result.deleteCharAt(result.length() - 1);
            toRemove--;
        }

        result.append(digit);
    }

    // If we still need to remove digits, remove from end
    while (toRemove > 0) {
        result.deleteCharAt(result.length() - 1);
        toRemove--;
    }

    // Remove leading zeros
    while (result.length() > 0 && result.charAt(0) == '0') {
        result.deleteCharAt(0);
    }

    // Handle empty result
    return result.length() == 0 ? "0" : result.toString();
}

Complexity Analysis

⏰ Time: O(n) - Each digit processed once

💾 Space: O(n) - StringBuilder storage

Detailed Dry Run

Input: num = "1432219", k = 3

═══════════════════════════════════════════════════════════
Initial State
═══════════════════════════════════════════════════════════

result = ""
toRemove = 3
n = 7

═══════════════════════════════════════════════════════════
i=0, digit='1'
═══════════════════════════════════════════════════════════

While loop check:
  toRemove > 0? 3 > 0? YES
  result.length() > 0? 0 > 0? NO

  Don't enter while loop

Append '1':
  result = "1"
  toRemove = 3

═══════════════════════════════════════════════════════════
i=1, digit='4'
═══════════════════════════════════════════════════════════

While loop check:
  toRemove > 0? YES
  result.length() > 0? YES
  result.last() > digit? '1' > '4'? NO

  Don't enter while loop

Append '4':
  result = "14"
  toRemove = 3

═══════════════════════════════════════════════════════════
i=2, digit='3'
═══════════════════════════════════════════════════════════

While loop check:
  toRemove > 0? YES
  result.length() > 0? YES
  result.last() > digit? '4' > '3'? YES ← Enter loop!

Iteration 1:
  Remove last: '4'
  result = "1"
  toRemove = 2

  Loop check again:
    toRemove > 0? YES
    result.length() > 0? YES
    result.last() > digit? '1' > '3'? NO
    Exit while loop

Append '3':
  result = "13"
  toRemove = 2

Explanation:
  We removed '4' because 4 > 3
  Keeping '3' makes number smaller

═══════════════════════════════════════════════════════════
i=3, digit='2'
═══════════════════════════════════════════════════════════

While loop check:
  toRemove > 0? 2 > 0? YES
  result.length() > 0? YES
  result.last() > digit? '3' > '2'? YES ← Enter loop!

Iteration 1:
  Remove last: '3'
  result = "1"
  toRemove = 1

  Loop check again:
    toRemove > 0? YES
    result.length() > 0? YES
    result.last() > digit? '1' > '2'? NO
    Exit while loop

Append '2':
  result = "12"
  toRemove = 1

Explanation:
  We removed '3' because 3 > 2
  Now we've removed 2 digits total (4, 3)
  Still need to remove 1 more!

═══════════════════════════════════════════════════════════
i=4, digit='2'
═══════════════════════════════════════════════════════════

While loop check:
  toRemove > 0? 1 > 0? YES
  result.length() > 0? YES
  result.last() > digit? '2' > '2'? NO

  Don't enter while loop

Append '2':
  result = "122"
  toRemove = 1

═══════════════════════════════════════════════════════════
i=5, digit='1'
═══════════════════════════════════════════════════════════

While loop check:
  toRemove > 0? YES
  result.length() > 0? YES
  result.last() > digit? '2' > '1'? YES ← Enter loop!

Iteration 1:
  Remove last: '2'
  result = "12"
  toRemove = 0

  Loop check again:
    toRemove > 0? 0 > 0? NO
    Exit while loop

Append '1':
  result = "121"
  toRemove = 0

Explanation:
  We removed the last '2' because 2 > 1
  Now we've removed 3 digits total (4, 3, 2)
  toRemove = 0, done removing!

═══════════════════════════════════════════════════════════
i=6, digit='9'
═══════════════════════════════════════════════════════════

While loop check:
  toRemove > 0? 0 > 0? NO

  Don't enter while loop

Append '9':
  result = "1219"
  toRemove = 0

═══════════════════════════════════════════════════════════
Post-processing
═══════════════════════════════════════════════════════════

Remove from end if toRemove > 0:
  toRemove = 0, skip

Remove leading zeros:
  result[0] = '1' != '0', skip

Return: "1219" ✓

Why This Works

We removed: 4, 3, 2
Result: "1219"

Why this is optimal:
  - Removed digits from left when they were peaks
  - Kept leftmost digits as small as possible
  - "1219" is smallest possible after removing 3 digits

---

✅ Approach 3: Monotonic Stack (Optimal & Cleaner)

The Idea

Use a stack to maintain increasing sequence:
  - When new digit is smaller, pop larger digits
  - This automatically builds smallest number
  - Stack naturally handles the greedy logic

Implementation

public String removeKdigits(String num, int k) {
    int n = num.length();

    // Edge case: remove all digits
    if (k == n) return "0";

    Stack<Character> stack = new Stack<>();
    int toRemove = k;

    for (int i = 0; i < n; i++) {
        char digit = num.charAt(i);

        // Pop larger digits while we can remove
        while (toRemove > 0 && !stack.isEmpty() && 
               stack.peek() > digit) {
            stack.pop();
            toRemove--;
        }

        stack.push(digit);
    }

    // Remove remaining digits from end
    while (toRemove > 0) {
        stack.pop();
        toRemove--;
    }

    // Build result
    StringBuilder result = new StringBuilder();
    while (!stack.isEmpty()) {
        result.append(stack.pop());
    }
    result.reverse();

    // Remove leading zeros
    while (result.length() > 0 && result.charAt(0) == '0') {
        result.deleteCharAt(0);
    }

    return result.length() == 0 ? "0" : result.toString();
}

Complexity Analysis

⏰ Time: O(n) - Each digit pushed/popped at most once

💾 Space: O(n) - Stack storage

Detailed Dry Run

Input: num = "10200", k = 1

═══════════════════════════════════════════════════════════
Initial State
═══════════════════════════════════════════════════════════

stack = []
toRemove = 1

═══════════════════════════════════════════════════════════
i=0, digit='1'
═══════════════════════════════════════════════════════════

While loop:
  toRemove > 0? YES
  !stack.isEmpty()? NO

  Don't enter

Push '1':
  stack = ['1']

═══════════════════════════════════════════════════════════
i=1, digit='0'
═══════════════════════════════════════════════════════════

While loop:
  toRemove > 0? YES
  !stack.isEmpty()? YES
  stack.peek() > digit? '1' > '0'? YES ← Enter!

Iteration 1:
  stack.pop() → remove '1'
  toRemove = 0
  stack = []

  Loop check:
    toRemove > 0? NO
    Exit

Push '0':
  stack = ['0']

═══════════════════════════════════════════════════════════
i=2, digit='2'
═══════════════════════════════════════════════════════════

While loop:
  toRemove > 0? 0 > 0? NO

Push '2':
  stack = ['0', '2']

═══════════════════════════════════════════════════════════
i=3, digit='0'
═══════════════════════════════════════════════════════════

While loop:
  toRemove > 0? NO

Push '0':
  stack = ['0', '2', '0']

═══════════════════════════════════════════════════════════
i=4, digit='0'
═══════════════════════════════════════════════════════════

While loop:
  toRemove > 0? NO

Push '0':
  stack = ['0', '2', '0', '0']

═══════════════════════════════════════════════════════════
Post-processing
═══════════════════════════════════════════════════════════

Remove from end:
  toRemove = 0, skip

Build result:
  Pop all: '0', '0', '2', '0'
  result = "0020"
  Reverse: "0200"

Remove leading zeros:
  '0' == '0'? YES, remove
  result = "200"
  '2' == '0'? NO, stop

Return: "200" ✓

---

📊 Approach Comparison

┌──────────────────────────────────────────────────────────┐
│             Approach 1    Approach 2       Approach 3    │
│             (Brute)       (StringBuilder)  (Stack)       │
├──────────────────────────────────────────────────────────┤
│ Strategy    Try all       Greedy build    Monotonic     │
│             combos        with removal    stack          │
│                                                           │
│ Time        Exponential   O(n) ✓          O(n) ✓        │
│                                                           │
│ Space       O(n)          O(n)            O(n)           │
│                                                           │
│ Code        Complex       Medium          Clean ✓       │
│ simplicity                                               │
│                                                           │
│ Interview   Never         Acceptable      Preferred ✓   │
│             use                                          │
└──────────────────────────────────────────────────────────┘

Which Approach to Use?

Both Approach 2 and 3 are good!

Approach 2 (StringBuilder):
  ✓ Slightly more direct
  ✓ No reverse needed at end

Approach 3 (Stack):
  ✓ Cleaner conceptually
  ✓ Shows monotonic stack pattern
  ✓ Easier to explain in interview

Either is acceptable! Pick what you're comfortable with.

---

🧪 Edge Cases

Edge Case 1: Remove All Digits

Input: num = "12345", k = 5
Output: "0"

All digits removed → return "0" ✓

Edge Case 2: All Increasing

Input: num = "12345", k = 2
Output: "123"

No peaks to remove!
Remove from end ✓

Edge Case 3: All Decreasing

Input: num = "54321", k = 2
Output: "321"

Remove from front greedily:
  Remove 5 (5 > 4)
  Remove 4 (4 > 3)
Result: "321" ✓

Edge Case 4: Leading Zeros

Input: num = "10200", k = 1
Output: "200"

Remove '1' → "0200"
Strip leading zeros → "200" ✓

Edge Case 5: All Zeros

Input: num = "0000", k = 2
Output: "0"

After removing 2 zeros: "00"
Strip leading zeros: ""
Return "0" for empty ✓

Edge Case 6: Single Digit

Input: num = "9", k = 1
Output: "0"

Remove only digit → return "0" ✓

---

⚠️ Common Mistakes

Mistake 1: Not handling toRemove at end

// ❌ WRONG - Might not remove k digits
for (char c : num.toCharArray()) {
    while (toRemove > 0 && !stack.isEmpty() && stack.peek() > c) {
        stack.pop();
        toRemove--;
    }
    stack.push(c);
}
// Forgot: what if toRemove > 0 still?

// ✓ CORRECT - Remove from end if needed
while (toRemove > 0) {
    stack.pop();
    toRemove--;
}

Mistake 2: Not handling leading zeros

// ❌ WRONG - Returns "0200"
return result.toString();

// ✓ CORRECT - Remove leading zeros
while (result.length() > 0 && result.charAt(0) == '0') {
    result.deleteCharAt(0);
}
return result.length() == 0 ? "0" : result.toString();

Mistake 3: Not handling empty result

// ❌ WRONG - Returns empty string
return result.toString();

// ✓ CORRECT - Return "0" for empty
return result.length() == 0 ? "0" : result.toString();

Mistake 4: Wrong comparison operator

// ❌ WRONG - Uses >=
while (stack.peek() >= digit) {
    // Removes equal digits too!
}

// ✓ CORRECT - Use >
while (stack.peek() > digit) {
    // Only removes larger digits
}

---

🎯 Pattern Recognition

When you see:

- "remove k elements to minimize/maximize"
- "build smallest/largest number"
- "greedy removal from sequence"
- "maintain increasing/decreasing order"

Think:
  "Monotonic stack!"
  "Greedy approach from left to right"

Similar Problems: - Next Greater Element (LC 496) - Daily Temperatures (LC 739) - Largest Rectangle in Histogram (LC 84) - Create Maximum Number (LC 321)

---

📝 Quick Revision Notes

🎯 Core Concept

Remove k digits to make number smallest. Greedy approach: scan left to right, remove digit when current > next (it's a peak). Use monotonic stack to maintain increasing sequence. Handle leading zeros and empty result.

⚡ Quick Implementation (Approach 3 - Stack)

import java.util.Stack;

class Solution {
  public String removeKdigits(String num, int k) {
    // Base case for early exit.
    if(num.length() == k) {
      return "0"; // can remove all digits
    }

    // Find the minimal number.    
    Stack<Character> stack = new Stack<>();
    for(char ch : num.toCharArray()) {
      // while stack top is still greater than incoming digit, pop it and push the current one.
      // check: still stack not empty and k > 0.
      while (!stack.empty() && k >= 1 && stack.peek() > ch) {
        stack.pop();
        k--;
      }
      // at last push
      stack.push(ch);
    }

    // If still k is not 0, remove last k.
    // For example, in "112" and k = 1, all (1,1,2) will remain in stack. 2 can be removed.
    while (k > 0) {
      stack.pop();
      k--;
    }

    // Form the string from stack.
    StringBuilder sb = new StringBuilder();
    for(char ch : stack) {
      sb.append(ch);
    }

    // Remove the leading 0s.
    // GOTCHA: simple for loop with sb.deleteCharAt(i) will not work as sb updates 
    // immediately and gives us very wrong results.
    while (sb.length() > 0 && sb.charAt(0) == '0') {
      sb.deleteCharAt(0);
    }

    // to handle use case when num = 10 and k = 1.
    // Till above loop, sb is 0 and it becomes empty due to above. We return empty string which is wrong.
    // Hence we need to check like below to handle the above use case.
    return sb.length() == 0 ? "0" : sb.toString();
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.removeKdigits("1432219", 3).equals("1219"));
    System.out.println(s.removeKdigits("10200", 1).equals("200"));
    System.out.println(s.removeKdigits("10", 2).equals("0"));    
    System.out.println(s.removeKdigits("10", 1).equals("0"));    
    System.out.println(s.removeKdigits("112", 1).equals("11"));    
    System.out.println(s.removeKdigits("33526221184202197273", 19));    
  }
}

🔑 Key Insights

• Pattern: Monotonic Stack (Greedy)
• Strategy: Remove peaks (digit > next)
• Data Structure: Stack for increasing sequence
• Greedy Rule: Leftmost digits matter most
• Post-processing: Remove from end, strip leading zeros
• Edge Cases: All removed → "0", empty → "0"
• Time: O(n) - each digit pushed/popped once
• Space: O(n)

🎪 Memory Aid

"Remove the peaks from left to right!"
"Stack keeps it increasing!"
"Don't forget: end removal and leading zeros!" ✨

⚠️ Don't Forget

• Use > not >= when comparing
• Remove remaining from end if toRemove > 0
• Strip leading zeros
• Return "0" for empty result
• Handle k == n case

---

Happy practicing! 🎯

Note: This is a great monotonic stack problem! The greedy insight (remove peaks) is key. Common at Amazon, Meta! 💪✨