Find the Most Competitive Subsequence
MediumArraySorting
Description
Given an integer array nums and a positive integer k, return the most competitive subsequence of length k. Smaller is more competitive.
Examples
Input:
nums = [3,5,2,6], k = 2Output:
[2,6]Explanation:
[2,6] is smallest.
Input:
nums = [7,1,9,4,8,3], k = 3Output:
[1,4,3]Explanation:
Need the lexicographically smallest subsequence of length 3 (preserving original index order). Starting from index 1 with value 1, the next choices come from [9,4,8,3]. Picking 4 (index 3) lets us still take one more from [8,3], where 3 is smaller. The result is [1,4,3] taken from indices 1, 3, 5.
Input:
nums = [1,2,3,4], k = 1Output:
[1]Explanation:
This is an edge case where k=1 and the array is already sorted in ascending order. The most competitive subsequence of length 1 is simply the smallest element in the array, which is 1.
Constraints
- •
1 ≤ nums.length ≤ 10⁵