Problem Statement in English

You’re given an integer array nums and an integer k.

You need to return the most competitive subsequence of nums of size k.

A competitive subsequence is one that has the smallest lexicographical order.

Approach

You need to use a monotonic stack to solve this problem.

The metric we use popping from the stack is:

  • If the stack is full and the current number is greater than the last number in the stack, we skip it.
  • If the stack is not full and the current number is less than the last number in the stack, AND we have enough numbers in nums to still reach k elements in the stack, OR, there are already $k$ elements in the stack, we pop from the stack.

This is because we must have $k$ elements in the stack at the end.

Solution in Python


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

        for i, num in enumerate(nums):
            if len(stack) == k and num >= stack[-1]:
                continue

            while stack and stack[-1] > num and ((len(stack) < k and l-(i+1) >= k-len(stack)) or (len(stack) == k)):
                stack.pop()

            stack.append(num)

        return stack

Complexity

  • Time: $O(n)$
    Since we are iterating through the array once and popping from the stack at most $n$ times.

  • Space: $O(n)$
    Since we are using a stack to store the elements.

And we are done.