Skip to content

The Pop Budget

From Digits to Anything

In the last lesson, you removed K digits from a number to make it as small as possible. Now let's zoom out. Forget about digits and numbers. Here's the general question:

Given an array of N elements, find the lexicographically smallest subsequence of length L.

That's it. The elements could be integers, characters, anything comparable. And "Remove K Digits" is just a special case where the elements are digit characters and L = N - K.

The insight is the same. You're building a sequence greedily from left to right, and you have a pop budget of N - L — that's how many elements you're allowed to discard.

The Pop Budget, Defined

Let's nail down the terminology.

  • N = total number of elements.
  • L = desired length of the result.
  • Budget = N - L = maximum number of elements you can remove (pops you can make).

When budget is large, you have lots of freedom. You can aggressively pop to improve the sequence. When budget is small, you're constrained — you have to keep almost everything.

Two extremes are worth thinking about:

  • Budget = 0 (L = N). You can't pop anything. The result is just the original array. No choice at all.
  • Budget = N - 1 (L = 1). You can pop everything except one element. The result is the single smallest element in the array.

Every problem lives somewhere on this spectrum. The pop budget controls how aggressively the stack can optimize.

The Algorithm

Same structure as Remove K Digits, but stated generically:

budget = N - L
stack = empty
for each element a[i] in the array:
    while budget > 0 and stack is not empty and stack.top() > a[i]:
        pop stack
        budget--
    push a[i]
trim stack to length L (remove excess from the end)
return stack

Wait — why do we need the trim step? Because the budget might not get fully used. If the array is already sorted, no pops happen, and the stack ends up with all N elements. Trimming to L removes the excess from the end, which is correct because the last elements are the least significant positions.

Walkthrough: Smallest Subsequence of Length 3 from [3, 1, 4, 1, 5, 9]

N = 6, L = 3, Budget = 3.

  1. Element 3. Stack empty. Push. Stack: [3] | Budget: 3

  2. Element 1. 1 < 3 — pop 3. Budget: 2. Stack empty. Push 1. Stack: [1] | Budget: 2

  3. Element 4. 4 > 1, no disturbance. Push. Stack: [1, 4] | Budget: 2

  4. Element 1. 1 < 4 — pop 4. Budget: 1. 1 <= 1, stop. Push 1. Stack: [1, 1] | Budget: 1

  5. Element 5. 5 > 1, push. Stack: [1, 1, 5] | Budget: 1

  6. Element 9. 9 > 5, push. Stack: [1, 1, 5, 9] | Budget: 1

Trim to length 3: [1, 1, 5].

Is that right? The lexicographically smallest subsequence of length 3 from [3, 1, 4, 1, 5, 9]. Let's verify. Could we do better than [1, 1, 5]? The two 1's are at indices 1 and 3 — we need a third element after index 3, and the smallest available is 5 (index 4). So yes, [1, 1, 5] is optimal.

The Constraint People Miss

Here's a subtlety that catches people off guard. Consider building the smallest subsequence of length 4 from [5, 3, 1, 6, 2].

N = 5, L = 4, Budget = 1.

  1. Element 5. Push. Stack: [5] | Budget: 1
  2. Element 3. 3 < 5 — pop 5. Budget: 0. Push 3. Stack: [3] | Budget: 0
  3. Element 1. Budget is 0, just push. Stack: [3, 1]
  4. Element 6. Push. Stack: [3, 1, 6]
  5. Element 2. 2 < 6, but budget is 0. Push. Stack: [3, 1, 6, 2]

Result: [3, 1, 6, 2]. That's correct. But what if we'd been too aggressive?

Imagine a scenario where you eagerly pop elements and then don't have enough left to fill the result. If your stack has size elements and there are remaining elements still to process, you need size + remaining >= L after any pop. Otherwise you'll fall short.

In the template above, this constraint is implicitly satisfied because the budget is exactly N - L. If you've popped budget times and pushed everything, you'll have exactly L elements in the stack at the end. But if you're implementing a variant where the budget calculation is less straightforward — say, elements can be skipped for reasons other than popping — you need to add an explicit guard:

