Remove K Digits (Smallest Number)

▶

Steps

setup

Initialize empty builder and start iteration

We start with an empty stack (builder) and prepare to iterate over each digit in the input number.

💡 Initialization is crucial to build the result incrementally and apply the greedy removal logic.

Line:

builder = []
for digit in num:

💡 The stack will hold digits of the resulting number as we process each digit.

fill_cells

Process first digit '1': push onto stack

The first digit '1' is pushed onto the empty stack since there is nothing to compare it with.

💡 Pushing the first digit sets the base for comparisons with subsequent digits.

Line:

builder.append(digit)

💡 The stack now contains the first digit of the resulting number.

fill_cells

Process second digit '4': push onto stack

Digit '4' is greater than the top of the stack '1', so it is pushed onto the stack without popping.

💡 Digits are pushed if they maintain or increase the stack's monotonic order.

Line:

builder.append(digit)

💡 Stack now holds digits in non-decreasing order: ['1', '4'].

compare

Process third digit '3': pop '4' and push '3'

Since '3' is less than the top of the stack '4' and k > 0, we pop '4' to remove a larger digit and then push '3'.

💡 Removing larger digits before smaller ones helps form a smaller number.

Line:

while k > 0 and builder and builder[-1] > digit:
    builder.pop()
    k -= 1
builder.append(digit)

💡 Popping '4' reduces k by 1 and helps achieve a smaller number.

compare

Process fourth digit '2': pop '3' and push '2'

Digit '2' is less than the top '3' and k=2 > 0, so pop '3' and push '2'.

💡 Continuing to remove larger digits before smaller ones reduces the number.

Line:

while k > 0 and builder and builder[-1] > digit:
    builder.pop()
    k -= 1
builder.append(digit)

💡 Removing '3' further decreases k and improves minimality.

fill_cells

Process fifth digit '2': push '2' onto stack

Digit '2' is equal to the top of the stack '2', so it is pushed without popping.

💡 Equal digits do not violate the monotonic property and are kept.

Line:

builder.append(digit)

💡 Stack now has repeated digits, which is allowed.

compare

Process sixth digit '1': pop one '2' and push '1'

Digit '1' is less than the top '2' and k=1 > 0, so pop one '2' and push '1'.

💡 Pop only one '2' because k allows only one removal here.

Line:

while k > 0 and builder and builder[-1] > digit:
    builder.pop()
    k -= 1
builder.append(digit)

💡 Removing one '2' uses remaining k to get a smaller number.

fill_cells

Process seventh digit '9': push '9' onto stack

Digit '9' is greater than the top '1', so it is pushed without popping.

💡 Digits larger than the top are appended to maintain order.

Line:

builder.append(digit)

💡 Stack now contains the final digits before any leftover removals.

shrink

Remove leftover digits if k > 0 (k=0 now, so no removal)

After processing all digits, k is 0, so no further removals are needed.

💡 If k was still positive, we would remove digits from the end to minimize the number.

Line:

while k > 0:
    builder.pop()
    k -= 1

💡 No trailing removals needed, so the stack is final.

reconstruct

Remove leading zeros and form final answer

Leading zeros are stripped from the stack digits, and the remaining digits are joined to form the final answer.

💡 Removing leading zeros ensures the number is correctly formatted.

Line:

result = ''.join(builder).lstrip('0')
return result if result else '0'

💡 The final smallest number after removals is '1219'.

def removeKdigits(num: str, k: int) -> str:
    builder = []  # STEP 1: initialize empty stack
    for digit in num:  # STEP 2-8: iterate digits
        while k > 0 and builder and builder[-1] > digit:  # STEP 4,5,7: pop while top > digit
            builder.pop()  # STEP 4,5,7: pop top
            k -= 1  # STEP 4,5,7: decrement k
        builder.append(digit)  # STEP 2,3,6,8: push current digit
    while k > 0:  # STEP 9: remove leftover digits
        builder.pop()
        k -= 1
    result = ''.join(builder).lstrip('0')  # STEP 10: remove leading zeros
    return result if result else '0'

if __name__ == '__main__':
    print(removeKdigits("1432219", 3))  # 1219
    print(removeKdigits("10200", 1))   # 200
    print(removeKdigits("10", 2))      # 0

📊

Remove K Digits (Smallest Number) - Watch the Algorithm Execute, Step by Step

Watching each push and pop operation reveals how the algorithm maintains a monotonic stack to ensure the smallest number is formed, which is hard to grasp from code alone.

no_opElement[0]: 1

Stack (top→bottom)

empty

pushElement[0]: 1

Stack (top→bottom)

1

↑ pushed: 1

pushElement[1]: 4

Stack (top→bottom)

4

1

↑ pushed: 4

popElement[2]: 3

Stack (top→bottom)

3

1

↓ popped: [4]

popElement[3]: 2

Stack (top→bottom)

2

1

↓ popped: [3]

pushElement[4]: 2

Stack (top→bottom)

2

2

1

↑ pushed: 2

popElement[5]: 1

Stack (top→bottom)

1

2

1

↓ popped: [2]

pushElement[6]: 9

Stack (top→bottom)

9

1

2

1

↑ pushed: 9

no_op

Stack (top→bottom)

9

1

2

1

no_op

Stack (top→bottom)

9

1

2

1

Contributes: "1219"

Key Takeaways

✓ The greedy removal of digits from the stack ensures the smallest number by always removing a larger digit before a smaller one.

