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.lengthThis 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(k).
| Approach | Complexity |
|---|---|
| Using a Stack for Maintaining Order | Time Complexity: Space Complexity: |
| Greedy Strategy with Direct Modification | Time Complexity: Space Complexity: |
Leetcode 1673. Find the Most Competitive Subsequence • Fraz • 6,637 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