Find the Most Competitive Subsequence
Problem
You are given an integer array nums and an integer k. Pick exactly k elements from nums, keeping their original order, so that the chosen subsequence is the most competitive one possible. One subsequence beats another if, at the first index where they differ, it holds the smaller number — in other words, return the lexicographically smallest subsequence of length k.
The trick: scan left to right with an increasing stack. Pop a stack top whenever the new value is smaller and the elements still unread are enough to fill all k slots; only push while fewer than k elements have been kept.
nums = [3, 5, 2, 6], k = 2[2, 6]def most_competitive(nums, k):
stack = []
n = len(nums)
for i, x in enumerate(nums):
while stack and stack[-1] > x and len(stack) + (n - i) > k:
stack.pop()
if len(stack) < k:
stack.append(x)
return stackfunction mostCompetitive(nums, k) {
const stack = [];
const n = nums.length;
for (let i = 0; i < n; i++) {
const x = nums[i];
while (stack.length && stack[stack.length - 1] > x && stack.length + n - i > k) {
stack.pop();
}
if (stack.length < k) stack.push(x);
}
return stack;
}int[] mostCompetitive(int[] nums, int k) {
int[] stack = new int[k];
int top = 0, n = nums.length;
for (int i = 0; i < n; i++) {
int x = nums[i];
while (top > 0 && stack[top - 1] > x && top + n - i > k) {
top--;
}
if (top < k) stack[top++] = x;
}
return stack;
}vector<int> mostCompetitive(vector<int>& nums, int k) {
vector<int> stack;
int n = nums.size();
for (int i = 0; i < n; i++) {
int x = nums[i];
while (!stack.empty() && stack.back() > x && (int)stack.size() + n - i > k) {
stack.pop_back();
}
if ((int)stack.size() < k) stack.push_back(x);
}
return stack;
}Explanation
"Most competitive" is just lexicographically smallest, and lexicographic order is decided by the earliest positions. So we greedily want the smallest possible value first, then the smallest possible second value, and so on. A monotonic increasing stack realizes this greed in a single left-to-right pass: the stack always holds the best prefix of the answer found so far.
When a new value x arrives and the stack top is larger than x, keeping that top is a mistake — replacing it with x makes the subsequence smaller at an earlier position. But we can only afford to pop if there are still enough elements left to fill all k slots. With i the current index, the elements from i to the end number n − i, so popping is safe exactly while stack_size + (n − i) > k.
After popping, we push x only if fewer than k elements are kept; if the stack already has k elements (and the top is ≤ x), the new value cannot improve anything and is skipped. Because pushes happen at most k times after the popping rule has run, the stack ends with exactly k elements — the answer.
Walk through nums = [3, 5, 2, 6], k = 2: push 3, then push 5 (it is larger, no pop). When 2 arrives, top 5 > 2 and 2 kept + 2 unread = 4 > 2, so pop 5; then top 3 > 2 and 1 + 2 = 3 > 2, so pop 3 as well; push 2. Finally 6 arrives, the stack has only one element, so push 6. The answer is [2, 6].
Notice how the remaining-count guard mattered: without it we would happily pop everything for a late small value and finish with fewer than k picks. With it, a small value that appears too late simply cannot evict earlier picks.
Every element is pushed at most once and popped at most once, so the pass costs O(n) time. The stack never exceeds k entries after the guard, giving O(k) extra space.