To solve Remove K Digits, use a monotonic stack to maintain increasing digits while iterating through the number. Remove digits from the stack whenever a higher digit precedes a lower one, ensuring the smallest number after k removals. Handle leading zeros carefully and return '0' if all digits are removed, applying stack-based state management for guaranteed minimal output.
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.
How GhostInterview Helps
- GhostInterview highlights the stack-based state management pattern to guide digit selection.
- It identifies failure points like mishandled leading zeros and incomplete removals during practice runs.
- Provides step-by-step tracing of stack operations to confirm minimal integer formation and correct k removals.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Remove K Digits instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Remove K Digits from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Remove duplicate letters from a string to produce the lexicographically smallest result using stack-based state management.
Open problem page#1081 Smallest Subsequence of Distinct CharactersThe Smallest Subsequence of Distinct Characters problem asks you to find the lexicographically smallest subsequence of a string with distinct characters.
Open problem page#321 Create Maximum NumberCreate Maximum Number involves merging digits from two arrays while preserving order, maximizing the resulting number.
Open problem page