We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Most Competitive Subsequence

Number: 1792

Difficulty: Medium

Paid? No

Companies: Google, Uber

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 derived from the array by deleting some (or no) elements without changing the order. One subsequence is considered more competitive than another if at the first differing position, it has a smaller number.

Key Insights

  • Use a greedy algorithm with a monotonic stack to continuously build the smallest lexicographical sequence.
  • Ensure that after potential removals, there are still enough elements remaining to complete a subsequence of size k.
  • At each step, compare the current number with the last element in the stack and decide whether to pop from the stack.

Space and Time Complexity

Time Complexity: O(n), where n is the length of nums. Space Complexity: O(k), since the stack holds at most k elements.

Solution

The solution iterates over the array while maintaining a monotonic stack. For each element, if the current element is smaller than the last element in the stack and there are enough elements left to reach a total of k, the algorithm pops from the stack to remove suboptimal choices. This greedy process guarantees that the resulting subsequence is the most competitive (i.e., lexicographically smallest possible). Once the iteration is finished, the stack contains the desired subsequence.

Code Solutions

# Function to find the most competitive subsequence using a greedy monotonic stack.
def mostCompetitive(nums, k):
    stack = []  # Stack to hold the resulting subsequence
    n = len(nums)  # Total number of elements in the input array
    
    # Iterate over each number with its index.
    for i, num in enumerate(nums):
        # While the stack is not empty, and the last element in the stack is greater than the current element,
        # and we have enough remaining elements to fill the subsequence of size k:
        while stack and num < stack[-1] and (len(stack) - 1 + (n - i)) >= k:
            stack.pop()  # Remove the last element from the stack
        # If the current subsequence is not yet of length k, add the current element.
        if len(stack) < k:
            stack.append(num)
    return stack

# Example usage:
print(mostCompetitive([3, 5, 2, 6], 2))  # Expected Output: [2, 6]
← Back to All Questions