Problem Description

You are given an integer array nums and an integer k. Your task is to find the most competitive subsequence of nums of size k.

A subsequence is formed by deleting some (possibly zero) elements from nums without changing the order of the remaining elements. A subsequence a is said to be more competitive than a subsequence b if at the first position where they differ, a has a smaller number than b. There is always exactly one valid solution.

• You must not reuse elements; the subsequence must be of length k.
• Return the answer as an array of integers.

Thought Process

At first glance, you might try to generate all possible subsequences of length k and select the lexicographically smallest one. However, this brute-force approach is not practical because the number of subsequences grows exponentially with the size of nums.

We need a way to efficiently build the most competitive subsequence by making greedy choices. At each step, we want to keep our sequence as small as possible, so if we see a smaller number and still have room to remove earlier elements, we should do so.

This leads us to consider a stack-based approach, where we can remove previously chosen elements if a better (smaller) candidate appears, as long as we do not run out of elements needed for the subsequence.

Solution Approach

To efficiently construct the most competitive subsequence:

1. Use a stack: We'll maintain a stack to store the elements of our current subsequence.
2. Iterate through nums: For each number, we'll check if we can pop elements from the stack (making the sequence smaller) and still be able to fill the subsequence to length k with the remaining elements.
3. Pop when possible: If the current number is smaller than the top of the stack, and if removing the top still allows enough elements left to reach k, we pop it.
4. Push if not full: If the stack has less than k elements, we push the current number.
5. Continue until done: At the end, the stack contains the answer.

This approach is efficient because each element is pushed and popped at most once, leading to linear time complexity.

Example Walkthrough

Let's walk through an example:

Input: nums = [3, 5, 2, 6], k = 2

1. Start with an empty stack.
2. 3: Stack is empty, push 3. Stack = [3]
3. 5: Stack has 1 element, less than k, push 5. Stack = [3, 5]
4. 2: Stack is full (2 elements), but since 2 < 5 and we have enough elements left, pop 5. Stack = [3]. Now, 2 < 3 and still enough elements left, pop 3. Stack = []. Push 2. Stack = [2]
5. 6: Stack has 1 element, less than k, push 6. Stack = [2, 6]

Final answer: [2, 6]

Notice how we removed larger numbers from the left when a smaller number appeared, as long as we could still build a subsequence of length k.

Time and Space Complexity

• Brute-force approach: Generating all subsequences of length k has time complexity O(\binom{n}{k}), which is infeasible for large n.
• Optimized stack approach:
  • Each element is pushed and popped from the stack at most once, resulting in O(n) time.
  • The stack stores at most k elements, so space complexity is O(k).

Code Implementation

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        stack = []
        n = len(nums)
        for i, num in enumerate(nums):
            while stack and num < stack[-1] and len(stack) + (n - i) > k:
                stack.pop()
            if len(stack) < k:
                stack.append(num)
        return stack
      

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        vector<int> stack;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (!stack.empty() && nums[i] < stack.back() && stack.size() + (n - i) > k) {
                stack.pop_back();
            }
            if (stack.size() < k) {
                stack.push_back(nums[i]);
            }
        }
        return stack;
    }
};
      

class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        int n = nums.length;
        int[] stack = new int[k];
        int top = 0;
        for (int i = 0; i < n; i++) {
            while (top > 0 && nums[i] < stack[top - 1] && (top - 1) + (n - i) >= k) {
                top--;
            }
            if (top < k) {
                stack[top++] = nums[i];
            }
        }
        return stack;
    }
}
      

var mostCompetitive = function(nums, k) {
    let stack = [];
    let n = nums.length;
    for (let i = 0; i < n; i++) {
        while (stack.length && nums[i] < stack[stack.length - 1] && stack.length + (n - i) > k) {
            stack.pop();
        }
        if (stack.length < k) {
            stack.push(nums[i]);
        }
    }
    return stack;
};
      

Summary

The key to solving the "Most Competitive Subsequence" problem is to realize that a greedy, stack-based approach lets us efficiently construct the smallest possible subsequence of length k by always removing larger elements to the left when a better candidate appears, as long as we have enough elements left. This method is both elegant and efficient, with linear time and space complexity, making it suitable for large inputs.