Find the Most Competitive Subsequence

LeetCode 1673: Find the Most Competitive Subsequence Solution & Explanation

Problem Overview

TL;DR: Use a Monotonic Increasing Stack to greedily maintain the smallest possible elements for the subsequence while ensuring enough elements remain in the input to fulfill the length requirement k.

The problem asks us to find a subsequence of length k from an integer array nums that is the "most competitive." In this context, "competitive" implies lexicographically smallest. We need to select k numbers such that their relative order is preserved, but the resulting sequence has the smallest possible numbers appearing as early as possible. This is a classic optimization problem found in interviews, often referred to as LeetCode 1673: Find the Most Competitive Subsequence.

Brute Force Approach for Find the Most Competitive Subsequence

A naive approach would involve generating every possible subsequence of length k and comparing them to find the lexicographically smallest one.

The algorithm would look like this:

1. Use recursion or backtracking to explore the decision tree: for every element, either include it in the subsequence or skip it.
2. Only consider branches that result in a subsequence of exactly length k.
3. Compare all valid subsequences and return the minimum.

1# Pseudo-code for Brute Force
2def solve(index, current_subsequence):
3    if len(current_subsequence) == k:
4        update_global_min(current_subsequence)
5        return
6    if index == len(nums):
7        return
8    
9    # Include nums[index]
10    solve(index + 1, current_subsequence + [nums[index]])
11    
12    # Exclude nums[index]
13    solve(index + 1, current_subsequence)

Complexity Analysis: The number of subsequences of length k from an array of size N is given by the binomial coefficient $\binom{N}{k}$. In the worst case (e.g., $k = N/2$), this grows exponentially. With $N$ up to $10^5$, this approach will immediately hit a Time Limit Exceeded (TLE) error.

Algorithm Strategy: Stack Patterns

1. Initialization: Create an empty stack (or a list/vector acting as a stack) to store the result subsequence.
2. Iteration: Traverse the input array nums from left to right with index i.
3. Monotonic Maintenance: Inside the loop, check the Monotonic Stack conditions. While the stack is not empty AND the current element nums[i] is smaller than the stack's top element:
   • Check the Feasibility Constraint: calculate if stack.size() - 1 + (remaining elements in nums) is greater than or equal to k.
   • If feasible, pop the top element. This action signifies that the popped element is not part of the most competitive subsequence because a smaller, valid candidate (nums[i]) appeared later.
   • If not feasible, stop popping (we are forced to keep the larger number to satisfy length k).
4. Selection: Push nums[i] onto the stack if the stack size is less than k.
5. Result: After the loop finishes, the stack contains the most competitive subsequence.

Execution Flow

Let's trace nums = [3, 5, 2, 6], k = 2. Length n = 4.

1. i = 0, val = 3:
   • Stack is empty.
   • Push 3. Stack: [3].
2. i = 1, val = 5:
   • Top is 3. 5 > 3, so no popping (we want smallest, but 5 is larger).
   • Stack size (1) < k (2). Push 5. Stack: [3, 5].
3. i = 2, val = 2:
   • Top is 5. 2 < 5.
   • Feasibility: stack.size() - 1 (remains 1) + remaining input (1 element: 6) = 2. Since 2 >= k, we can pop.
   • Pop 5. Stack: [3].
   • Top is 3. 2 < 3.
   • Feasibility: stack.size() - 1 (remains 0) + remaining input (1 element: 6) = 1. Since 1 < k, we cannot pop 3. We need 3 to reach size 2.
   • Push 2. Stack: [3, 2].
4. i = 3, val = 6:
   • Top is 2. 6 > 2. No pop.
   • Stack size (2) == k. Do not push 6.
5. End: Return [3, 2]. Wait, looking at the example logic provided in the prompt, [2, 6] is the answer. Let's re-verify the feasibility check.

Correction on Step 3 Feasibility: Current index i=2 (value 2). Remaining elements after this index is n - 1 - i = 4 - 1 - 2 = 1 (value 6).

• Stack: [3, 5]. Top 5. 2 < 5.
  • If we pop 5, stack becomes [3]. New size 1.
  • Can we fill to k=2? We have stack size 1 + remaining 1 = 2. Yes.
  • Pop 5. Stack [3].
