Question

Formatted question description: https://leetcode.ca/all/1673.html

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

Algorithm

Given an array A, find the subsequence of length k with the smallest lexicographic order.

The idea is a ·monotonous stack·.

Finding the subsequence of length k is equivalent to deleting len−k numbers in A. We use a variable r to mark how many digits can be deleted, and assign it to len−k at the beginning.

Then open a stack that strictly rises monotonically from the bottom of the stack to the top of the stack. If the stack is not empty and the top of the stack is greater than the new number, and the number can be deleted (referring to the establishment of r> 0), the stack is popped and r is reduced by 1.

Until the stack is empty or the top of the stack is less than or equal to the new number or r = 0 (it cannot be deleted at this time), and then the new number is pushed into the stack (if the stack is full, it means that the new number cannot be pushed into the stack, then more to delete a number, subtract 1 from r).

Finally, the array from the bottom of the stack to the top of the stack is what you want. To prove the correctness of the algorithm, you only need to pay attention to every time you can delete (the deletion here mainly refers to the top of the pop stack), deletion is always better than no deletion.

Code

Array as stack

Java

public class Find_the_Most_Competitive_Subsequence {

    public class Solution {

        public int[] mostCompetitive(int[] nums, int k) {

            int[] result = new int[k];
            int idx = 0; // result's index

            for (int i = 0; i < nums.length; i++) {

                while (idx > 0 && result[idx - 1] > nums[i] && (idx + (nums.length - i) > k)) {
                    idx--;
                }

                if (idx < result.length ) {

                    result[idx++] = nums[i];
                }
            }

            return result;
        }
    }
}
from typing import List

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:

        result = [0] * k
        idx = 0
        remaining = len(nums) - k

        for i in range(len(nums)):
            while(idx > 0 and nums[i] < result[idx - 1] and remaining > 0):
                idx -= 1
                remaining -= 1

            if idx < len(result):
                result[idx] = nums[i]
                idx += 1
                # remaining -= 1 # no remaining--
            else:
                remaining -= 1

        return result


if __name__ == "__main__":
    print(Solution().mostCompetitive([3,5,2,6], 2))

Stack

Java

class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        int length = nums.length;
        int remove = length - k;
        if (remove == 0)
            return nums;
        Deque<Integer> stack = new LinkedList<Integer>();
        int index = 0;
        while (index < length && remove > 0) {
            int num = nums[index];
            while (!stack.isEmpty() && num < stack.peek() && remove > 0) {
                stack.pop();
                remove--;
            }
            stack.push(num);
            index++;
        }
        while (!stack.isEmpty() && remove > 0) {
            stack.pop();
            remove--;
        }
        int[] subsequence = new int[k];
        int size = stack.size();
        for (int i = size - 1; i >= 0; i--)
            subsequence[i] = stack.pop();
        for (int i = size; i < k; i++, index++)
            subsequence[i] = nums[index];
        return subsequence;
    }
}
class Solution_Stack:
    def mostCompetitive(self, A: List[int], k: int):
        stack = []
        for i, a in enumerate(A):
            while stack and stack[-1] > a and (len(stack) - 1) + (len(A) - i) >= k:
            # also working: while stack and stack[-1] > a and (len(stack)) + (len(A) - i) > k:
                stack.pop()
            if len(stack) < k:
                stack.append(a)
        return stack

All Problems

All Solutions