Find the Most Competitive Subsequence

Problem Description

Given an integer array nums and a positive integer k, return the most competitive subsequence of nums of size k. A subsequence is more competitive if it has a smaller number in the first position where it differs from another subsequence of the same length.

Key Insights

• The problem requires forming a subsequence of a given length k that is lexicographically smallest.
• We can use a greedy approach to ensure that the subsequence remains competitive by removing larger elements when smaller ones are encountered, while still allowing enough elements to complete the size k.
• A stack can be used to maintain the current subsequence, allowing us to efficiently compare and add elements.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(k)

Solution

To solve the problem, we utilize a greedy approach with a stack data structure. The idea is to iterate through the array nums, and for each element, we decide whether to include it in our subsequence based on the following:

1. If the current element is smaller than the last element in the stack (subsequence), we can pop the last element from the stack if it allows us to maintain enough elements left in the array to reach size k.
2. We push the current element onto the stack if the size of the stack is less than k.

By the end of the iteration, we will have a stack that potentially holds more than k elements, so we simply take the first k elements from the stack to form the final subsequence.

Code Solutions