Find The Most Competitive Subsequence - Leetcode Solution

Problem Statement: 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 array formed by choosing any elements from the array without changing their relative order. The most competitive subsequence is the one that has the smallest possible values of all the k-length subsequences.

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]

Approach:

• We will create a stack to hold the elements of the most competitive subsequence.
• We will iterate through each element of the input array nums.
• While iterating, if there are still enough elements left in nums to form a k-length subsequence, we will compare the current element with the elements in the stack to see if it is more competitive. If it is, we will remove the less competitive element from the stack until the remaining elements in the stack plus the remaining elements in nums will be enough to form a k-length subsequence.
• If there are not enough elements left in nums to form a k-length subsequence, we will just append the current element to the stack.
• Once the iteration is completed, we will return the elements in the stack.

Code:

class Solution: def mostCompetitive(self, nums: List[int], k: int) -> List[int]: stack = [] for i in range(len(nums)): while stack and nums[i] < stack[-1] and len(stack) + len(nums) - i > k: stack.pop() if len(stack) < k: stack.append(nums[i]) return stack

Time Complexity: O(n) where n is the length of the input array nums.

Space Complexity: O(k) since the size of the stack will be at most k.

1