This insight is hard to see from code alone because it requires understanding the monotonic stack property and how removals affect the final number.

✓ The stack maintains a non-decreasing order of digits, which guarantees the minimality of the resulting number after removals.

Visualizing the stack shows how the algorithm preserves order and why certain digits are popped or kept.

✓ Multiple pops can occur in one iteration when the current digit is smaller than several top digits, using up k removals efficiently.

Seeing these multiple pops in the trace clarifies how the algorithm aggressively removes digits to minimize the number.

Practice

1. You have a list of children each with a greed factor and a list of cookies each with a size. You want to assign cookies to children so that each child gets at most one cookie and the cookie size is at least the child's greed factor. Which algorithmic approach guarantees the maximum number of content children?

easy

A. Greedy algorithm by sorting greed factors and cookie sizes, then assigning smallest sufficient cookie to each child

B. Dynamic Programming to try all possible assignments and pick the best

C. Brute force nested loops checking every cookie for every child without sorting

D. Divide and Conquer by splitting children and cookies and merging results

Solution

1. Step 1: Understand problem constraints

   Each child can get at most one cookie, and the cookie must satisfy the child's greed factor.

2. Step 2: Identify optimal approach

   Sorting both greed and cookie arrays allows a greedy assignment from smallest greed to smallest sufficient cookie, ensuring maximum matches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy sorting approach is classic for assignment problems [OK]

Hint: Sort both arrays and assign greedily [OK]

Common Mistakes:

• Thinking brute force is needed for optimality
• Assuming DP is required
• Ignoring sorting leads to suboptimal matches

2. You are given an array where each element represents the maximum jump length from that position. Your goal is to reach the last index in the minimum number of jumps. Which algorithmic approach guarantees finding the minimum number of jumps efficiently?

easy

A. A simple greedy approach that always jumps to the farthest reachable index from the current position.

B. A breadth-first search (BFS) treating each index as a node and exploring all reachable indices level by level.

C. A dynamic programming approach that computes the minimum jumps for each index by checking all previous indices.

D. A depth-first search (DFS) exploring all possible jump sequences recursively and returning the minimum.

Solution

1. Step 1: Understand problem as shortest path in graph

   Each index can be seen as a node with edges to reachable indices. BFS explores nodes level by level, guaranteeing the shortest path (minimum jumps).

2. Step 2: Compare approaches

   Greedy alone can fail on some inputs by making locally optimal but globally suboptimal jumps. DP is correct but less efficient. DFS is exponential time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   BFS ensures minimum jumps by level order traversal [OK]

Hint: Minimum jumps = shortest path -> BFS [OK]

Common Mistakes:

• Believing greedy always yields minimum jumps
• Confusing DP with BFS for this problem
• Assuming DFS is efficient here

3. Consider the following buggy code for assigning cookies to children. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line 5: Missing increment of j when cookie is assigned

B. Line 3: Incorrect loop condition including count < len(g)

C. Line 1: Missing sorting of g and s arrays

D. Line 7: Incrementing j only in else block

Solution

1. Step 1: Identify missing pointer increment

   When a cookie satisfies a child (s[j] ≥ g[i]), j should increment to avoid reusing the same cookie.

2. Step 2: Check code lines

   Line 5 increments count and i but does not increment j, causing the same cookie to be assigned multiple times.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without j increment on assignment, cookie reuse occurs [OK]

Hint: Check pointer increments on both branches [OK]

Common Mistakes:

• Forgetting to sort arrays
• Incorrect loop conditions
• Not incrementing both pointers on assignment

4. Consider the following buggy code for the Gas Station problem. Which line contains the subtle bug that can cause incorrect results?

def canCompleteCircuit(gas, cost):
    n = len(gas)
    net = [gas[i] - cost[i] for i in range(n)]
    # Bug: missing total gas check
    prefix = [0] * (2 * n + 1)
    for i in range(2 * n):
        prefix[i+1] = prefix[i] + net[i % n]
    for i in range(n):
        if prefix[i+n] - prefix[i] >= 0:
            return i
    return -1

medium

A. Line 3: net array computation

B. Line 4: missing total gas vs total cost check

C. Line 6: prefix sums computation loop

D. Line 8: checking prefix sums for valid start

Solution

1. Step 1: Identify missing total gas check

   The code does not check if sum(net) < 0 before proceeding, which can cause incorrect start index or false positives.

2. Step 2: Verify other lines

   Net array, prefix sums, and prefix difference checks are correct and standard.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing total gas check leads to incorrect results [OK]

Hint: Always check total gas >= total cost before searching start [OK]

Common Mistakes:

• Forgetting total gas check
• Misusing modulo in prefix sums
• Resetting start without resetting tank

5. What is the time complexity of the optimal min-heap based algorithm for finding the minimum number of platforms required for n trains?

medium

A. O(n²) due to nested loops checking all train pairs

B. O(n) because each train is processed once

C. O(n log n) due to sorting and heap operations for each train

D. O(n log k) where k is the maximum number of platforms needed

Solution

1. Step 1: Identify sorting cost

   Sorting n trains by arrival time costs O(n log n).

2. Step 2: Analyze heap operations

   Each train causes at most one push and one pop on the heap, each O(log n), so total O(n log n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting + heap operations dominate complexity [OK]

Hint: Sorting + heap push/pop per train -> O(n log n) [OK]

Common Mistakes:

• Assuming O(n) ignoring sorting and heap costs
• Confusing heap size k with n for complexity
• Mistaking nested loops for optimal approach complexity