Remove K Digits (Smallest Number)

📋

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. If the new number is empty, return "0".

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

Edge cases: k equals 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: 1219 (correct) but code returns 4321Not using monotonic stack; removing digits incorrectly or in wrong order.✅ Implement a stack that pops digits larger than current digit while k > 0.

Wrong: 0200 instead of 200Leading zeros not removed after digit removal.✅ Strip leading zeros from the final string or return '0' if empty.

Wrong: 11 instead of 0 when k equals num lengthNot returning '0' when all digits are removed.✅ Return '0' if the resulting string is empty after removal.

Wrong: 12 instead of 11Removing wrong digit due to incorrect greedy logic.✅ Remove digits only when next digit is smaller or from the end if none.

Wrong: TLE on large inputUsing brute force or non-linear time complexity.✅ Use O(n) monotonic stack approach to remove digits efficiently.

✓

Test Cases

Focus on handling boundary conditions like empty results and all identical digits.

Test your solution against tricky cases that break naive greedy assumptions.

Ensure your solution runs in linear time to handle large inputs efficiently.

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.

💡 Remove digits from the stack while the current digit is smaller and k > 0.

💡 Pop larger digits from stack until k is zero, then build the result removing leading zeros.

Why it failed: Incorrect output means the monotonic stack logic is wrong; ensure you pop digits larger than current while k > 0.

✓ Correctly implemented monotonic stack approach.

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 is '200'.

💡 Leading zeros must be removed after removal.

💡 Use stack to remove digits larger than next digit while k > 0.

💡 After processing, strip leading zeros or return '0' if empty.

Why it failed: Failing this test means leading zeros are not removed properly or stack removal logic is incorrect.

✓ Handles leading zeros and stack removal correctly.

t2_01edge

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

Expected"0"

⏱ Performance - must finish in 2000ms

No digits removed, single digit zero remains.

💡 Check behavior when k=0; output should be original number.

💡 Ensure no digits are removed if k=0.

💡 Return original number as is, no leading zero removal needed.

Why it failed: If output differs, code incorrectly removes digits when k=0; fix by skipping removal when k=0.

✓ Correctly returns original number when k=0.

t2_02edge

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 '11'.

💡 When digits are identical, removal should be from the right.

💡 Stack approach should not remove digits unnecessarily from left.

💡 Ensure removal count k is fully used by popping from the end if needed.

Why it failed: If output is wrong, stack removal logic may remove digits incorrectly; fix by removing remaining k digits from the end after stack processing.

✓ Correctly handles identical digits by removing from the end.

t2_03edge

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

Expected"0"

⏱ Performance - must finish in 2000ms

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

💡 If k equals length of num, output must be '0'.

💡 Check for empty result after removal and return '0'.

💡 Handle edge case where all digits are removed.

Why it failed: If output is not '0', code does not handle full removal correctly; fix by returning '0' when result is empty.

✓ Correctly returns '0' when all digits removed.

t3_01corner

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

Expected"0"

⏱ Performance - must finish in 2000ms

Removing 9 digits leaves '0' as smallest number.

💡 Greedy approach must remove largest digits first.

💡 Check that removal continues until k digits removed, even if digits are increasing.

💡 Ensure final result is not empty; return '0' if so.

Why it failed: Failing means greedy logic stops early or does not remove enough digits; fix by continuing removals until k=0.

✓ Correctly removes largest digits even in increasing sequence.

t3_02corner

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

Expected"11"

⏱ Performance - must finish in 2000ms

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

💡 Avoid removing digits that cause larger number after removal.

💡 Check that removal is done only when next digit is smaller.

💡 If no smaller next digit, remove from the end.

Why it failed: If output is '12', code incorrectly removes the wrong digit; fix by removing digits only when next digit is smaller or from the end if none.

✓ Correctly removes the last digit when no smaller next digit.

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'.

💡 Leading zeros after removal must be stripped.

💡 Stack approach must handle zeros correctly.

💡 Ensure final string is not empty after stripping zeros.

Why it failed: If output is '0200' or '00200', code does not remove leading zeros properly; fix by stripping leading zeros after building result.

✓ 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 is O(n choose k), which is infeasible here.

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

💡 Avoid nested loops and repeated string operations.

Why it failed: TLE indicates brute force or inefficient approach; fix by implementing O(n) monotonic stack solution.

✓ Solution runs in O(n) time and passes performance constraints.

Practice

1. You have a sequence of children standing in a line, each with a rating. You must distribute candies such that each child has at least one candy, and any child with a higher rating than an immediate neighbor gets more candies than that neighbor. Which algorithmic approach guarantees the minimum total candies distributed?

easy

