#1673

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Find the Most Competitive Subsequence

Identify the lexicographically smallest subsequence of size k using stack-based greedy selection in array traversal.

Problem Statement

Given an integer array nums and a positive integer k, determine the subsequence of length k that is lexicographically smallest. A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements.

A subsequence a is more competitive than subsequence b if at the first differing index, a has a smaller number than b. For instance, [1,3,4] is more competitive than [1,3,5]. Return the most competitive subsequence of size k from nums.

Examples

Example 1

Input: nums = [3,5,2,6], k = 2

Output: [2,6]

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]

Example details omitted.

Constraints

1 <= nums.length <= 105
0 <= nums[i] <= 109
1 <= k <= nums.length

Solution Approach

Use a Monotonic Stack

Iterate through nums and maintain a stack that represents the current best subsequence. While the stack is not empty and the current number is smaller than the top of the stack, pop the stack if removing the top still allows enough remaining elements to reach length k.

Push Candidates

Push the current number onto the stack if the stack size is less than k. This ensures that only the most competitive elements are kept in order, balancing future options with the immediate value comparison.

Finalize Subsequence

After traversing the array, the stack contains the k elements of the most competitive subsequence. Convert the stack into a result array of size k and return it.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each element is pushed and popped at most once in the monotonic stack. Space complexity is O(k) since the stack only holds the subsequence of size k.

What Interviewers Usually Probe

Expect recognition that a stack can maintain current candidates for lexicographical order.
Probe whether the candidate removal logic respects remaining elements to reach size k.
Check understanding of why left-side elements have higher priority than later ones.

Common Pitfalls or Variants

Common pitfalls

Not accounting for enough remaining elements when popping from the stack, causing subsequence length < k.
Confusing subsequence with subarray, leading to incorrect indexing.
Attempting a brute-force enumeration of all subsequences, which is infeasible for large n.

Follow-up variants

Find the most competitive subsequence under additional constraints like minimum sum or maximum product.
Compute the lexicographically largest subsequence instead of smallest.
Apply the monotonic stack approach to a circular array where wrapping is allowed.

FAQ

What is the key strategy to solve Find the Most Competitive Subsequence efficiently?

The key strategy is using a monotonic stack to maintain candidate elements while ensuring the subsequence remains lexicographically minimal and of size k.

Can we solve this problem without a stack?

A stack simplifies the logic and ensures O(n) time. Without it, you would need complex tracking of indices and elements, potentially increasing time complexity.

How do we handle ties when elements are equal in the subsequence?

Equal elements are treated as competitive in order; the first encountered element is kept, and popping only occurs when a strictly smaller number is found.

What if k equals the array length?

If k equals nums.length, the entire array is already the only subsequence of length k and is returned directly.

Does the solution pattern relate to other LeetCode problems?

Yes, the stack-based state management pattern appears in other greedy subsequence and monotonic stack problems, useful for lexicographical order optimizations.

terminal

Solution

Solution 1: Stack

We traverse the array `nums` from left to right, maintaining a stack `stk`. During the traversal, if the current element `nums[i]` is less than the top element of the stack, and the number of elements in the stack plus $n-i$ is greater than $k$, then we pop the top element of the stack until the above condition is no longer satisfied. At this point, if the number of elements in the stack is less than $k$, then we push the current element into the stack.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        stk = []
        n = len(nums)
        for i, v in enumerate(nums):
            while stk and stk[-1] > v and len(stk) + n - i > k:
                stk.pop()
            if len(stk) < k:
                stk.append(v)
        return stk

Continue Practicing

#1526 minimum number of increments on subarrays to form a target array #1996 the number of weak characters in the game #1130 minimum cost tree from leaf values