## The Problem

Given an integer array

`nums`

and a positive integer`k`

, return the mostcompetitivesubsequence 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 morecompetitivethan a subsequence`b`

(of the same length) if in the first position where`a`

and`b`

differ, subsequence`a`

has a numberlessthan 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]
```

## Analysis

## 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.

## Top comments (0)