1673

1673. Find the Most Competitive Subsequence (Medium)

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 <= 105
• 0 <= nums[i] <= 109
• 1 <= k <= nums.length

Companies:
Dunzo

Related Topics:
Array, Stack, Greedy, Monotonic Stack

Similar Questions:

• Remove K Digits (Medium)
• Smallest Subsequence of Distinct Characters (Medium)

Solution 1. Mono-stack + Greedy

This problem is very similar to 402. Remove K Digits (Medium).

Since we are looking for the lexicographically smallest subsequence, we use mono-increasing stack.

For each A[i], we pop back of ans if:

• There is delete allowance, i.e. i - ans.size() < N - k: i - ans.size() is the number of elements that we've already popped, and N - k is the number of elements that we need to remove. So if i - ans < N - k, we can continue popping.
• ans.back() is strictly greater than A[i], i.e. ans.size() && ans.back() > A[i].

We only push A[i] into ans when ans.size() < k i.e. there are not yet k elements selected.

// OJ: https://leetcode.com/problems/find-the-most-competitive-subsequence/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<int> mostCompetitive(vector<int>& A, int k) {
        vector<int> ans;
        for (int i = 0, N = A.size(); i < N; ++i) {
            while (i - ans.size() < N - k && ans.size() && A[i] < ans.back()) ans.pop_back();
            if (ans.size() < k) ans.push_back(A[i]);
        }
        return ans;
    }
};