Remove K Digits (Monotonic Stack)

📋

Problem

Imagine you have a large number displayed on a screen, but you want to make it as small as possible by removing exactly k digits. How do you do it efficiently?

Given a non-negative integer num represented as a string and an integer k, remove k digits from the number so that the new number is the smallest possible. Return the new number as a string without leading zeros. If the result is empty, return "0".

1 ≤ num.length ≤ 10^5num consists of only digits '0' to '9'0 ≤ k ≤ num.length

Edge cases: k equals the length of num → output '0'num consists of all identical digits → remove k digits from the endnum has leading zeros after removal → remove leading zeros in output

</>

IDE

def removeKdigits(num: str, k: int) -> str:public String removeKdigits(String num, int k)string removeKdigits(string num, int k)function removeKdigits(num, k)

def removeKdigits(num: str, k: int) -> str:
    # Write your solution here
    pass

class Solution {
    public String removeKdigits(String num, int k) {
        // Write your solution here
        return "";
    }
}

#include <string>
using namespace std;

string removeKdigits(string num, int k) {
    // Write your solution here
    return "";
}

function removeKdigits(num, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: empty stringReturning empty string instead of '0' when all digits are removed.✅ Return '0' if the resulting string after removals and stripping zeros is empty.

Wrong: number with leading zerosNot stripping leading zeros after digit removal.✅ Strip leading zeros from the final string before returning; if empty, return '0'.

Wrong: wrong digit removed due to greedy mistakeRemoving digits without checking if the next digit is smaller, causing suboptimal result.✅ Pop from stack only when top digit > current digit and k > 0.

Wrong: incorrect output when k=0Modifying the number even when k=0.✅ Return the original number immediately if k is zero.

Wrong: TLE or timeoutUsing brute force or non-linear time complexity approach.✅ Implement O(n) monotonic stack solution to handle large inputs efficiently.

✓

Test Cases

Focus on handling boundary conditions like empty results and leading zeros.

Watch out for greedy mistakes and off-by-one errors in digit removal.

Optimize your solution to linear time using a monotonic stack.

t1_01basic

Input{"num":"1432219","k":3}

Expected"1219"

⏱ Performance - must finish in 2000ms

Remove digits '4', '3', and '2' to get the smallest number '1219'.

💡 Try using a stack to keep digits in increasing order.

💡 Pop from the stack when the current digit is smaller than the top and k > 0.

💡 After processing, remove remaining digits from the end if k > 0, then strip leading zeros.

Why it failed: Failed to remove larger digits before smaller ones or did not handle leading zeros correctly. Fix by popping from stack while top > current digit and k > 0, then remove leading zeros.

✓ Correctly removes digits to form the smallest number using a monotonic stack.

t1_02basic

Input{"num":"10200","k":1}

Expected"200"

⏱ Performance - must finish in 2000ms

Remove the '1' to get '0200', which after removing leading zeros becomes '200'.

💡 Consider how removing digits affects leading zeros.

💡 Use a stack to remove digits that are larger than the next digit.

💡 After removal, strip leading zeros before returning the result.

Why it failed: Did not correctly remove leading zeros after digit removal or removed wrong digits. Fix by stripping leading zeros after stack processing.

✓ Handles leading zeros correctly after removal.

t2_01edge

Input{"num":"10","k":2}

Expected"0"

⏱ Performance - must finish in 2000ms

Removing all digits results in an empty string, which should return '0'.

💡 What happens if k equals the length of num?

💡 The result should be '0' if all digits are removed.

💡 Check for empty result after removals and return '0' accordingly.

Why it failed: Returned empty string instead of '0' when k equals num length. Fix by returning '0' if result is empty after removals.

✓ Correctly returns '0' when all digits are removed.

t2_02edge

Input{"num":"7","k":0}

Expected"7"

⏱ Performance - must finish in 2000ms

No digits removed, so output is the original number.

💡 What if k is zero?

💡 The output should be the original number unchanged.

💡 Ensure your code handles k=0 by returning num directly.

Why it failed: Incorrectly modified number when k=0. Fix by returning original number if k is zero.

✓ Correctly returns original number when k=0.

t2_03edge

Input{"num":"11111","k":3}

Expected"11"

⏱ Performance - must finish in 2000ms

All digits identical; remove k digits from the end to get smallest number.

💡 How does the algorithm behave with all identical digits?

💡 Removing digits from the end is optimal since all digits are equal.

💡 Ensure your stack or logic handles this case without removing wrong digits.

Why it failed: Removed digits incorrectly in all identical digits case. Fix by removing digits from the end when digits are equal.

✓ Correctly removes digits from the end when all digits are identical.

t3_01corner

Input{"num":"1234567890","k":9}

Expected"0"

⏱ Performance - must finish in 2000ms

Removing 9 digits leaves only one digit '0', which is the smallest possible.

💡 Check if your code handles removing almost all digits correctly.

💡 Make sure to remove digits greedily from left to right to get smallest number.

💡 If only one digit remains, return it even if it is zero.

Why it failed: Returned empty string or wrong digit when removing almost all digits. Fix by ensuring at least one digit remains and handle leading zeros.

✓ Correctly returns the smallest remaining digit after removing k digits.

t3_02corner

Input{"num":"112","k":1}

Expected"11"

⏱ Performance - must finish in 2000ms

Removing the '2' at the end yields the smallest number '11'.

💡 Beware of greedy traps that remove the wrong digit.

💡 Check if your algorithm removes the first larger digit before a smaller digit.

💡 Ensure you only remove digits when the next digit is smaller and k > 0.

Why it failed: Removed wrong digit due to greedy mistake, e.g., removing '1' instead of '2'. Fix by popping only when top of stack > current digit.

✓ Correctly removes the right digit to minimize the number.

t3_03corner

Input{"num":"100200","k":1}

Expected"200"

⏱ Performance - must finish in 2000ms

Removing the first '1' leads to '00200' which after removing leading zeros is '200'.

💡 Check if your code handles leading zeros after removal correctly.

💡 Make sure to remove leading zeros before returning the result.

💡 If the result is empty after removing zeros, return '0'.

Why it failed: Returned '00200' or '0200' instead of '200' due to not stripping leading zeros. Fix by stripping leading zeros after removal.

✓ Correctly strips leading zeros after removal.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 requires O(n) solution to complete within 2 seconds.

💡 Brute force solutions will time out on large inputs.

💡 Use a monotonic stack to achieve O(n) time complexity.

💡 Avoid nested loops or combinatorial approaches.

Why it failed: TLE due to exponential or quadratic complexity. Fix by implementing O(n) monotonic stack approach.

✓ Solution runs efficiently in O(n) time on large inputs.

Practice

1. Given the following code for largestRectangleArea, what is the returned max_area for input heights = [2,1,2]?

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Trace stack operations for heights=[2,1,2]

   i=0,h=2: stack=[0]; i=1,h=1: pop 0 (height=2,width=1), max_area=2; stack=[]; append 1; i=2,h=2: append 2; i=3,h=0: pop 2 (height=2,width=1), max_area=2; pop 1 (height=1,width=3), max_area=3

2. Step 2: Final max_area after processing all elements

   max_area=3

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max rectangle area is 3 for input [2,1,2] [OK]

Hint: Remember to add sentinel zero to flush stack [OK]

Common Mistakes:

• Forgetting sentinel zero causes missed areas
• Incorrect width calculation
• Off-by-one in stack indices

2. The following code attempts to detect the 132 pattern using the optimal approach. Which line contains a subtle bug that can cause incorrect results?

medium

A. Line 4: for num in reversed(nums):

B. Line 5: if num <= third:

C. Line 7: while stack and stack[-1] < num:

D. Line 9: stack.append(num)

Solution

1. Step 1: Analyze the condition on line 5

   The original correct condition is num < third. Using num <= third incorrectly returns True when num equals third, which violates strict inequality in 132 pattern.

2. Step 2: Confirm other lines are correct

   Iteration order, stack operations, and append are correct and necessary for the algorithm.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Using <= instead of < causes false positives [OK]

Hint: Strict inequality is required for pattern detection [OK]

Common Mistakes:

• Using <= instead of <
• Confusing iteration direction
• Not popping smaller elements

3. What is the time complexity of the optimal solution that uses a fixed-size frequency array and a queue to find the first unique character in a stream of length n, and why?

medium

A. O(n^2) because each character may cause scanning the entire queue repeatedly.

B. O(n) because each character is enqueued and dequeued at most once, and frequency updates are O(1).

C. O(n log n) due to sorting the queue elements to find the first unique character.

D. O(n * 26) because for each character, frequency array of size 26 is scanned.

Solution

1. Step 1: Analyze queue operations

   Each character is enqueued once when first seen and dequeued once when found duplicate, total O(n) operations.

2. Step 2: Analyze frequency updates

   Frequency array updates are O(1) per character, no scanning needed.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Each character processed in constant time overall [OK]

Hint: Each character enqueued/dequeued once -> O(n) time [OK]

Common Mistakes:

• Assuming scanning queue each time causes O(n^2)
• Thinking frequency array is scanned fully each iteration
• Confusing sorting or scanning with queue operations

4. What is the time complexity of the optimized monotonic stack solution for the sum of subarray minimums problem, and why?

medium

A. O(n log n) due to sorting or binary search inside the stack operations

B. O(n^2) because each element can be pushed and popped multiple times

C. O(n) because each element is pushed and popped at most once

D. O(n) but with O(n^2) auxiliary space for storing subarray minimums

Solution

1. Step 1: Identify stack operations per element

   Each element is pushed once and popped once, so total stack operations are O(n).

2. Step 2: Confirm no nested loops or extra sorting

   The algorithm uses a single pass with a stack, no sorting or nested loops, so time is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Monotonic stack guarantees linear time complexity [OK]

Hint: Each element pushed and popped once -> O(n) time [OK]

Common Mistakes:

• Assuming multiple pops per element cause O(n^2)
• Confusing with sorting-based methods

5. Suppose the problem changes so that elements in the array can be negative integers. Which modification to the monotonic stack approach is necessary to correctly compute the sum of subarray minimums?

hard

A. Add a sentinel element with value 0 at the end to ensure stack empties correctly

B. No change needed; the existing monotonic stack approach works for negative values

C. Use a different data structure like a balanced BST to handle negative values

D. Modify the comparison to use <= instead of < to handle negative duplicates

Solution

1. Step 1: Analyze effect of negative values on monotonic stack

   The monotonic stack approach relies on relative ordering, which holds regardless of sign.

2. Step 2: Confirm no structural changes needed

   Sentinel and strict < comparison still work; negative values do not break the logic.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Monotonic stack handles negatives without modification [OK]

Hint: Monotonic stack compares values, sign does not affect correctness [OK]

Common Mistakes:

• Assuming negative values require different data structures
• Changing comparison operators unnecessarily