1673. Find the Most Competitive Subsequence

Problem

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

Solution

We must first understand what the competitive subsequence in the problem is. When a is more competitive than b, this means that the letters of a are smaller than the letters of b at the same position. According to this idea, we can build an increasing monotonic stack to find a minimum incremental subsequence. In addition, it should be noted that when the sum of the number of stacks plus the number of unprocessed letters plus the current processed letter is greater than k, we can pop the letters in the stack. Otherwise, we may not get k numbers of letters at the end.

Monotonic Stack

• Times: 
• Spaces: 

class Solution {
    public static int[] mostCompetitive(int[] nums, int k) {
        int[] results = new int[k];
        int pointer = -1;

        for (int i = 0; i < nums.length; i++) {
            int n = nums[i];
            while (pointer >= 0 && results[pointer] > n && pointer + (nums.length - i) >= k) {
                pointer--;
            }

            if (pointer < k - 1) {
                results[++pointer] = n;
            }
        }

        return results;
    }
}

Reference

• 1673. Find the Most Competitive Subsequence, LeetCode.
• 1673. Find the Most Competitive Subsequence, LeetCode Solutions.