DSA problem
Find the Most Competitive Subsequence
Given an integer array nums and a positive integer k, return the most competitive subsequence of nums of size k. A subsequence is most competitive if, when compared lexicographically to any other subsequence of the same length, it is smaller at the first index where they differ.
To minimize lexicographically, we want the smallest possible value at every prefix position, subject to the constraint that we still have enough remaining elements to fill the final length k. A greedy idea is: walk through the array maintaining a stack representing the answer so far; whenever we see a value smaller than the top, we should pop the top — but only if popping still leaves enough elements ahead to reach size k.
This is precisely a monotonic increasing stack with a deletion budget. At index i we may pop the stack top if stack.top > nums[i] and the remaining count stack.size - 1 + (n - i) is still at least k. Equivalently we can keep popping while the stack is non-empty, stack.size + (n - i) > k, and stack.top > nums[i]. We then push nums[i] as long as stack.size < k.
Because each element is pushed and popped at most once, the total work is O(n) time, and the stack holds at most k elements, giving O(k) auxiliary space. The final answer is the contents of the stack from bottom to top.
Examples
nums = [3,5,2,6], k = 2[2,6]nums = [2,4,3,3,5,4,9,6], k = 4[2,3,3,4]nums = [1,2,3,4,5], k = 3[1,2,3]Constraints
- 1 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^9
- 1 <= k <= nums.length
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.