LeetCode 1673 - Find the Most Competitive Subsequence

Difficulty: 🟡 Medium
Topics: Array, Stack, Greedy, Monotonic Stack

Solution

Here is a complete, detailed technical solution guide for LeetCode 1673 - Find the Most Competitive Subsequence following your formatting rules.

Problem Understanding

The problem asks us to find the most competitive subsequence of a given integer array nums of size k. A subsequence is formed by deleting zero or more elements from the array without changing the relative order of the remaining elements. A subsequence a is considered more competitive than subsequence b of the same length if the first differing element in a is smaller than in b.

For example, given nums = [3,5,2,6] and k = 2, the subsequences of length 2 are [3,5], [3,2], [3,6], [5,2], [5,6], [2,6]. Among these, [2,6] is the smallest in lexicographical order at the first differing index, so it is the most competitive.

The input constraints are important for understanding the scale: nums can have up to 100,000 elements, each element can be as large as 10^9, and k can range from 1 to the length of nums. This rules out any brute-force solution that generates all subsequences explicitly because the number of subsequences of length k is combinatorial and will be infeasible for large inputs.

Edge cases to consider include arrays that are already sorted in ascending or descending order, arrays with repeated elements, and k equal to 1 or equal to the length of nums. These cases could trip up naive implementations if they do not correctly handle remaining elements or stack-based removals.

Approaches

The brute-force approach would involve generating all possible subsequences of length k from nums and comparing them to find the most competitive one. This guarantees correctness because it examines every possible candidate. However, generating all subsequences of length k requires combinatorial operations (C(n,k)), which is impractical for n = 10^5.

The optimal approach relies on a greedy strategy using a monotonic stack. The key observation is that for a subsequence to be competitive, we want smaller elements as early as possible while ensuring that we can still form a subsequence of length k with the remaining elements. We can iterate through nums and maintain a stack that represents the current most competitive subsequence so far. At each step, if the current number is smaller than the top of the stack, and there are enough remaining elements to complete a length k subsequence, we pop the stack to make room for the smaller number. This guarantees we always maintain a lexicographically minimal subsequence.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(C(n,k) * k)	O(k)	Generates all subsequences of length k and selects the minimal. Too slow for n=10^5
Optimal	O(n)	O(k)	Uses a monotonic stack to maintain the most competitive subsequence greedily

Algorithm Walkthrough

Initialize an empty stack to represent the subsequence under construction.
Iterate through each element num in nums.
While the stack is not empty, the top element is greater than num, and the remaining elements plus the stack length are sufficient to form a subsequence of length k, pop the top of the stack. This ensures smaller numbers replace larger numbers if possible.
If the stack has fewer than k elements, push num onto the stack. Otherwise, skip num because including it would exceed the desired length.
After processing all elements, the stack contains the most competitive subsequence of length k.

Why it works: The stack invariant ensures that at each index, we maintain the smallest possible numbers in the earliest positions while still guaranteeing enough remaining elements to complete a subsequence of length k. This produces the lexicographically minimal sequence because we greedily remove larger elements in favor of smaller ones when allowed.

Python Solution

from typing import List

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        stack = []
        n = len(nums)
        
        for i, num in enumerate(nums):
            # Pop elements from stack if current num is smaller and enough elements remain
            while stack and stack[-1] > num and len(stack) - 1 + (n - i) >= k:
                stack.pop()
            if len(stack) < k:
                stack.append(num)
        return stack

Explanation: We maintain a stack as our subsequence. The while loop ensures we remove larger elements at the top if we can safely replace them with smaller num while still being able to reach length k. The final check prevents the stack from exceeding size k. This directly follows the algorithm walkthrough.

Go Solution

func mostCompetitive(nums []int, k int) []int {
    stack := make([]int, 0, k)
    n := len(nums)

    for i, num := range nums {
        for len(stack) > 0 && stack[len(stack)-1] > num && len(stack)-1+(n-i) >= k {
            stack = stack[:len(stack)-1]
        }
        if len(stack) < k {
            stack = append(stack, num)
        }
    }
    return stack
}

Go-specific notes: We preallocate the stack slice with capacity k to avoid repeated allocations. Slice resizing via append automatically handles adding elements. The logic is identical to the Python version, and bounds checks are handled safely by slice operations.

Worked Examples

Example 1: nums = [3,5,2,6], k = 2

Step	Stack	Current num	Action
i=0	[]	3	Append 3
i=1	[3]	5	Append 5
i=2	[3,5]	2	Pop 5 (2 < 5 and enough remaining), Pop 3 (2 < 3 and enough remaining), Append 2
i=3	[2]	6	Append 6

Final stack: [2,6]

Example 2: nums = [2,4,3,3,5,4,9,6], k = 4

Step	Stack	Current num	Action
i=0	[]	2	Append 2
i=1	[2]	4	Append 4
i=2	[2,4]	3	Pop 4 (3 < 4 and enough remaining), Append 3
i=3	[2,3]	3	Append 3
i=4	[2,3,3]	5	Append 5
i=5	[2,3,3,5]	4	Pop 5 (4 < 5 and enough remaining), Append 4
i=6	[2,3,3,4]	9	Skip (stack already k elements)
i=7	[2,3,3,4]	6	Skip

Final stack: [2,3,3,4]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is pushed and popped at most once from the stack.
Space	O(k)	The stack maintains at most k elements at any time.

The time complexity is linear because each number is considered once and popped at most once. Space complexity is proportional to k because that is the maximum size of the stack.

Test Cases

# Provided examples
assert Solution().mostCompetitive([3,5,2,6], 2) == [2,6]  # basic case
assert Solution().mostCompetitive([2,4,3,3,5,4,9,6], 4) == [2,3,3,4]  # repeated elements

# Edge cases
assert Solution().mostCompetitive([1,2,3,4,5], 3) == [1,2,3]  # already increasing
assert Solution().mostCompetitive([5,4,3,2,1], 2) == [2,1]  # strictly decreasing
assert Solution().mostCompetitive([1], 1) == [1]  # single element
assert Solution().mostCompetitive([1,1,1,1], 2) == [1,1]  # all identical
assert Solution().mostCompetitive([10,9,8,7,6,5,4,3,2,1], 5) == [6,5,4,3,2]  # large k in descending

Test	Why
[3,5,2,6], k=2	Basic functionality and subsequence choice
[2,4,3,3,5,4,9,6], k=4	Handling repeated elements and multiple pops
Increasing array	Stack never pops; basic order preserved
Decreasing array