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. You are given two arrays nums1 and nums2, where nums1 is a subset of nums2. For each element in nums1, you want to find the first greater element to its right in nums2. Which algorithmic approach guarantees an optimal solution in terms of time complexity?

easy

A. Use a monotonic stack to precompute the next greater element for all elements in nums2, then map results for nums1.

B. Use nested loops to check each element of nums1 against all elements to its right in nums2.

C. Use dynamic programming to store the next greater element for each index in nums2.

D. Sort nums2 and use binary search to find the next greater element for each element in nums1.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the next greater element for each element in nums1 based on their positions in nums2, which is a classic next greater element problem.

2. Step 2: Identify the optimal approach

   Using a monotonic stack to precompute next greater elements for all nums2 elements allows O(n) processing, then mapping results for nums1 is O(m), leading to an overall O(n + m) time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack approach is well-known for next greater element problems [OK]

Hint: Monotonic stack precomputes next greater efficiently [OK]

Common Mistakes:

• Using nested loops leads to O(m*n) time, too slow for large inputs
• Sorting nums2 loses original order, invalidating next greater logic
• Dynamic programming is not applicable here as no overlapping subproblems

2. Given the following Python code for checking valid parentheses, what is the return value when the input string is "([)]"?

def isValid(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
        else:
            return False
    return not stack

easy

A. False

B. True

C. Raises an exception

D. Depends on input length

Solution

1. Step 1: Trace input "([)]" through the code

   Push '(' then push '['. Next char is ')', expected to match '[' but pairs[')'] = '(', top of stack is '[' -> mismatch -> return False immediately.

2. Step 2: Confirm final output

   Function returns False as soon as mismatch is detected.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mismatch detected at third character -> returns False [OK]

Hint: Mismatch causes immediate False return [OK]

Common Mistakes:

• Assuming order doesn't matter and returning True incorrectly

3. What is the amortized time complexity of the pop operation in the optimal two-stack queue implementation, and why?

medium

A. Amortized O(1) because each element is moved at most once between stacks before being popped.

B. O(log n) due to repeated stack operations during transfer.

C. O(1) worst-case because pop_stack always contains all elements in order.

D. O(n) because elements are transferred from push_stack to pop_stack on every pop.

Solution

1. Step 1: Identify when transfer happens

   Transfer from push_stack to pop_stack happens only when pop_stack is empty.

2. Step 2: Analyze element movement

   Each element is pushed and popped at most twice (once into push_stack, once into pop_stack), so total operations per element are constant.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Amortized O(1) per pop due to limited transfers [OK]

Hint: Each element moves stacks once -> amortized O(1) pop [OK]

Common Mistakes:

• Thinking transfer happens every pop -> O(n) pop
• Assuming worst-case O(1) pop always

4. The following code attempts to implement the optimized next greater element algorithm. Which line contains a subtle bug that can cause incorrect results or inefficiency?

medium

A. Line with 'while stack and num > stack[-1]:' condition

B. Line 'while stack:' loop assigning -1 to remaining elements

C. Line 'nums1_set.remove(smaller)' inside the if condition

D. Line missing 'next_greater_map[smaller] = num' inside the while loop

Solution

1. Step 1: Identify missing mapping assignment

   The code pops smaller elements but does not assign their next greater element in next_greater_map, causing missing or incorrect results.

2. Step 2: Confirm other lines are correct

   The while condition, set removal, and final assignment of -1 are all correct and necessary for correctness and efficiency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Without mapping assignment, queries for nums1 elements fail [OK]

Hint: Mapping next greater elements must happen immediately after popping [OK]

Common Mistakes:

• Forgetting to assign next greater element after popping from stack
• Incorrectly removing elements from nums1_set too early
• Misplacing the final assignment of -1 for leftover stack elements

5. Consider this buggy version of the sliding window maximum code. Which line contains the subtle bug that causes incorrect maximum values for some inputs?

from typing import List
from collections import deque

def maxSlidingWindow(nums: List[int], k: int) -> List[int]:
    n = len(nums)
    dq = deque()  # stores indices
    result = []
    for i in range(n):
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()  # remove smaller elements
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()  # remove out of window
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

medium

A. Line with 'while dq and nums[dq[-1]] < nums[i]: dq.pop()'

B. Line with 'if dq[0] <= i - k: dq.popleft()'

C. Line with 'dq.append(i)'

D. Line with 'if i >= k - 1: result.append(nums[dq[0]])'

Solution

1. Step 1: Understand window boundary condition

   Indices outside the window must be removed. The window covers indices [i-k+1, i].

2. Step 2: Check condition correctness

   Condition 'dq[0] <= i - k' removes indices ≤ i-k, but should remove indices < i-k+1, so correct condition is 'dq[0] == i - k'.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Incorrect boundary check causes stale indices to remain [OK]

Hint: Remove indices exactly out of window, not before or after [OK]

Common Mistakes:

• Using <= instead of == for out-of-window removal