Find the Most Competitive Subsequence
Understanding the Problem
We need to pick exactly k elements from nums while keeping their original relative order, and the resulting subsequence should be the lexicographically smallest possible. When two subsequences of the same length are compared, the more competitive one has the smaller value at the first position where they differ.
This is a greedy selection problem with a constraint. At each position in the result we want the smallest possible value, but we also have to leave enough elements remaining to fill the rest of the subsequence. Picking the smallest value now and keeping enough elements for later pull in opposite directions, and balancing the two is the core of the problem.
That balance maps onto building a stack that stays as small as possible at the front, subject to a capacity of k. When a smaller element arrives, we can remove larger elements already chosen, as long as enough elements remain in the array to complete the subsequence.
Key Constraints:
1 <= nums.length <= 10^5means an O(n^2) approach will time out. The target is O(n).0 <= nums[i] <= 10^9means values fit in a 32-bit signed integer, and there are no negatives. The range is too wide for counting sort or a frequency array.1 <= k <= nums.lengthguaranteeskis always valid, so there is nok > ncase to handle.
Approach 1: Brute Force (Generate All Subsequences)
Intuition
Generate every possible subsequence of size k, compare them lexicographically, and return the smallest one. This enumerates all candidates and picks the winner with no cleverness.
For an array of size n, the number of subsequences of size k is C(n, k), which grows exponentially. For small inputs it works and confirms what the answer should be, which is useful for checking the optimal approach against it.
Algorithm
- Use backtracking to generate all subsequences of size
kfromnums. - For each subsequence, compare it with the current best using lexicographic comparison.
- Keep track of the lexicographically smallest subsequence found.
- Return the result after checking all candidates.
Example Walkthrough
Input:
All subsequences of size 2: [3,5], [3,2], [3,6], [5,2], [5,6], [2,6]
Comparing lexicographically: [2,6] is the smallest (2 < 3 < 5 at the first position).
Result:
Code
- Time Complexity: O(C(n, k) * k). We generate all C(n, k) subsequences, and comparing each against the current best takes O(k) time. C(n, k) is exponential in the worst case, so this only runs on small inputs.
- Space Complexity: O(k). The recursion depth is at most k, and we store the current subsequence of size k.
The brute force enumerates an exponential number of subsequences, most of which are far from optimal. The next approach builds the answer greedily in a single pass, always preferring a smaller value at an earlier position whenever there is still room to complete the subsequence.
Approach 2: Monotonic Stack (Optimal)
Intuition
Build the result left to right. While scanning nums, when a value is smaller than one already chosen, replacing the larger earlier pick with this smaller value produces a more competitive subsequence. The replacement is only allowed when enough elements remain in the array to still fill all k spots.
A monotonic stack implements this directly. The stack holds the current best subsequence so far. For each element in the array:
- If the current element is smaller than the top of the stack, and enough elements remain to still fill
kpositions, pop the top (it is a larger value at an earlier position, so removing it helps). - Push the current element onto the stack, unless the stack already holds
kelements.
The remaining-elements check is what keeps the answer valid. With n - i elements left in the array (including the current one) and stack.size() elements already chosen, a pop is allowed only when stack.size() - 1 + (n - i) >= k. After removing one element, the elements still on the stack plus the elements still ahead in the array must be enough to reach size k.
Lexicographic comparison is decided by the first position where two subsequences differ, so a smaller value at an earlier position outweighs any difference later. Reducing the value at the earliest position we can therefore never makes the result worse. When a smaller element arrives and a larger earlier pick can still be replaced without making the subsequence impossible to complete, replacing it strictly improves that earliest differing position.
The check size - 1 + (n - i) >= k enforces the size requirement: it allows a pop only when the elements left on the stack plus the elements still ahead can reach k. If a pop would make a size-k subsequence impossible, the larger value stays.
Each element is pushed at most once and popped at most once, so the total push and pop work is O(n) even though a single iteration can pop several elements.
Algorithm
- Initialize an empty stack (or list used as a stack).
- Iterate through each element
nums[i]: - While the stack is not empty, AND the top of the stack is greater than
nums[i], ANDstack.size() - 1 + (n - i) >= k(we can afford to pop): pop the top of the stack. - If the stack size is less than
k, pushnums[i]onto the stack. - Return the stack as the result array.
Example Walkthrough
Code
- Time Complexity: O(n). Each element is pushed onto the stack at most once and popped at most once. So across all iterations, the total number of push and pop operations is at most 2n. Every other operation inside the loop is O(1).
- Space Complexity: O(k). The stack holds at most k elements. In the Java and C# implementations, we pre-allocate an array of size k. In other languages, the dynamic array or list grows up to size k.