< Back





1673. Find the Most Competitive Subsequence

Your regular monotonically increasing stack problem, except with a constraint on the size of the
stack. I almost got this one right on the first try, however, there needs to be a constraint on when
we start to pop items from the stack that's related to stack size and the remaining elements in the
list.

The total number of elements in the list is n. We maintain the size of the stack with m. We're
inspecting element nums[i] with index i at any given time. While maintaining the monotonically
increasing nature of the stack is pretty straightfoward, we can't just pop items off from the stack
without checking to see if there are enough remaining elements in the list.

Our final answer's size has to equal k. So we check to see if, at the current index, there are
enough elements to fill the stack to size k. If there are, we can pop items off the stack. We also
check to see if the size of the stack is less than size k - if so, we append the item.

The solution is as follows:


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

          for i in range(n):
              while stack and stack[-1] > nums[i] and n - i - 1 >= k - m:
                  stack.pop()
                  m -= 1

              if m < k:
                  stack.append(nums[i])
                  m += 1

          return stack


_ Time Complexity:

  O(n) - We iterate through the list once.

_ Space Complexity:

  O(n) - We maintain a monotonically increasing stack.