Find the Most Competitive Subsequence: Monotonic Stack Pattern

Given an integer array nums and a positive integer k, return the most competitive subsequence of nums of size k. A subsequence is more competitive than another subsequence of the same length if, at the first position where they differ, the first subsequence has a smaller value.

This is LeetCode 1673: Find the Most Competitive Subsequence.

Why this problem matters

At first glance, "find the smallest subsequence of length k" sounds like it might need brute force over all possible subsequences. There are C(n, k) of them, which blows up fast. But the problem has a greedy structure hiding underneath: at every position, you want the smallest value you can afford to place there without running out of elements for the remaining slots.

That greedy structure maps perfectly to a monotonic stack. You scan left to right, and whenever the current element is smaller than the top of the stack, you pop the top -- as long as you still have enough elements left in the array to fill the remaining slots. This "budget check" is what separates this problem from a plain monotonic stack. It is the same pattern you see in Remove K Digits (LeetCode 402) and Remove Duplicate Letters (LeetCode 316), and once you internalize it, all three problems become variations of the same idea.

The key insight

You maintain a stack that will become your answer. As you iterate through nums, you compare the current element to the top of the stack. If the current element is smaller, you want to pop the top and replace it -- but only if you can. The constraint is: len(stack) - 1 + remaining_elements >= k. In other words, after popping, there must still be enough elements left (including the current one and everything after it) to reach a total of k. If there are, pop. If not, you are stuck with what you have.

This "remaining elements budget" is the key guard. Without it, you might pop too aggressively and end up with fewer than k elements. With it, you greedily minimize each position of the subsequence from left to right.

The solution

def most_competitive(nums: list[int], k: int) -> list[int]:
    stack = []
    n = len(nums)

    for i, val in enumerate(nums):
        remaining = n - i
        while stack and val < stack[-1] and len(stack) - 1 + remaining >= k:
            stack.pop()
        if len(stack) < k:
            stack.append(val)

    return stack

Let's walk through what each piece does.

The outer loop processes each element of nums from left to right. For each element, remaining counts how many elements are left in the array from position i onward (including nums[i] itself).

The while loop is the greedy popping logic. It runs as long as three conditions hold: the stack is not empty, the current value is smaller than the top of the stack, and popping would still leave enough room to fill k slots. The expression len(stack) - 1 + remaining >= k says: "If I pop one element, my stack shrinks by one, but I still have remaining elements to pick from. Is that enough to reach k total?" If yes, pop and try again.

After the while loop, if the stack has fewer than k elements, we push the current value. The len(stack) < k guard ensures we never exceed k elements in the stack.

Visual walkthrough

Let's trace through nums = [3, 5, 2, 6] with k = 2. Watch how the stack evolves as we process each element and apply the budget check before popping.

The critical moment is step 3. When we encounter 2, we check: can we pop 5? The stack would go from length 2 to 1, and there are 2 remaining elements (2 and 6). So 1 + 2 = 3 >= 2. Yes, pop. Can we pop 3? The stack would go from length 1 to 0, and there are still 2 remaining elements. 0 + 2 = 2 >= 2. Yes, pop. Now we push 2. This greedy popping is what produces the optimal answer.

Complexity analysis

Time is O(n). Each element is pushed onto the stack at most once and popped at most once. Even though there is a while loop inside the for loop, the total number of pops across the entire run cannot exceed n, because you cannot pop more elements than you pushed. This gives amortized O(1) work per element.

Space is O(k). The stack never holds more than k elements, since we guard against that with the len(stack) < k check before pushing.

The building blocks

1. Monotonic stack with budget

The core pattern: pop from the stack when the current element is smaller, but only if you can afford to.

while stack and val < stack[-1] and len(stack) - 1 + remaining >= k:
    stack.pop()

This is the greedy engine. The val < stack[-1] condition ensures you only pop when you can improve the subsequence. The budget condition len(stack) - 1 + remaining >= k ensures you never pop so much that you cannot fill k slots. Together, they guarantee that every pop makes the result strictly more competitive without making it impossible to complete.

2. Remaining elements check

The guard that prevents overfilling and underfilling:

remaining = n - i
if len(stack) < k:
    stack.append(val)

The remaining variable tells you how many elements are available from the current position to the end of the array. The append guard len(stack) < k ensures the stack never exceeds k elements. If the stack already has k elements and the current value is not small enough to trigger a pop, we simply skip it. These two checks work in tandem with the while loop to produce exactly k elements.

Edge cases

• k equals n: You must take every element. The stack never pops because len(stack) - 1 + remaining would drop below k. The answer is the original array.
• Already sorted array: No pops ever happen because each new element is larger than the top. The answer is the first k elements.
• Reverse sorted array: Maximum popping. Each new element triggers pops until the budget runs out, producing the smallest possible tail of the array.
• All elements identical: No pops because val < stack[-1] is never true. The answer is k copies of that element.
• k = 1: You want the single smallest element in the array. The stack will pop everything until only the minimum remains.

From understanding to recall

You now understand the monotonic stack with a budget. The idea is clean: greedily keep the smallest values at each position, popping larger values from the stack as long as you can still fill k slots. But understanding it once and writing it from scratch under time pressure are different skills.

The details that trip people up: Is the budget check >= or >? Do you use remaining or remaining - 1? Do you check len(stack) < k before or after the while loop? These are not conceptual misunderstandings. They are recall gaps, and they cost you time in interviews. Spaced repetition closes those gaps. You practice writing the stack loop and the budget guard from memory, at increasing intervals, until the code flows out without hesitation.

Related posts

• Remove K Digits - The classic monotonic stack budget problem where you remove k digits to make the smallest number
• Daily Temperatures - A pure monotonic stack problem that builds your intuition for stack-based greedy patterns
• Remove Duplicate Letters - Another monotonic stack variant with a constraint on which elements you can pop

CodeBricks breaks Find the Most Competitive Subsequence into its monotonic stack and budget check building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy stack problem shows up in your interview, you do not think about it. You just write it.