Problem statement

https://binarysearch.com/problems/K-Lexicographically-Smallest-Subsequence/

Solution

Equal to Leetcode 1673. Find the Most Competitive Subsequence.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums, k):
        attempts = len(nums) - k
        stack = []
        for num in nums:
            while stack and num < stack[-1] and attempts > 0:
                stack.pop()
                attempts -= 1
            stack.append(num)
        
        return stack[:k]