LeetCode 402: Remove K Digits Solution in Python – A Step-by-Step Guide

What Is LeetCode 402: Remove K Digits?

In LeetCode 402: Remove K Digits, you’re given a string num representing a non-negative integer (like "1432219") and an integer k. Your task is to remove exactly k digits to form the smallest possible number, returned as a string. Leading zeros aren’t allowed in the final result (e.g., "021" becomes "21"), and if you remove all digits, you return "0". For example, with "1432219" and k = 3, removing 4, 3, and 2 gives "1219"—the smallest outcome.

Problem Statement

• Input: A string num (the number), an integer k (digits to remove).
• Output: A string—the smallest number after removing k digits.
• Rules:
• Remove exactly k digits.
• No leading zeros in result.
• If result is empty, return "0".

Constraints

• 1 <= k <= num.length <= 10⁵.
• num contains only digits (0-9), no leading zeros unless "0" itself.

Examples

• Input: num = "1432219", k = 3
• Output: "1219".
• Input: num = "10200", k = 1
• Output: "200".
• Input: num = "10", k = 2
• Output: "0".

Understanding the Problem: Shrinking to the Smallest

To solve LeetCode 402: Remove K Digits in Python, we need to erase k digits from num to get the smallest possible number. A naive idea might be to try every combination of removals—but with a string up to 10⁵ digits, that’s way too many options! Instead, we’ll use:

• Best Solution (Monotonic Stack): O(n) time, O(n) space—builds a rising sequence fast.
• Alternative Solution (Greedy Recursion): O(k * n) time, O(n) space—removes digits one by one.

Let’s dive into the monotonic stack solution with a clear, step-by-step explanation.

Best Solution: Monotonic Stack

Why This Is the Best Solution

The monotonic stack method is the star here because it’s fast—O(n) time and O(n) space—and super smart. It builds the smallest number by keeping digits in a stack that only goes up (or stays flat), popping bigger digits when a smaller one comes along, as long as we have removals left. It’s like stacking blocks to keep the pile as low as possible while tossing out the tall ones!

How It Works

Think of the number as a line of digits you’re organizing:

• Step 1: Start with an Empty Stack:
• You’ll build the result digit by digit.
• Step 2: Add Digits, Keep It Small:
• For each digit in num:
• If the stack’s top digit is bigger and we can still remove digits (k > 0), pop it.
• Push the new digit onto the stack.
• This keeps the stack “monotonic” (non-decreasing).
• Step 3: Use Up Remaining Removals:
• If k is still > 0 after all digits, pop from the end.
• Step 4: Clean Up:
• Remove leading zeros from the stack.
• If empty, return "0".
• Step 5: Why This Works:
• Popping bigger digits for smaller ones ensures the leftmost digits (most significant) are as small as possible.
• We stop when we’ve used all k removals or run out of digits to compare.
• It’s like sculpting the smallest number by chiseling away high spots!

Step-by-Step Example

Example: num = "1432219", k = 3

• Start: Stack = [], k = 3.
• Digit 1: Stack = [1], k = 3.
• Digit 4: 1 < 4, push, Stack = [1, 4], k = 3.
• Digit 3: 4 > 3, pop 4 (k = 2), push 3, Stack = [1, 3], k = 2.
• Digit 2: 3 > 2, pop 3 (k = 1), push 2, Stack = [1, 2], k = 1.
• Digit 2: 2 ≤ 2, push, Stack = [1, 2, 2], k = 1.
• Digit 1: 2 > 1, pop 2 (k = 0), push 1, Stack = [1, 2, 1], k = 0.
• Digit 9: k = 0, push, Stack = [1, 2, 1, 9], k = 0.
• Result: Join stack = "1219".

Example: num = "10200", k = 1

