DSA sheet · Stack · Greedy + Stack pattern

Remove K Digits

This video opens a new pattern in the stack section: Stack + Greedy. The teacher says this exact question was asked in her own interviews for an SDE-2 level role, so she treats it as a must-do. She first builds a brute force (delete one digit at a time and keep the smallest result), shows why it is too slow for the constraints, and then builds the greedy stack solution step by step, including the three special cases (normal pops, an increasing tail, and leading zeros).

Why it matters: "remove some items so that what is left is as small as possible" is the heart of the Greedy + Stack pattern. The next two problems in the sheet (Remove Duplicate Letters, Smallest Subsequence of Distinct Characters) use the same idea with one extra rule.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Stacks from scratch, and the Greedy + Stack idea
• Part A · Brute force: delete one digit, k times
• Part B · Optimal: greedy with a monotonic stack
• Part C · Revision page

Part 0 · Before starting

What is a stack?

A stack is a pile of plates. You can only put a plate on the top (push), look at the top plate (peek), or take the top plate off (pop). The last plate you put on is the first one you take off. This rule is called LIFO: Last In, First Out.

  push 1, push 4, push 3         pop  -> gives 3

     | 3 |  <- top                   | 4 |  <- top
     | 4 |                           | 1 |
     | 1 |  <- bottom                +---+
     +---+

A Python list is a stack

stack = []
stack.append('1')      # push: put on top
top = stack[-1]        # peek: look at the top, don't remove it
x = stack.pop()        # pop: remove the top and give it back
if stack:              # empty check: an empty list is "false"
    print(stack[-1])

We always write a stack left = bottom, right = top. So ['1', '2'] means 1 is at the bottom and 2 is on top.

When do we reach for a stack?

The teacher's rule of thumb from the whole playlist: when you need to go back and change or delete something you saw just before, use a stack. The most recent item is always on top, so going back one step costs O(1), not a fresh scan of everything behind you.

The Greedy + Stack pattern (a monotonic stack)

Greedy means making the choice that looks best right now and never undoing it. In this pattern we walk left to right and push items. Before pushing a new item, we look at the top: if the top is bigger than the new item, and we are still allowed to remove something, we pop it. We repeat until the top is no longer bigger.

• Because we pop every bigger item, the stack always stays in increasing order from bottom to top (equal items can sit next to each other). A stack that is always sorted like this is called a monotonic stack (monotonic = only goes one way).
• What the stack "remembers": the best (smallest) prefix we can build from what we have seen so far, given the removals we have used.
• Why we pop the bigger one: in a number, the digit further left has a bigger place value. If a big digit sits just before a smaller one, removing the big one lets the smaller one slide into its place. That makes the number smaller (the exact reason is in Part B, step 4).

stack = []
for x in items:
    while stack and allowed_to_remove and stack[-1] > x:
        stack.pop()            # a bigger item before a smaller one: drop it
    stack.append(x)

Digits as characters

The number comes as a string, so each digit is a character like '4'. Python compares single digit characters in the right order: '0' < '1' < … < '9'. So stack[-1] > ch works without converting to int.

Part A · Brute force: delete one digit, k times

LeetCode 402

1The question in simple words

You get a non-negative number num written as a string, and a number k. Delete exactly k digits (from any positions) so that the number that is left is as small as possible. The remaining digits keep their order. Return it as a string with no leading zeros (and "0" if nothing is left).

Other LeetCode examples: "10200", k = 1 → "200" (deleting the 1 leaves "0200", and the leading zero goes) and "10", k = 2 → "0" (everything is deleted).

2What the constraints tell us

• 1 ≤ k ≤ num.length ≤ 10⁵ → the string can be 100,000 digits long. Far too long to fit in any int type (in Java/C++), so we must work with the string, not convert it.
• k can be as large as n. The teacher points this out: if k = n = 10⁵, anything that does "k rounds × n work" is 10⁵ × 10⁵ = 10¹⁰ steps.
• Her TLE rule from the playlist: past about 10⁸ operations it's risky, past 10⁹ it surely gives TLE (Time Limit Exceeded). So we need roughly O(n) or O(n log n).
• num has no leading zeros (except the number "0" itself), but after deleting we can create leading zeros, so we must handle them.

3Intuition: delete the big digit… but position matters too

Forget all rules and think like a person. To make a number smaller, you'd delete a big digit. Take 912 with one deletion:

So "delete the biggest digit" seems right. But now try 1432219 with one deletion. The biggest digit is the 9:

• Delete the 9 → 143221. The 9 was in the ones place, worth only 9.
• Delete the 4 → 132219. Smaller! Even though 4 < 9.

