667. Find the Most Competitive Subsequence

HardStack Monotonic Stack Greedy

Given an array nums and an integer k, return the most competitive subsequence of length k — the lexicographically smallest subsequence of that length (comparing element by element). The input is JSON {nums, k}.

Input: JSON {nums, k}.

Output: Array — the most competitive subsequence.

Examples

Example 1

Input: {"nums":[3,5,2,6],"k":2}
Output: [2,6]
Explanation: Smallest length-2 subsequence.

Example 2

Input: {"nums":[2,4,3,3,5,4,9,6],"k":4}
Output: [2,3,3,4]
Explanation: Greedy smallest picks.

Example 3

Input: {"nums":[5],"k":1}
Output: [5]
Explanation: Only choice.

Constraints

1<=k<=n<=10^5

Asked by

Google

Solve this problem in the editor →