python
# Pseudo-code for Brute Force
def solve(index, current_subsequence):
    if len(current_subsequence) == k:
        update_global_min(current_subsequence)
        return
    if index == len(nums):
        return
    
    # Include nums[index]
    solve(index + 1, current_subsequence + [nums[index]])
    
    # Exclude nums[index]
    solve(index + 1, current_subsequence)

Complexity Analysis: The number of subsequences of length k from an array of size N is given by the binomial coefficient $\binom{N}{k}$. In the worst case (e.g., $k = N/2$), this grows exponentially. With $N$ up to $10^5$, this approach will immediately hit a Time Limit Exceeded (TLE) error.

Core Insight for Find the Most Competitive Subsequence

The core intuition is greedy. To make a sequence lexicographically smallest, we want the smallest available numbers at the beginning of the sequence.

When iterating through nums, if we encounter a number nums[i] that is smaller than the last number we selected (the top of our stack), we should ideally discard the larger number from the stack and replace it with nums[i]. This local optimization ensures the sequence becomes "more competitive."

However, we cannot simply pop from the stack whenever we find a smaller number. We have a strict constraint: the final subsequence must have length k. We can only discard an element from the stack if the number of elements currently in the stack plus the number of elements remaining in the input array is greater than k.

The Invariant: We pop stack.top() if and only if:

1. stack is not empty.
2. nums[i] < stack.top() (Greedy condition).
3. stack.size() + (nums.length - 1 - i) >= k (Feasibility condition).

This feasibility condition ensures that even after discarding an element, we still have enough candidates left in the input to reach the target size k.

Visual Description: Imagine the stack as a container for our potential answer. As we iterate through the input array, we compare the current element with the top of the stack. If the current element is smaller, it tries to "kick out" the larger element at the top. This "kicking out" process repeats until the stack is empty, the top element is smaller than the current one, or we realize that kicking out another element would make it impossible to reach size k.

Execution Flow

Let's trace nums = [3, 5, 2, 6], k = 2. Length n = 4.

1. i = 0, val = 3:
   • Stack is empty.
   • Push 3. Stack: [3].
2. i = 1, val = 5:
   • Top is 3. 5 > 3, so no popping (we want smallest, but 5 is larger).
   • Stack size (1) < k (2). Push 5. Stack: [3, 5].
3. i = 2, val = 2:
   • Top is 5. 2 < 5.
   • Feasibility: stack.size() - 1 (remains 1) + remaining input (1 element: 6) = 2. Since 2 >= k, we can pop.
   • Pop 5. Stack: [3].
   • Top is 3. 2 < 3.
   • Feasibility: stack.size() - 1 (remains 0) + remaining input (1 element: 6) = 1. Since 1 < k, we cannot pop 3. We need 3 to reach size 2.
   • Push 2. Stack: [3, 2].
4. i = 3, val = 6:
   • Top is 2. 6 > 2. No pop.
   • Stack size (2) == k. Do not push 6.
5. End: Return [3, 2]. Wait, looking at the example logic provided in the prompt, [2, 6] is the answer. Let's re-verify the feasibility check.

Correction on Step 3 Feasibility: Current index i=2 (value 2). Remaining elements after this index is n - 1 - i = 4 - 1 - 2 = 1 (value 6).

• Stack: [3, 5]. Top 5. 2 < 5.
  • If we pop 5, stack becomes [3]. New size 1.
  • Can we fill to k=2? We have stack size 1 + remaining 1 = 2. Yes.
  • Pop 5. Stack [3].
• Stack: [3]. Top 3. 2 < 3.
  • If we pop 3, stack becomes []. New size 0.
  • Can we fill to k=2? We have stack size 0 + remaining 1 (the 6) + current element 2.
  • Correct Logic: The condition is stack.size() + (n - i) > k.
  • Current i=2. n=4. k=2. n-i = 2.
  • Check pop 5: Stack size 2. 2 + 2 > 2. True. Pop 5.
  • Check pop 3: Stack size 1. 1 + 2 > 2. True. Pop 3.
  • Stack is empty. Push 2. Stack [2].
• i = 3, val = 6:
  • Push 6. Stack [2, 6].
• Result [2, 6]. Matches Example 1.

Proof of Correctness

The algorithm produces the correct result due to the properties of the Monotonic Stack and the greedy choice property.

1. Lexicographical Smallest: By enforcing the monotonic increasing property, we ensure that for any two adjacent elements in our subsequence, the earlier one is smaller than the later one wherever possible.
2. Feasibility: The condition stack.size() + (nums.length - i) > k guarantees that we never discard an element if doing so would make it impossible to construct a subsequence of length k. This ensures the final output is always a valid subsequence of the required length.
3. Optimal Substructure: The decision to keep or discard an element is made locally based on the current top of the stack and the remaining counts, which leads to the globally optimal solution for this specific constraint.

Reference Implementation

C++ Solution for LeetCode 1673

cpp
#include <vector>

class Solution {
public:
    std::vector<int> mostCompetitive(std::vector<int>& nums, int k) {
        std::vector<int> stack;
        int n = nums.size();
        
        for (int i = 0; i < n; ++i) {
            // While stack is not empty, current val is smaller than top,
            // and we have enough remaining elements to fill the stack to size k
            while (!stack.empty() && nums[i] < stack.back() && 
                   stack.size() + (n - i) > k) {
                stack.pop_back();
            }
            
            // Only push if we haven't filled the required length k
            if (stack.size() < k) {
                stack.push_back(nums[i]);
            }
        }
        
        return stack;
    }
};

Java Solution for LeetCode 1673

java
import java.util.Stack;

class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        // Using an array as a stack for performance optimization
        int[] stack = new int[k];
        int top = -1; // Points to the index of the top element
        int n = nums.length;
        
        for (int i = 0; i < n; i++) {
            // Monotonic stack logic:
            // Pop if current element is smaller than stack top
            // AND we have enough remaining elements (n - i) to fill the rest
            // Current stack size is (top + 1).
            // Condition: (top + 1) + (n - i) > k
            while (top >= 0 && nums[i] < stack[top] && (top + 1) + (n - i) > k) {
                top--;
            }
            
            // Push current element if there is space
            if (top < k - 1) {
                top++;
                stack[top] = nums[i];
            }
        }
        
        return stack;
    }
}

Python Solution for LeetCode 1673

python
class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        stack = []
        n = len(nums)
        
        for i, val in enumerate(nums):
            # While stack has elements, current val is smaller than top,
            # and we have enough remaining elements to satisfy length k.
            # Feasibility: len(stack) + (remaining items) > k
            # Remaining items including current 'val' is (n - i)
            while stack and val < stack[-1] and len(stack) + (n - i) > k:
                stack.pop()
            
            if len(stack) < k:
                stack.append(val)
                
        return stack