A. Two-pass greedy: first left-to-right to satisfy left neighbors, then right-to-left to satisfy right neighbors

B. Brute force repeated adjustment until no changes occur

C. Single pass greedy from left to right only, assigning candies based on previous child

D. Dynamic programming with memoization over all subsequences

Solution

1. Step 1: Understand the problem constraints

   Each child must have at least one candy, and children with higher rating than neighbors must have more candies.

2. Step 2: Identify algorithm that satisfies both left and right neighbor constraints

   Two-pass greedy first ensures left neighbor condition, then right neighbor condition, guaranteeing minimal total candies.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two passes ensure both neighbor constraints met [OK]

Hint: Two passes needed to satisfy both neighbors [OK]

Common Mistakes:

• Using single pass left-to-right misses right neighbor constraints
• Assuming brute force is efficient enough
• Confusing DP with greedy here

2. You are given a positive integer n. The task is to find the largest integer less than or equal to n such that its digits are in non-decreasing order from left to right. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Divide and conquer splitting the number into halves and solving recursively

B. Dynamic Programming that tries all digit combinations to build the largest monotone number

C. Brute force decrementing from n downwards checking monotonicity for each number

D. Greedy algorithm scanning digits from right to left, adjusting digits and setting trailing digits to 9

Solution

1. Step 1: Understand the problem constraints

   The problem requires the largest number ≤ n with digits in non-decreasing order, which suggests a digit-wise adjustment rather than enumerating all numbers.

2. Step 2: Identify the approach that efficiently fixes digits from right to left

   The greedy right-to-left scan decreases digits when a violation is found and sets subsequent digits to 9, ensuring the largest monotone number ≤ n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy right-to-left fix is optimal and efficient [OK]

Hint: Greedy right-to-left digit fix ensures optimal monotone number [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Assuming DP is needed for digit monotonicity
• Believing divide and conquer applies here

3. What is the time complexity of the optimal greedy solution for the Jump Game problem, and why is the following common misconception incorrect? Misconception: The time complexity is O(n^2) because for each index, you might check all reachable next indices.

medium

A. O(n) because the algorithm iterates through the array once, updating max reachable index

B. O(n log n) due to sorting or binary search involved in jump calculations

C. O(n^2) because each index can jump to multiple next indices

D. O(n) but with O(n) auxiliary space for memoization

Solution

1. Step 1: Identify the algorithm's iteration pattern

   The greedy solution iterates through the array once, updating a single variable maxReach without nested loops.

2. Step 2: Explain why O(n^2) is incorrect

   Unlike brute force, it does not explore all jumps explicitly; it only tracks the furthest reachable index, so no nested iteration occurs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass through array -> O(n) time, no nested loops [OK]

Hint: Greedy uses one pass, no nested loops [OK]

Common Mistakes:

• Confusing brute force with greedy complexity
• Assuming nested loops due to jumps

4. What is the time complexity of the optimal solution that sorts the list of numbers (converted to strings) using a custom comparator which compares concatenations of pairs?

medium

A. O(n * k * log n), where n is number of elements and k is max digit length

B. O(n! * n * k), where n is number of elements and k is max digit length

C. O(n^2 * k), where n is number of elements and k is max digit length

D. O(n log n * k), where n is number of elements and k is max digit length

Solution

1. Step 1: Identify sorting complexity

   Sorting n elements takes O(n log n) comparisons.

2. Step 2: Each comparison involves concatenating two strings of max length k and comparing them

   Each comparison is O(k), so total is O(n log n * k).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting with custom comparator comparing concatenations costs O(k) per comparison [OK]

Hint: Each comparison costs O(k), sorting O(n log n) times [OK]

Common Mistakes:

• Confusing O(n*k*log n) with O(n log n * k)
• Assuming O(n^2) due to pairwise comparisons
• Forgetting string concat cost

5. The following code attempts to compute the minimum cost to connect sticks using a min-heap. Identify the bug that causes incorrect results or infinite loops.

medium

A. Line 3: Incorrect base case check for single stick

B. Line 9: Adding cost before popping sticks

C. Line 6: Not heapifying the sticks before processing

D. Line 11: Not pushing the merged stick back into the heap

Solution

1. Step 1: Review the merge loop

   The loop pops two smallest sticks and sums their lengths as cost.

2. Step 2: Check if merged stick is reinserted

   The merged stick must be pushed back into the heap to continue merging. Missing this causes infinite loop or incorrect cost.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Without pushing merged stick, heap shrinks incorrectly -> infinite loop or wrong result [OK]

Hint: Merged sticks must be pushed back to heap [OK]

Common Mistakes:

• Forgetting to push merged stick back
• Incorrect base case handling
• Misordering heap operations