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]

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.