Problem Description

You are given an integer array nums and a positive integer k. Your task is to find the most competitive subsequence of nums that has exactly k elements.

A subsequence is a sequence derived from the original array by deleting some (possibly zero) elements without changing the order of the remaining elements.

When comparing two subsequences of the same length, one subsequence is considered more competitive than another if, at the first position where they differ, it has a smaller number. For example:

• [1,3,4] is more competitive than [1,3,5] because they first differ at the last position, where 4 < 5
• [2,3] is more competitive than [3,4] because they first differ at the first position, where 2 < 3

The solution uses a monotonic stack approach. As we traverse the array, we maintain a stack that will eventually contain our answer. For each element:

• We check if we can remove larger elements from the stack to make our subsequence more competitive
• We only remove an element from the stack if: the current element is smaller than the stack's top element AND we have enough remaining elements to still form a subsequence of size k
• The condition len(stk) + n - i > k ensures we don't remove too many elements - it checks that the current stack size plus the remaining unprocessed elements is greater than k
• We only add the current element if the stack size is less than k

This greedy approach ensures we always try to keep smaller elements earlier in our subsequence, making it as competitive as possible.

Intuition

The key insight is that we want to build the lexicographically smallest subsequence of size k. To make a subsequence as competitive as possible, we should prioritize placing smaller numbers at earlier positions.

Think of it like building a team where you can only pick k players from a lineup. You want the strongest possible team, and strength is determined by comparing players position by position from left to right. The first difference determines which team is better.

As we scan through the array, we face a decision at each element: should we include it in our subsequence or not? If we encounter a smaller element, we might want to go back and remove some larger elements we've already chosen - but only if we have enough elements remaining to still form a complete subsequence of size k.

This naturally leads to a stack-based greedy approach. The stack represents our current candidate subsequence. When we see a new element:

1. If it's smaller than what's on top of our stack, we'd prefer to use this smaller element instead - it would make our subsequence more competitive
2. But we can only remove the larger element if we'll still have enough elements left to reach size k
3. The condition len(stk) + n - i > k checks exactly this: current stack size + remaining elements must be greater than k for us to safely remove an element

This greedy strategy works because once we've chosen to keep a smaller element at an earlier position, we never need to reconsider that decision. Any subsequence with a larger element at that position would be less competitive, regardless of what comes after.

The beauty of this approach is that it processes each element exactly once while maintaining the optimal subsequence at each step, giving us an efficient O(n) solution.

Learn more about Stack, Greedy and Monotonic Stack patterns.

Solution Approach

We use a monotonic stack to build the most competitive subsequence. The stack maintains our current candidate subsequence as we traverse the array from left to right.

Here's the step-by-step implementation:

1. Initialize an empty stack stk to store our subsequence and get the array length n.

2. Traverse the array using enumeration to have both index i and value v:

   for i, v in enumerate(nums):

3. For each element, check if we should remove elements from the stack:

   while stk and stk[-1] > v and len(stk) + n - i > k:
       stk.pop()

   This condition has three parts:

   • stk - stack is not empty
   • stk[-1] > v - the top element is larger than the current element (we found a more competitive option)
   • len(stk) + n - i > k - we have enough remaining elements to still form a subsequence of size k
     • n - i represents the number of elements left to process (including current)
     • If len(stk) + n - i = k, we can't afford to remove any more elements

4. Add the current element if there's room:

   if len(stk) < k:
       stk.append(v)

   We only add the current element if we haven't reached the required size k yet.

5. Return the stack which now contains the most competitive subsequence of size k.

Example walkthrough with nums = [3,5,2,6] and k = 2:

• Process 3: stack = [3]
• Process 5: stack = [3,5] (reached size k)
• Process 2: 2 < 5 and we can afford to remove (4 - 2 + 1 > 2), so pop 5; then 2 < 3 and we can afford to remove (3 - 2 + 1 > 2), so pop 3; add 2: stack = [2]
• Process 6: add 6: stack = [2,6]
• Result: [2,6]

The time complexity is O(n) since each element is pushed and popped at most once. The space complexity is O(k) for the stack.

Example Walkthrough

Let's walk through the solution with nums = [2, 4, 3, 3, 5, 4, 9, 6] and k = 4.

We'll use a stack to build our competitive subsequence, checking at each step if we can make improvements.

Initial state: stk = [], n = 8

Step 1: Process nums[0] = 2

• Stack is empty, add 2
• stk = [2]

Step 2: Process nums[1] = 4

