Watch 10 video solutions for Find the Most Competitive Subsequence, a medium level problem involving Array, Stack, Greedy. This walkthrough by Pepcoding has 10,888 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array nums and a positive integer k, return the most competitive subsequence of nums of size k.
An array's subsequence is a resulting sequence obtained by erasing some (possibly zero) elements from the array.
We define that a subsequence a is more competitive than a subsequence b (of the same length) if in the first position where a and b differ, subsequence a has a number less than the corresponding number in b. For example, [1,3,4] is more competitive than [1,3,5] because the first position they differ is at the final number, and 4 is less than 5.
Example 1:
Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.
Example 2:
Input: nums = [2,4,3,3,5,4,9,6], k = 4 Output: [2,3,3,4]
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1091 <= k <= nums.lengthProblem Overview: Given an integer array nums and an integer k, return the most competitive subsequence of length k. A subsequence is considered more competitive if at the first position where two subsequences differ, the one with the smaller number is chosen.
Approach 1: Using a Stack for Maintaining Order (Greedy + Monotonic Stack) (Time: O(n), Space: O(k))
This approach builds the answer using a monotonic increasing stack. You iterate through the array and maintain a stack that stores the current best subsequence. While the current element is smaller than the top of the stack and you still have enough remaining elements to fill k, pop the stack. This ensures larger elements earlier in the subsequence get replaced with smaller ones, making the sequence lexicographically smaller. After handling removals, push the current number if the stack size is still less than k. Each element is pushed and popped at most once, giving O(n) time complexity and O(k) space. This pattern appears frequently in monotonic stack problems and is a standard technique when maintaining optimal order while scanning an array.
Approach 2: Greedy Strategy with Direct Modification (Time: O(n), Space: O(k))
This approach applies the same greedy principle but manages the result array directly instead of an explicit stack structure. Iterate through nums while tracking how many elements can still be removed. If the current element is smaller than the last element in the result and removals are still allowed, remove the previous element to improve competitiveness. Continue this process until the order condition is satisfied. Then append the current number if the result size is below k. Conceptually, this is still a stack-like process but implemented using direct array modification. The algorithm processes each element once, producing O(n) time complexity with O(k) extra space.
The key insight behind both solutions is greedy ordering: whenever a smaller value appears and removing a previous value still allows building a length k subsequence, removing the larger value improves the final sequence. The constraint on remaining elements ensures the subsequence length remains achievable.
Recommended for interviews: The monotonic stack approach is what most interviewers expect. It demonstrates understanding of greedy decisions, stack-based ordering, and array traversal patterns. Recognizing when to remove earlier elements to maintain a lexicographically smaller sequence is a common theme in greedy and stack problems. Explaining why each element is pushed and popped at most once clearly shows mastery of the O(n) optimal solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack for Maintaining Order (Monotonic Stack) | O(n) | O(k) | General optimal solution. Best when maintaining lexicographically smallest subsequence while scanning once. |
| Greedy Strategy with Direct Modification | O(n) | O(k) | When implementing greedy logic without explicitly using a stack structure. |