MediumNo. 0402
Remove K Digits — LeetCode 402 Python Solution
- Pattern
- Stack
- Topics
- Stack, Greedy, String, Monotonic Stack
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.
Example
- 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.
Python solution
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'Complexity
- Time
- O(n log n)
- Space · auxiliary
- O(1) to O(n)
Pattern: Stack
When the most recent unresolved thing is the one that matters, use a stack. LeetCode 402. Remove K Digits is filed here because LeetCode tags it Stack, which is the vocabulary this hub collects.
The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0316 | Remove Duplicate Letters | Medium |
| 1081 | Smallest Subsequence of Distinct Characters | Medium |
| 0768 | Max Chunks To Make Sorted II | Hard |
| 0769 | Max Chunks To Make Sorted | Medium |
| 0921 | Minimum Add to Make Parentheses Valid | Medium |
| 0936 | Stamping The Sequence | Hard |
Frequently asked questions
- How hard is LeetCode 402. Remove K Digits?
LeetCode 402. Remove K Digits is rated Medium on LeetCode.
- What topics does LeetCode 402. Remove K Digits cover?
LeetCode 402. Remove K Digits is tagged Stack, Greedy, String and Monotonic Stack on LeetCode.