## DEV Community is a community of 871,688 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Ruairí O'Brien

Posted on

# Day 21 - Find the Most Competitive Subsequence

## The 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`

## Tests

``````import pytest
from .Day21_FindtheMostCompetitiveSubsequence import Solution

s = Solution()

@pytest.mark.parametrize(
"nums,k,expected",
[
([3, 5, 2, 6], 2, [2, 6]),
([2, 4, 3, 3, 5, 4, 9, 6], 4, [2, 3, 3, 4]),
],
)
def test_most_competitive(nums, k, expected):
assert s.mostCompetitive(nums, k) == expected
``````

## Solution

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

for i in range(n):
while len(stack) > max(0, rem + i) and nums[i] < stack[-1]:
stack.pop()
stack.append(nums[i])

return stack[:k]
``````

## Commentary

My solution performs terribly! I am too tired today to improve it.

I thought is was similar to yesterday's problem where all we really want is a stack to keep track of things. Here we add each number to the stack as we go. If there is a number on the stack and if the current number is less than the last number on the stack, pop the last number off the stack. That way, you always have the most competitive sequence on the stack. Then we take the last `k` numbers from the stack.

I am not sure why it performs so badly relatively to other submissions. I guess if I use a different data structure like a queue I might get better performance.