How do you solve Remove K Digits on LeetCode?

Remove K Digits (LeetCode #402) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Removing larger digits when possible helps in forming the smallest number.

What is the brute force solution for Remove K Digits?

The brute force approach for Remove K Digits is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute-force approach involves generating all possible numbers by removing k digits from the input string and then selecting the smallest one. This method is straightforward but inefficient, especially for large strings. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Remove K Digits?

Remove K Digits uses the following concepts: String, Stack, Greedy, Monotonic Stack. The recommended patterns to study are: Greedy, Monotonic Stack.

What are the interview tips for Remove K Digits?

Explain your thought process clearly while coding. Consider edge cases and discuss them with the interviewer. Practice writing clean and efficient code, as readability matters.

What are common mistakes when solving Remove K Digits?

Not considering leading zeros in the final result. Failing to handle cases where k equals the length of the number.

#402

Remove K Digits

Medium

StringStackGreedyMonotonic StackGreedyMonotonic Stack

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a greedy strategy with a monotonic stack to efficiently build the smallest number by removing digits. This method ensures that we always keep the smallest possible digits in the result.

⚙️

Algorithm

6 steps

1Step 1: Initialize an empty stack to build the result.
2Step 2: Iterate through each digit in 'num'.
3Step 3: While the stack is not empty, and the current digit is smaller than the top of the stack, pop the stack if we still have digits to remove (k > 0).
4Step 4: Push the current digit onto the stack.
5Step 5: After processing all digits, if k > 0, remove the last k digits from the stack.
6Step 6: Convert the stack to a string and remove leading zeros.

solution.py15 lines

1# Full working Python code
2from collections import deque
3
4def removeKdigits(num, k):
5    stack = deque()
6    for digit in num:
7        while k > 0 and stack and stack[-1] > digit:
8            stack.pop()
9            k -= 1
10        stack.append(digit)
11    while k > 0:
12        stack.pop()
13        k -= 1
14    result = ''.join(stack).lstrip('0')
15    return result if result else '0'

ℹ

Complexity note: The time complexity is O(n) because we iterate through the digits once, and the stack operations are O(1) on average. The space complexity is O(n) due to the stack used to build the result.

1Removing larger digits when possible helps in forming the smallest number.
2Leading zeros must be handled carefully to ensure valid output.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.