Solution Explanation: Finding the Most Competitive Subsequence

This problem asks us to find the lexicographically smallest subsequence of length k from the input array nums. The solution uses a greedy approach with a stack to efficiently achieve this.

Algorithm:

The core idea is to maintain a stack (stk) that stores the currently most competitive subsequence seen so far. We iterate through the input array nums. For each number nums[i]:

1. Check for Improvement: While the stack is not empty, the top element of the stack is greater than the current number (nums[i]), and removing the top element from the stack will still allow us to form a subsequence of length k (i.e., len(stk) + (n - i) > k, where n is the length of nums), we pop the top element. This step ensures that we are always building a subsequence with the smallest possible numbers at each position.

2. Push onto Stack: If the stack has fewer than k elements, we push the current number (nums[i]) onto the stack. This ensures that we maintain a subsequence of length k.

3. Final Result: After iterating through the entire array, the stack contains the most competitive subsequence. We return the stack's content.

Time Complexity: O(n), where n is the length of nums. In the worst-case scenario, we iterate through the array once, and each element is pushed and potentially popped from the stack at most once. The operations on the stack (push and pop) take constant time O(1).

Space Complexity: O(k). The maximum size of the stack is k, as we are only interested in subsequences of length k.

Code Examples:

The following code demonstrates the solution in various programming languages. The logic remains consistent across all implementations.

Python:

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

Java:

import java.util.ArrayDeque;
import java.util.Deque;
 
class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        Deque<Integer> stk = new ArrayDeque<>();
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (!stk.isEmpty() && stk.peek() > nums[i] && stk.size() + n - i > k) {
                stk.pop();
            }
            if (stk.size() < k) {
                stk.push(nums[i]);
            }
        }
        int[] ans = new int[stk.size()];
        for (int i = ans.length - 1; i >= 0; --i) {
            ans[i] = stk.pop();
        }
        return ans;
    }
}

C++:

#include <vector>
#include <stack>
 
class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        stack<int> stk;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && stk.top() > nums[i] && stk.size() + n - i > k) {
                stk.pop();
            }
            if (stk.size() < k) {
                stk.push(nums[i]);
            }
        }
        vector<int> ans;
        while (!stk.empty()) {
            ans.push_back(stk.top());
            stk.pop();
        }
        reverse(ans.begin(), ans.end()); // Reverse to maintain original order
        return ans;
    }
};
 

Go:

func mostCompetitive(nums []int, k int) []int {
	stk := []int{}
	n := len(nums)
	for i, v := range nums {
		for len(stk) > 0 && stk[len(stk)-1] > v && len(stk)+n-i > k {
			stk = stk[:len(stk)-1]
		}
		if len(stk) < k {
			stk = append(stk, v)
		}
	}
	return stk
}

These examples all implement the same core algorithm with minor syntactic differences due to language features. They all achieve linear time complexity and use space proportional to k.