// Only pop if we'll still have enough elements to fill the result
while (budget > 0 && !st.empty() && st.back() > a[i]
       && (int)st.size() - 1 + (n - i) >= L) {
    st.pop_back();
    budget--;
}

The condition st.size() - 1 + (n - i) >= L says: "If I pop this element, the remaining stack plus all unprocessed elements is still at least L." If that's false, don't pop — you can't afford to lose that element even if it's suboptimal.

For the basic "smallest subsequence of length L" problem, the budget alone handles this. But you'll see this explicit guard become necessary in harder variants (like the next lesson's Remove Duplicate Letters).

The Dual: Largest Subsequence

Everything flips cleanly. To find the lexicographically largest subsequence of length L, just reverse the comparison:

while (budget > 0 && !st.empty() && st.back() < a[i]) {
    st.pop_back();
    budget--;
}

Now you're maintaining a decreasing stack instead of an increasing one. Small elements get popped when a larger one arrives. Same budget, same trim step, opposite direction.

This duality comes up in problems like "Create Maximum Number" (next lesson), where you need the largest subsequence from each of two arrays.

Thinking in Terms of the Budget Spectrum

Here's a mental model that ties everything together.

Imagine a slider that goes from 0 to N-1. That's your budget. At budget = 0, you keep everything — no optimization, just take what you're given. At budget = N-1, maximum optimization — you cherry-pick the single best element.

The standard monotonic stack from Chapters 1-3 operates at budget = infinity. It pops freely, with no constraint on how many elements it ejects. That's why it produces structures like "nearest greater element" arrays — it resolves every disturbance it encounters.

The greedy construction problems in this chapter operate at some finite budget. They resolve disturbances in order of encounter, left to right, until the budget runs out. After that, they accept whatever comes.

This is the bridge between "query" uses of the stack and "construction" uses. Same data structure, same comparison-and-pop loop. The budget is the only new parameter.

The budget spectrum — from no pops (take first L) to unrestricted (find single minimum)

Equal Elements

One detail worth calling out. When the current element equals the stack top, should you pop?

For the smallest subsequence: no. Popping a 3 to replace it with another 3 wastes budget for zero benefit. Use strict > in the pop condition.

For the largest subsequence: same reasoning, use strict <.

If a problem asks for "smallest" with some tie-breaking rule, you might need >=, but that's rare. Default to strict inequality.

Complexity

Time: O(N). Each element enters the stack once and leaves at most once. The while loop's total iterations across the entire algorithm is bounded by N.

Space: O(N) for the stack, though the final result uses O(L).

Practice

Try this exercise before moving on. Given the array [9, 2, 5, 1, 7, 3, 8, 4], find the lexicographically smallest subsequence of length 4. Work through the algorithm by hand. You should get [1, 3, 4] — wait, that's only 3. Let me redo that.

N = 8, L = 4, Budget = 4.

  • 9: push. Stack [9], budget 4.
  • 2: pop 9 (budget 3). Push 2. Stack [2], budget 3.
  • 5: push. Stack [2, 5], budget 3.
  • 1: pop 5 (budget 2), pop 2 (budget 1). Push 1. Stack [1], budget 1.
  • 7: push. Stack [1, 7], budget 1.
  • 3: pop 7 (budget 0). Push 3. Stack [1, 3], budget 0.
  • 8: push. Stack [1, 3, 8].
  • 4: budget 0, push. Stack [1, 3, 8, 4].

Trim to 4: [1, 3, 8, 4]. Hmm, that 8 is annoying, but we ran out of budget. Can you verify that no subsequence of length 4 beats [1, 3, 8, 4] lexicographically? The 1 is the best possible first element. After index 3 (value 1), we need 3 more elements from [7, 3, 8, 4]. The smallest first pick there is 3. After the 3 (index 5), we need 2 from [8, 4] — and we must take both. So [1, 3, 8, 4] is indeed optimal.

What's Next

The pop budget gives you a clean framework for building optimal subsequences. But real problems don't always hand you a fixed budget. In the next lesson, we'll look at variants where the pop condition depends on the data itself — characters that appear later, required elements, and multi-array merges. Same core pattern, different constraints on when you're allowed to pop.