• Check: Can we remove 2? No, because 4 > 2 (we want smaller elements)
• Stack size (1) < k (4), so add 4
• stk = [2, 4]

Step 3: Process nums[2] = 3

• Check: Can we remove 4? Yes! Because 3 < 4 AND len(stk) + n - i = 2 + 8 - 2 = 8 > k
• Pop 4, now stk = [2]
• Check: Can we remove 2? No, because 3 > 2
• Stack size (1) < k (4), so add 3
• stk = [2, 3]

Step 4: Process nums[3] = 3

• Check: Can we remove 3? No, because 3 = 3 (not smaller)
• Stack size (2) < k (4), so add 3
• stk = [2, 3, 3]

Step 5: Process nums[4] = 5

• Check: Can we remove 3? No, because 5 > 3
• Stack size (3) < k (4), so add 5
• stk = [2, 3, 3, 5] (reached size k!)

Step 6: Process nums[5] = 4

• Check: Can we remove 5? Yes! Because 4 < 5 AND len(stk) + n - i = 4 + 8 - 5 = 7 > k
• Pop 5, now stk = [2, 3, 3]
• Check: Can we remove 3? No, because 4 > 3
• Stack size (3) < k (4), so add 4
• stk = [2, 3, 3, 4]

Step 7: Process nums[6] = 9

• Check: Can we remove 4? No, because 9 > 4
• Stack size already equals k, don't add 9
• stk = [2, 3, 3, 4]

Step 8: Process nums[7] = 6

• Check: Can we remove 4? No, because 6 > 4
• Stack size already equals k, don't add 6
• stk = [2, 3, 3, 4]

Final result: [2, 3, 3, 4]

This subsequence is the most competitive because it starts with the smallest possible elements while maintaining the original order and having exactly k elements.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the array once with the for loop, visiting each element exactly once. Although there's a while loop inside that performs pop operations, each element can be pushed onto the stack at most once and popped at most once throughout the entire execution. This means the total number of operations across all iterations is at most 2n, resulting in an amortized time complexity of O(n), where n is the length of the array nums.

Space Complexity: O(k)

The stack stk is constrained to never exceed size k due to the condition if len(stk) < k before appending elements. The maximum space used by the stack is therefore k elements. The only other variables used are constants (i, v, n), which take O(1) space. Thus, the overall space complexity is O(k), where k is the desired size of the most competitive subsequence.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Remaining Elements Calculation

The Problem: A common mistake is incorrectly calculating the number of remaining elements when deciding whether to pop from the stack. Developers often write:

• n - i - 1 (off by one, excludes current element)
• n - i + 1 (off by one, counts one extra)
• len(stack) + (n - i - 1) >= k (using >= instead of >)

Why It Happens: The confusion arises from zero-based indexing. When at index i, there are n - i elements remaining (including the current one), not n - i - 1.

Incorrect Example:

while stack and stack[-1] > value and len(stack) + n - i - 1 > k:
    stack.pop()

This would keep one more element than necessary, potentially missing optimal solutions.

Correct Solution:

while stack and stack[-1] > value and len(stack) + n - i > k:
    stack.pop()

Pitfall 2: Forgetting the Stack Size Check Before Appending

The Problem: Adding elements unconditionally without checking if the stack has reached size k:

# Wrong - adds all elements that survive the while loop
for i, v in enumerate(nums):
    while stack and stack[-1] > v and len(stack) + n - i > k:
        stack.pop()
    stack.append(v)  # Missing size check!

Why It Happens: It's easy to assume that after popping larger elements, we should always add the current element. However, we might already have k elements in our stack.

Example of Failure: With nums = [2,4,3,3,5,4,9,6] and k = 4, without the size check, you might end up with more than 4 elements.

Correct Solution: Always check the stack size before appending:

if len(stack) < k:
    stack.append(v)

Pitfall 3: Using Wrong Comparison in the While Loop Condition

The Problem: Using >= instead of > in the remaining elements check:

# Wrong - too conservative
while stack and stack[-1] > value and len(stack) + n - i >= k:
    stack.pop()

Why It Happens: The logic seems intuitive: "if we have at least k elements total, we can pop." But this is incorrect.

The Issue: When len(stack) + n - i == k, we have exactly enough elements to form our subsequence. If we pop now, we'll be left with fewer than k elements total, making it impossible to form a valid subsequence.

Correct Solution: Use strict inequality:

while stack and stack[-1] > value and len(stack) + n - i > k:
    stack.pop()

We can only pop when we have MORE than k elements available in total.