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.
This approach uses a stack to build the competitive subsequence. The basic idea is to iterate through the array and maintain a stack where the final size is k. For each element, we decide whether it should be added to the stack or replace the top element of the stack, which ensures the stack remains a competitive sequence.
We will replace the top element of the stack if the current element is smaller and there are enough elements left to fill the required subsequence size.
This method ensures that the maintained sequence is minimal and competitive, based on the problem constraints.
This solution defines a function mostCompetitive that iteratively builds the most competitive subsequence using a stack-like array. It uses a top pointer to simulate stack operations. During the construction, we only add elements when they are appropriate to maintain the most competitive sequence.
The loop checks if the current element should replace the stack's last element by looking at the number of elements left and ensuring the stack will have the required size k.
Time Complexity: O(n) where n is the number of elements in nums.
Space Complexity: O(k) to store the competitive subsequence.
This approach builds upon the idea that maintaining a competitive subsequence can be achieved by iteratively reducing and replacing elements in a greedy fashion, focusing directly on modifications to an output array.
This strategy is slightly different from a pure stack-based approach as it directly handles result index placement while keeping track of candidates for subsequences and managing the required number of subsequence slots.
The approach uses an array result to directly keep track of current selections. It employs a similar logic as before, but in terms of placement, directly filling array slots and managing index replacement based on element choices.
This provides direct insight into how the subsequence is filled.
Time Complexity: O(n).
Space Complexity: O(k).
We traverse the array nums from left to right, maintaining a stack stk. During the traversal, if the current element nums[i] is less than the top element of the stack, and the number of elements in the stack plus n-i is greater than k, then we pop the top element of the stack until the above condition is no longer satisfied. At this point, if the number of elements in the stack is less than k, then we push the current element into the stack.
After the traversal, the elements in the stack are the answer.
The time complexity is O(n), and the space complexity is O(k). Where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Using a Stack for Maintaining Order | Time Complexity: Space Complexity: |
| Greedy Strategy with Direct Modification | Time Complexity: Space Complexity: |
| Stack | — |
| 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. |
Lexicographically Smallest Subsequence | Find the Most Competitive Subsequence | Leetcode 1673 • Pepcoding • 10,888 views views
Watch 9 more video solutions →Practice Find the Most Competitive Subsequence with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor