1673. Find the Most Competitive Subsequence LeetCode Solution
In this guide, you will get 1673. Find the Most Competitive Subsequence LeetCode Solution with the best time and space complexity. The solution to Find the Most Competitive Subsequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
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]
1673. Find the Most Competitive Subsequence LeetCode Solution in C++
class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
vector<int> ans;
for (int i = 0; i < nums.size(); ++i) {
// If |ans| - 1 + |nums[i..n)| >= k, then it means we still have enough
// numbers, and we can safely pop an element from ans.
while (!ans.empty() && ans.back() > nums[i] &&
ans.size() - 1 + nums.size() - i >= k)
ans.pop_back();
if (ans.size() < k)
ans.push_back(nums[i]);
}
return ans;
}
}; /* code provided by PROGIEZ */
1673. Find the Most Competitive Subsequence LeetCode Solution in Java
class Solution {
public int[] mostCompetitive(int[] nums, int k) {
int[] ans = new int[k];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < nums.length; ++i) {
// If |stack| - 1 + |nums[i..n)| >= k, then it means we still have enough
// numbers, and we can safely pop an element from stack.
while (!stack.isEmpty() && stack.peek() > nums[i] && stack.size() - 1 + nums.length - i >= k)
stack.pop();
if (stack.size() < k)
stack.push(nums[i]);
}
for (int i = 0; i < k; i++)
ans[i] = stack.pollLast();
return ans;
}
} // code provided by PROGIEZ
1673. Find the Most Competitive Subsequence LeetCode Solution in Python
class Solution:
def mostCompetitive(self, nums: list[int], k: int) -> list[int]:
ans = []
for i, num in enumerate(nums):
# If |ans| - 1 + |nums[i..n)| >= k, then it means we still have enough
# numbers, and we can safely pop an element from ans.
while ans and ans[-1] > nums[i] and len(ans) - 1 + len(nums) - i >= k:
ans.pop()
if len(ans) < k:
ans.append(nums[i])
return ans # code by PROGIEZ