• Stack: [3]. Top 3. 2 < 3.
  • If we pop 3, stack becomes []. New size 0.
  • Can we fill to k=2? We have stack size 0 + remaining 1 (the 6) + current element 2.
  • Correct Logic: The condition is stack.size() + (n - i) > k.
  • Current i=2. n=4. k=2. n-i = 2.
  • Check pop 5: Stack size 2. 2 + 2 > 2. True. Pop 5.
  • Check pop 3: Stack size 1. 1 + 2 > 2. True. Pop 3.
  • Stack is empty. Push 2. Stack [2].
• i = 3, val = 6:
  • Push 6. Stack [2, 6].
• Result [2, 6]. Matches Example 1.

Proof of Correctness

The algorithm produces the correct result due to the properties of the Monotonic Stack and the greedy choice property.

1. Lexicographical Smallest: By enforcing the monotonic increasing property, we ensure that for any two adjacent elements in our subsequence, the earlier one is smaller than the later one wherever possible.
2. Feasibility: The condition stack.size() + (nums.length - i) > k guarantees that we never discard an element if doing so would make it impossible to construct a subsequence of length k. This ensures the final output is always a valid subsequence of the required length.
3. Optimal Substructure: The decision to keep or discard an element is made locally based on the current top of the stack and the remaining counts, which leads to the globally optimal solution for this specific constraint.

Pattern Reuse Notes

The Monotonic Stack pattern used here is highly transferable. Understanding how to maintain order while satisfying constraints helps in:

• LeetCode 402: Remove K Digits - Effectively the same problem: removing k digits to form the smallest number is equivalent to keeping n-k digits for the most competitive subsequence.
• LeetCode 496: Next Greater Element I - Uses the same monotonic logic to find the nearest larger value.
• LeetCode 503: Next Greater Element II - Circular version of the monotonic stack strategy.
• LeetCode 739: Daily Temperatures - Finds the distance to the next greater element using a monotonic stack.

Reference Implementation

C++ Solution for LeetCode 1673

1#include <vector>
2
3class Solution {
4public:
5    std::vector<int> mostCompetitive(std::vector<int>& nums, int k) {
6        std::vector<int> stack;
7        int n = nums.size();
8        
9        for (int i = 0; i < n; ++i) {
10            // While stack is not empty, current val is smaller than top,
11            // and we have enough remaining elements to fill the stack to size k
12            while (!stack.empty() && nums[i] < stack.back() && 
13                   stack.size() + (n - i) > k) {
14                stack.pop_back();
15            }
16            
17            // Only push if we haven't filled the required length k
18            if (stack.size() < k) {
19                stack.push_back(nums[i]);
20            }
21        }
22        
23        return stack;
24    }
25};

Java Solution for LeetCode 1673

1import java.util.Stack;
2
3class Solution {
4    public int[] mostCompetitive(int[] nums, int k) {
5        // Using an array as a stack for performance optimization
6        int[] stack = new int[k];
7        int top = -1; // Points to the index of the top element
8        int n = nums.length;
9        
10        for (int i = 0; i < n; i++) {
11            // Monotonic stack logic:
12            // Pop if current element is smaller than stack top
13            // AND we have enough remaining elements (n - i) to fill the rest
14            // Current stack size is (top + 1).
15            // Condition: (top + 1) + (n - i) > k
16            while (top >= 0 && nums[i] < stack[top] && (top + 1) + (n - i) > k) {
17                top--;
18            }
19            
20            // Push current element if there is space
21            if (top < k - 1) {
22                top++;
23                stack[top] = nums[i];
24            }
25        }
26        
27        return stack;
28    }
29}

Python Solution for LeetCode 1673

1class Solution:
2    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
3        stack = []
4        n = len(nums)
5        
6        for i, val in enumerate(nums):
7            # While stack has elements, current val is smaller than top,
8            # and we have enough remaining elements to satisfy length k.
9            # Feasibility: len(stack) + (remaining items) > k
10            # Remaining items including current 'val' is (n - i)
11            while stack and val < stack[-1] and len(stack) + (n - i) > k:
12                stack.pop()
13            
14            if len(stack) < k:
15                stack.append(val)
16                
17        return stack