#402

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Remove K Digits

Remove K Digits requires selecting which digits to drop using a monotonic stack for the smallest possible integer result efficiently.

string stack greedy monotonic stack

Problem Statement

You are given a string num representing a non-negative integer and an integer k. Remove exactly k digits from num so that the resulting number is the smallest possible. The resulting number should not contain leading zeros unless it is '0'.

For example, given num = '1432219' and k = 3, removing digits 4, 3, and 2 produces '1219', the minimal value. Consider edge cases such as removing all digits or handling numbers with leading zeros after removal.

Examples

Example 1

Input: num = "1432219", k = 3

Output: "1219"

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"

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"

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.

Solution Approach

Use a Monotonic Stack

Iterate through each digit and push it onto a stack. If the current digit is smaller than the stack's top and you still have removals left, pop from the stack. This maintains an increasing sequence to ensure the smallest result.

Finalize Removals and Build Result

After iterating through num, if removals remain, remove digits from the stack's end. Then, concatenate the stack elements into a string, taking care to strip leading zeros and returning '0' if empty.

Edge Case Handling

Account for cases where k equals the length of num, producing '0'. Also handle numbers with leading zeros after removals and single-digit inputs, ensuring correctness for all string lengths.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each digit is pushed and popped at most once in the stack. Space complexity is O(n) for storing the stack elements representing the partially built number.

What Interviewers Usually Probe

Check if candidate identifies the need for a monotonic stack to maintain increasing digits.
Observe whether they correctly remove digits when a higher digit precedes a smaller one.
Verify handling of leading zeros and edge cases like complete removal of all digits.

Common Pitfalls or Variants

Common pitfalls

Removing digits without maintaining a monotonic stack can produce a non-minimal number.
Failing to handle leading zeros after removal may give incorrect output.
Not considering the case where k equals num.length results in missing the '0' return.

Follow-up variants

Modify the problem to remove k digits to form the largest possible integer instead.
Restrict removals to contiguous segments instead of any digit positions.
Introduce a cost per digit removed and find the minimal value respecting removal cost.

FAQ

What is the main strategy to remove k digits for minimal number?

The key is using a monotonic increasing stack: push digits and pop when the current digit is smaller, ensuring the smallest sequence.

How do I handle leading zeros after removing digits?

After building the number from the stack, strip all leading zeros. Return '0' if the string becomes empty.

Can this approach handle large inputs efficiently?

Yes, the stack-based approach processes each digit once, giving O(n) time and O(n) space, suitable for num.length up to 10^5.

What if k equals the length of num?

Removing all digits results in '0' as the output, which must be explicitly handled.

Why is this considered a stack-based state management problem?

Because maintaining the stack as an increasing sequence represents the current optimal state, allowing dynamic removal decisions while scanning the number.

terminal

Solution

Solution 1: Greedy Algorithm

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stk = []
        remain = len(num) - k
        for c in num:
            while k and stk and stk[-1] > c:
                stk.pop()
                k -= 1
            stk.append(c)
        return ''.join(stk[:remain]).lstrip('0') or '0'

Continue Practicing

#316 remove duplicate letters #1081 smallest subsequence of distinct characters #321 create maximum number