402. Remove K Digits - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
You are given a non-negative integer in the form of a string num and an integer k. Your task is to remove exactly k digits from the number so that the new number is the smallest possible. Note that the resulting number should not contain any leading zeros. If the resulting number is empty, return "0".

Example 1:

Input:
- num = "1432219"
- k = 3
Output: "1219"
Explanation:
Remove the three digits 4, 3, and 2 to form the smallest number "1219".

Example 2:

Input:
- num = "10200"
- k = 1
Output: "200"
Explanation:
Remove the leading 1 to get "0200". After removing leading zeros, the final result is "200".

Example 3:

Input:
- num = "10"
- k = 2
Output: "0"
Explanation:
Removing both digits results in an empty number, so return "0".

Constraints:

1 ≤ num.length ≤ 10⁵
num consists of only digits.
0 ≤ k ≤ num.length

Hints to Approach the Problem

Hint 1:
Think about removing digits greedily. When a digit is greater than its next digit, removing it may yield a smaller number.
Hint 2:
Use a stack (or a similar data structure) to keep track of the digits. This allows you to decide which digit to remove as you iterate through the number.
Hint 3:
After processing all digits, if you haven’t removed k digits, remove them from the end because the remaining digits are in non-decreasing order.

Approaches

Approach 1: Brute Force (Naive)

Idea:
Try all possible ways to remove k digits and check the resulting numbers to find the smallest one.
Drawbacks:
The number of possibilities is enormous (combinatorial in nature), making this approach infeasible for large input sizes.

Approach 2: Greedy with a Stack (Optimal)

Idea:
Use a greedy algorithm with a stack to decide which digits to remove:
1. Traverse the number digit by digit.
2. While there is a previous digit (top of the stack) that is larger than the current digit and you still can remove more digits (k > 0), remove that digit.
3. Append the current digit to the stack.
4. If there are still digits to remove after the iteration, remove them from the end of the number (since the remaining sequence is non-decreasing).
5. Convert the stack back into a number and strip any leading zeros.
Benefits:
This approach ensures that at every step, you make a locally optimal removal that contributes to the global minimum. It runs in O(n) time.

Code Implementations

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
The algorithm processes each digit once. Each digit is pushed onto or popped from the stack at most once.
Time Complexity: O(n), where n is the length of the input string.
Space Complexity:
A stack (or StringBuilder) is used to store up to n digits.
Space Complexity: O(n).

Step-by-Step Walkthrough

Initialization:
- Create an empty stack to store digits.
- Set up a loop to iterate through each digit in the string.
Processing Each Digit:
- For the current digit, while the stack is not empty and the top digit is larger than the current digit (and removals are available), pop the top digit from the stack (this simulates removing a larger digit to lower the overall number).
- Append the current digit to the stack.
Post-Processing:
- After processing all digits, if there are still removals left (k > 0), remove the last k digits from the stack.
Constructing the Result:
- Convert the digits in the stack back into a string.
- Strip any leading zeros.
- If the resulting string is empty, return "0".
Return the Final Answer:
- The result is the smallest number possible after removing exactly k digits.

Visual Example

Consider num = "1432219" and k = 3.

Step 1: Start with an empty stack.
Step 2:
- Process '1': stack becomes [1].
- Process '4': stack becomes [1, 4] (4 ≥ 1, so no removal).
- Process '3': '4' > '3', so remove '4' (k becomes 2). Now stack = [1], then append '3': stack becomes [1, 3].
- Process '2': '3' > '2', so remove '3' (k becomes 1). Now stack = [1], then append '2': stack becomes [1, 2].
- Process next '2': stack becomes [1, 2, 2] (2 ≥ 2).
- Process '1': The last digit '2' > '1', remove it (k becomes 0), then append '1': stack becomes [1, 2, 1] (if k was still positive, further removals would occur).
- Process '9': Append '9', stack becomes [1, 2, 1, 9].
Step 3:
No remaining removals; the stack represents the number "1219".
Step 4:
Strip leading zeros if any. Final answer is "1219".

Common Mistakes

Not Removing Remaining k Digits:
Forgetting to check if k > 0 after iterating through the number may result in an incorrect final result.
Handling Leading Zeros Incorrectly:
Not stripping off leading zeros could yield an answer with unnecessary zeros.
Incorrect Stack Management:
Mismanaging the stack operations (pushing and popping) can lead to an incorrect order of digits.

Edge Cases

All Digits Removed:
If k equals the length of the string, the answer should be "0".
Already Minimum Number:
When the number is already in non-decreasing order, removals should occur at the end.
Leading Zeros in the Result:
After forming the number, ensure that leading zeros are removed (e.g., "000" should be returned as "0").

Smallest Subsequence of Distinct Characters:
A similar greedy approach using a stack.
Create Maximum Number:
Where you choose digits to form the largest number possible.
Remove Duplicate Letters:
Another problem involving greedy removal using a stack.

Remove Duplicate Letters
Smallest Subsequence of Distinct Characters
Create Maximum Number
Merge Strings Alternately