• Digit 1: Stack = [1], k = 1.
• Digit 0: 1 > 0, pop 1 (k = 0), push 0, Stack = [0], k = 0.
• Digit 2: Push, Stack = [0, 2], k = 0.
• Digit 0: Push, Stack = [0, 2, 0], k = 0.
• Digit 0: Push, Stack = [0, 2, 0, 0], k = 0.
• Clean: "0200" → "200".
• Result: "200".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        # Step 1: Start with an empty stack
        stack = []

        # Step 2: Process each digit
        for digit in num:
            # While stack isn’t empty, top is bigger, and k > 0, pop
            while stack and stack[-1] > digit and k > 0:
                stack.pop()  # Remove bigger digit
                k -= 1       # Use up one removal
            stack.append(digit)  # Add current digit

        # Step 3: If k > 0, remove from end
        while k > 0 and stack:
            stack.pop()
            k -= 1

        # Step 4: Build result, remove leading zeros
        result = "".join(stack).lstrip("0")

        # Step 5: If empty, return "0"
        return result if result else "0"

• Line 4: Create an empty list to act as our stack.
• Line 7-11: Loop through each digit:
• Line 8-10: If stack has digits, top is bigger than current, and we can remove (k > 0), pop it and decrease k.
• Line 11: Add the current digit (e.g., 1 → [1], then 4 → [1, 4]).
• Line 14-16: If k remains, pop from end (e.g., k = 1, [1, 2, 1, 9] → [1, 2, 1]).
• Line 19: Join stack into string, strip leading zeros (e.g., "0200" → "200").
• Line 22: Return result, or "0" if empty (e.g., "10", k = 2 → "0").
• Time Complexity: O(n)—each digit pushed/popped once.
• Space Complexity: O(n)—stack stores up to n digits.

This is like sculpting the smallest number with a stack chisel!

Alternative Solution: Greedy with Recursion

Why an Alternative Approach?

The greedy recursive method removes one digit at a time, always picking the move that keeps the number smallest, repeating k times. It’s O(k * n) time and O(n) space—slower but shows a different angle. It’s like peeling off layers to reveal the tiniest core!

How It Works

Picture it as trimming step-by-step:

• Step 1: Find the first spot where a digit is bigger than the next one (a peak).
• Step 2: Remove that digit to keep the number small.
• Step 3: Repeat k times, then clean up zeros.

Step-by-Step Example

Example: num = "1432219", k = 3

• Round 1: "1432219", 1 < 4 > 3, remove 4 → "132219", k = 2.
• Round 2: "132219", 3 > 2, remove 3 → "12219", k = 1.
• Round 3: "12219", 2 > 1, remove 2 → "1219", k = 0.
• Result: "1219".

Code for Greedy Recursion Approach

Copy codeclass Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        # Base case
        if k == 0:
            return num.lstrip("0") or "0"
        if len(num) <= k:
            return "0"

        # Find first peak to remove
        for i in range(len(num) - 1):
            if num[i] > num[i + 1]:
                # Remove this digit, recurse
                new_num = num[:i] + num[i + 1:]
                return self.removeKdigits(new_num, k - 1)

        # If no peak, remove last digit
        return self.removeKdigits(num[:-1], k - 1)

• Time Complexity: O(k * n)—k recursive calls, each scanning n.
• Space Complexity: O(n)—recursion stack.

It’s a patient peeler!

Comparing the Two Solutions

• Monotonic Stack (Best):
• Pros: O(n), O(n), fast and clean.
• Cons: Stack concept to grasp.
• Greedy Recursion (Alternative):
• Pros: O(k * n), O(n), intuitive.
• Cons: Slower.

Stack wins.

Additional Examples and Edge Cases

• "123", 3: "0".
• "100", 1: "0".
• "9", 1: "0".

Stack handles all.

Complexity Breakdown

• Monotonic Stack: Time O(n), Space O(n).
• Greedy Recursion: Time O(k * n), Space O(n).

Stack’s the speed champ.

Key Takeaways

• Monotonic Stack: Build small!
• Greedy Recursion: Peel smart!
• Digits: Order matters.
• Python Tip: Stacks are cool—see [Python Basics](/python/basics).

Final Thoughts: Trim to Win

LeetCode 402: Remove K Digits in Python is a digit-trimming challenge. Monotonic stack carves the smallest number fast, while greedy recursion peels it off. Want more string fun? Try LeetCode 316: Remove Duplicate Letters or LeetCode 321: Create Maximum Number. Ready to erase? Head to Solve LeetCode 402 on LeetCode and shrink that number today!