The face value of a digit is not enough. Its place value matters too. The 9 sat at the very end (ones place), while the 4 sat near the front (the hundred-thousands place). Deleting a digit near the front changes the number a lot more. So we can't just hunt for the biggest digit. We have to think about which digit and where.

4Building the logic: the "lame" approach

The teacher's first, simple plan: since we must delete 3 digits, delete just one at a time. In each round, try deleting every position, keep the smallest result, and use that as the new number for the next round.

Round 1 on 1432219

Smallest: 132219 (we deleted the 4).

Round 2 on 132219

Round 3 on 12219

After 3 rounds we have 1219, the expected answer ✓.

Comparing two candidates: the helper is_smaller

The candidates are strings, and string comparison is not number comparison. For example, the string "103" is less than "21" as text (because '1' < '2'), but 103 is the bigger number. The teacher's two rules:

• Different lengths (after removing leading zeros) → the shorter one is the smaller number. A 3-digit number is always bigger than a 2-digit one.
• Same length → compare them as text (Java's compareTo, or plain < in Python). With equal length, text order equals number order. For example "13" < "21".

Removing leading zeros

After a deletion, the candidate can start with zeros, like "0200". Those zeros add nothing to the value, so we strip them before comparing (and the teacher says there's no point carrying them into the next rounds either). If everything was zeros, the answer is "0".

5Approach steps

1. Repeat k times:
2. For every index i, build the candidate = num without the digit at i, and strip its leading zeros.
3. Keep the smallest candidate seen in this round (using is_smaller).
4. That smallest candidate becomes the new num.
5. After k rounds, return num (with leading zeros removed, "0" if empty).

6Code (Python)

class Solution:
    def removeKdigits(self, num, k):
        for _ in range(k):                         # one deletion per round
            best = None
            for i in range(len(num)):
                candidate = num[:i] + num[i + 1:]  # num without index i
                candidate = self.remove_leading_zeros(candidate)
                if best is None or self.is_smaller(candidate, best):
                    best = candidate
            num = best                             # next round starts from the best
        return self.remove_leading_zeros(num)

    def is_smaller(self, a, b):
        if len(a) != len(b):
            return len(a) < len(b)    # fewer digits = smaller number
        return a < b                  # same length: text order = number order

    def remove_leading_zeros(self, s):
        i = 0
        while i < len(s) and s[i] == '0':
            i += 1
        s = s[i:]
        return s if s else "0"

7Code line by line

8Dry run

The three round tables in step 4 are the dry run for num = "1432219", k = 3:

Notice: each round deleted the first digit that was bigger than the digit right after it (4 > 3, then 3 > 2, then 2 > 1). Keep that in mind, because it is exactly what Part B does in one pass.

9Complexity & remember

• Time: the teacher counts k rounds × n tries = O(k · n). With k = n = 10⁵ that is already 10¹⁰ → TLE. (Being exact, each try also builds and compares a string of length n, so it is really O(k · n²). It's even worse, and the conclusion is the same.)
• Space: O(n) for the candidate strings.

Part B · Optimal: greedy with a monotonic stack

1The question (same as Part A)

Delete k digits from num to get the smallest possible number. Now we want one pass, O(n).

2What the constraints tell us

• n up to 10⁵ and k up to n → we need about O(n). Every digit should be handled a constant number of times.
• k ≤ n always, so we can never be asked to delete more digits than exist.

3Intuition: read in small pieces, from the left

Instead of looking at the whole number, the teacher grows it one digit at a time and asks at every step: "should I delete something yet?"

• See 1. Delete anything? No. It is small, and bigger digits may still come later; if they do, those will be the ones to delete.
• See 4. Still no. The digits are going up (1, 4). Maybe a 5 or a 6 comes next, and then that would be the digit to delete. As long as the digits keep increasing, nothing before is worth deleting yet.
• See 3. Now we are sure: the 4 just before it is bigger. Deleting the 4 slides the 3 into the 4's place, so the number gets smaller. We delete the 4.

To "go back and delete the digit just before", we need the digits we kept so far, with the latest on top. That is a stack.

4Building the logic

Why the greedy pop is always safe

Say the stack's top is digit d and the new digit is c, with d > c, and we still have deletions left. Compare two futures that agree on every digit before d:

• Keep d: the position where d sits holds d.
• Delete d: c moves left into that same position, so it now holds c.

Two numbers of the same length are compared from the left, and the first position where they differ decides everything. Everything before that position is the same, and at that position c < d. So deleting d gives a smaller number, no matter what comes after. That's why we can decide right away and never need to undo it. The same works for a run of bigger digits: each one we pop lets a smaller digit move further left.

Case 1: pop while the top is bigger (WHILE, not IF)

The teacher's example: the digits 3, 4, 1. When the 1 arrives, the 4 on top is bigger → pop it. But the 3 now on top is also bigger than 1 → pop it too. One new digit can knock out several digits, so we use a while loop, not an if. The loop stops when:

• k becomes 0 (no deletions left), or
• the stack becomes empty (nothing to compare with, and peeking would crash), or
• the top is not bigger than the new digit.

Every pop uses one deletion: k -= 1. After the loop, push the new digit.

Case 2: digits already increasing → delete from the end

The teacher always checks the best, worst and average cases. Take "12345", k = 3. The digits only go up, so no new digit is ever smaller than the top, and the loop never pops. We finish with k still at 3.

What should go? When the digits are increasing, the biggest ones are at the end. Delete 5 → 1234; delete 4 → 123; delete 3 → 12. That's the smallest. So after the loop, if k > 0, chop the last k digits off the stack. This is safe because, after the loop, the stack is always in non-decreasing order.

Case 3: leading zeros

Take "10200", k = 1. The 1 goes in; the 0 arrives, 1 > 0, so pop the 1 (k = 0). The rest just gets pushed. The stack holds 0 2 0 0, which as a number is "0200". We must skip the zeros at the front → "200". If everything is zeros or the stack is empty (for example "10", k = 2), the answer is "0".

Java's StringBuilder vs a Python list

The teacher's Java code uses a StringBuilder instead of Java's Stack class. Java's Stack is synchronized (built to be thread-safe), which makes it slower. A StringBuilder can also add and delete at its end, so it works as a faster stack. Python has no StringBuilder, and its strings can't be changed in place, so her Python version uses a plain list as the stack. A list is already fast for append and pop, and ''.join(...) turns it back into a string at the end.

5Approach steps

1. Make an empty stack.
2. For each digit ch, from left to right:
3. While k > 0, the stack isn't empty, and the top is bigger than ch → pop the top and do k −= 1.
4. Push ch.
5. After the loop, if k > 0 → remove the last k digits (the stack is increasing, so the biggest are at the end).
6. Skip the leading zeros.
7. Join what is left. If it is empty, return "0".

6Code (Python)

class Solution:
    def removeKdigits(self, num, k):
        stack = []
        for ch in num:
            # a bigger digit before a smaller one: delete it (Case 1)
            while k > 0 and stack and stack[-1] > ch:
                stack.pop()
                k -= 1
            stack.append(ch)

        if k > 0:                      # Case 2: still have deletions left
            stack = stack[:-k]         # cut the last k digits

        start = 0                      # Case 3: skip leading zeros
        while start < len(stack) and stack[start] == '0':
            start += 1

        ans = ''.join(stack[start:])
        return ans if ans else "0"

7Code line by line

8Dry run: num = "1432219", k = 3

1. 1 and 4 go in. The digits are rising, so nothing is worth deleting yet.
2. 3 arrives: the 4 on top is bigger. Deleting it lets 3 take its place → pop 4 (k = 2). The top is now 1 < 3, so stop and push 3.
3. 2 arrives: the 3 on top is bigger → pop 3 (k = 1), push 2.
4. The second 2 is equal to the top → no pop, push.
5. 1 arrives: the 2 on top is bigger → pop it (k = 0). Now k is 0, so the loop stops even though the other 2 is also bigger. Push 1.
6. 9 is pushed. k = 0, so no cutting. No leading zeros. Answer "1219" ✓, the same as the brute force.

The red box is the top. The bottom of the picture is the bottom of the stack.

Dry run of Case 2: "12345", k = 3

Dry run of Case 3: "10200", k = 1

9Complexity & remember

• Time O(n): the for loop visits each digit once. The inner while loop can look heavy, but every digit is pushed once and popped at most once, so all the pops together are at most n. Going back is just popping the top, never a fresh scan. The leading-zero skip is one more pass in the worst case (for example, many zeros), so the teacher counts it as O(2n) in the worst case and O(n) normally. Both are linear.
• Space O(n): the stack (her Java StringBuilder) can hold all n digits.

Part C · Revision page

s = Solution()
print(s.removeKdigits("1432219", 3))   # 1219
print(s.removeKdigits("10200", 1))     # 200
print(s.removeKdigits("10", 2))        # 0
print(s.removeKdigits("12345", 3))     # 12
print(s.removeKdigits("54321", 3))     # 21
print(s.removeKdigits("11111", 2))     # 111
print(s.removeKdigits("341", 2))       # 1
print(s.removeKdigits("9", 0))         # 9

Based on this video: Remove K Digits | Stack + Greedy