# Find the Most Competitive Subsequence
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-most-competitive-subsequence)
Canonical: https://scaleengineer.com/dsa/problems/find-the-most-competitive-subsequence
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Stack, Monotonic Stack
---
## Problem
Given an integer array `nums` and a positive integer `k`, return _the most **competitive** subsequence of_ `nums` _of size_ `k`.

An array's subsequence is a resulting sequence obtained by erasing some (possibly zero) elements from the array.

We define that a subsequence `a` is more **competitive** than a subsequence `b` (of the same length) if in the first position where `a` and `b` differ, subsequence `a` has a number **less** than the corresponding number in `b`. For example, `[1,3,4]` is more competitive than `[1,3,5]` because the first position they differ is at the final number, and `4` is less than `5`.

**Example 1:**

**Input:** nums = [3,5,2,6], k = 2
**Output:** [2,6]
**Explanation:** 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]

**Constraints:**

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

# Approaches
## Brute-Force with Backtracking
This approach involves generating every possible subsequence of length `k` from the input array `nums`. After generating all such subsequences, we compare them lexicographically to find the 'most competitive' one, which is the lexicographically smallest subsequence.
**Time:** O(C(n, k) * k) - The number of subsequences of length `k` is given by the binomial coefficient `C(n, k)`. For each valid subsequence found, we perform a comparison that takes `O(k)` time. This is extremely slow and will time out for the given constraints. · **Space:** O(k) - The recursion depth is at most `k`, and we store the `current` subsequence and the `mostCompetitive` subsequence, both of which have a size of `k`.
**Pros:** Conceptually straightforward, as it directly follows the definition of the problem by checking all possibilities.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error on any reasonably sized input, making it impractical for the given constraints.
### Explanation
We can use a recursive backtracking function to explore all combinations. The function, say `findSubsequences(startIndex, currentSubsequence)`, would work as follows:

*   The `startIndex` indicates the starting position in `nums` for the current recursive call to prevent duplicate combinations.
*   `currentSubsequence` is the list of numbers we have picked so far.
*   **Base Case:** If `currentSubsequence.size()` equals `k`, we have found a valid subsequence. We then compare it with the best subsequence found so far and update the best one if the current one is more competitive.
*   **Recursive Step:** We iterate from `startIndex` to `nums.length - 1`. For each element `nums[i]`, we add it to `currentSubsequence` and make a recursive call `findSubsequences(i + 1, currentSubsequence)`. After the call returns, we backtrack by removing `nums[i]` from `currentSubsequence` to explore other possibilities.

To avoid storing all `C(n, k)` subsequences, which would consume a massive amount of memory, we can maintain a single 'best' subsequence found so far and update it whenever we find a more competitive one in the base case of our recursion.

```java
class Solution {
    int[] mostCompetitive;
    int k;
    int[] nums;

    public int[] mostCompetitive(int[] nums, int k) {
        this.mostCompetitive = null;
        this.k = k;
        this.nums = nums;
        backtrack(0, new java.util.ArrayList<>());
        return mostCompetitive;
    }

    private void backtrack(int start, java.util.List<Integer> current) {
        // Pruning: if remaining elements are not enough to form a k-length subsequence
        if (current.size() + (nums.length - start) < k) {
            return;
        }

        if (current.size() == k) {
            int[] currentArr = current.stream().mapToInt(i -> i).toArray();
            if (mostCompetitive == null || isMoreCompetitive(currentArr, mostCompetitive)) {
                mostCompetitive = currentArr;
            }
            return;
        }

        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);
            backtrack(i + 1, current);
            current.remove(current.size() - 1); // backtrack
        }
    }

    private boolean isMoreCompetitive(int[] a, int[] b) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] < b[i]) {
                return true;
            }
            if (a[i] > b[i]) {
                return false;
            }
        }
        return false; // they are equal
    }
}
```
### Algorithm
*   Initialize a list `mostCompetitive` of size `k` with a placeholder value (e.g., `Integer.MAX_VALUE`).
*   Define a recursive function `backtrack(start, current)`.
*   Inside `backtrack(start, current)`:
    *   If `current.size() == k`:
        *   Compare `current` with `mostCompetitive`.
        *   If `current` is lexicographically smaller, update `mostCompetitive` with the elements of `current`.
        *   Return.
    *   Add a pruning step: if the number of elements picked (`current.size()`) plus the number of remaining elements in `nums` (`nums.length - start`) is less than `k`, we can't form a valid subsequence, so we return early.
    *   Iterate `i` from `start` to `nums.length - 1`:
        *   Add `nums[i]` to `current`.
        *   Call `backtrack(i + 1, current)`.
        *   Remove the last element from `current` (this is the backtracking step).
*   Start the process by calling `backtrack(0, new ArrayList<>())`.
*   Return `mostCompetitive`.

## Greedy Approach with a Monotonic Stack
A much more efficient approach is to build the result subsequence greedily. The core idea is that to get the lexicographically smallest subsequence, we want the smallest possible numbers to appear as early as possible. We can use a structure that behaves like a stack (often called a monotonic stack in this context) to build this subsequence in a single pass.
**Time:** O(n) - We iterate through the `nums` array once. Each element is pushed onto the stack at most once and popped at most once. Therefore, the total number of operations is proportional to `n`. · **Space:** O(k) - We use an auxiliary data structure (an array acting as a stack) to store the result. The size of this structure is exactly `k`.
**Pros:** Highly efficient with linear time complexity.; Optimal solution for the given constraints.; Solves the problem in a single pass over the input array.; Space-efficient, especially when using a fixed-size array instead of a dynamic one.
**Cons:** The logic, especially the condition for popping elements, is less intuitive than the brute-force approach and requires careful reasoning to get right.
### Explanation
We iterate through the input array `nums` one element at a time and maintain a stack which will eventually hold our result.

For each number `num` from `nums`, we consider adding it to our stack. Before adding it, we look at the number at the top of the stack. If the stack is not empty, the top element is greater than the current `num`, and we still have enough elements remaining in the `nums` array to form a valid subsequence of length `k` if we pop the top element, we should pop it. Popping a larger element in favor of a smaller, later one makes the resulting subsequence more competitive.

The condition to check if we can afford to pop is crucial: `(stack.size() - 1) + (nums.length - i) >= k`. This means the number of elements already in the stack (minus the one we're about to pop) plus the number of elements remaining in the input array (including the current one) is enough to reach the desired length `k`. This condition simplifies to `stack.size() + n - i > k`.

After the popping loop, if the stack's size is still less than `k`, we push the current `num` onto the stack. We don't add more than `k` elements.

This process ensures that for any position in our result, we pick the smallest possible number that allows for a valid subsequence of length `k` to be formed from the remaining elements. This is why it's called a monotonic stack approach; we try to keep the elements in the stack in increasing order as much as possible.

```java
class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        // Use an array as a stack for O(k) space complexity.
        int[] stack = new int[k];
        int len = 0; // Pointer for the top of the stack
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            // Condition to pop:
            // 1. Stack is not empty (len > 0).
            // 2. The top of the stack is greater than the current element.
            // 3. We have enough elements left to form a k-length subsequence.
            //    (len - 1) is the new stack size after pop.
            //    (n - i) is the number of remaining elements in nums (including current).
            //    So, (len - 1) + (n - i) >= k.
            while (len > 0 && stack[len - 1] > nums[i] && (len - 1 + n - i >= k)) {
                len--; // Pop the element
            }
            
            // If the stack has space, push the current element.
            if (len < k) {
                stack[len] = nums[i];
                len++; // Push the element
            }
        }
        
        return stack;
    }
}
```
### Algorithm
*   Initialize an empty stack (a `Deque` or a fixed-size array of size `k` can be used).
*   Let `n` be the length of `nums`.
*   Iterate through `nums` from `i = 0` to `n - 1`.
*   For each element `nums[i]`:
    *   While the stack is not empty, the top element of the stack is greater than `nums[i]`, and we can still form a valid subsequence of length `k` if we pop an element, do so. The condition for this is `stack.size() + n - i > k`.
    *   If the stack's size is less than `k`, push `nums[i]` onto the stack.
*   After the loop, the stack will contain the `k` elements of the most competitive subsequence.
*   Convert the stack to an integer array and return it.

# Solutions
### Java

```java
class Solution { public int [] mostCompetitive ( int [] nums , int k ) { Deque < Integer > stk = new ArrayDeque <>(); int n = nums . length ; for ( int i = 0 ; i < nums . length ; ++ i ) { while (! stk . isEmpty () && stk . peek () > nums [ i ] && stk . size () + n - i > k ) { stk . pop (); } if ( stk . size () < k ) { stk . push ( nums [ i ]); } } int [] ans = new int [ stk . size ()]; for ( int i = ans . length - 1 ; i >= 0 ; -- i ) { ans [ i ] = stk . pop (); } return ans ; } }
```

### CPP

```cpp
class Solution { public: vector < int > mostCompetitive ( vector < int >& nums , int k ) { vector < int > stk ; int n = nums . size (); for ( int i = 0 ; i < n ; ++ i ) { while ( stk . size () && stk . back () > nums [ i ] && stk . size () + n - i > k ) { stk . pop_back (); } if ( stk . size () < k ) { stk . push_back ( nums [ i ]); } } return stk ; } };
```

### Python

```python
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 : # eg. input [1,2,3,4,5], k=3 stk . append ( v ) return stk ############# class Solution : # no variable 'remaining' def mostCompetitive ( self , nums : List [ int ], k : int ) -> List [ int ]: result = [ 0 ] * k idx = 0 for i in range ( len ( nums )): while idx > 0 and result [ idx - 1 ] > nums [ i ] and ( idx + ( len ( nums ) - i ) > k ): idx -= 1 if idx < len ( result ): result [ idx ] = nums [ i ] idx += 1 return result ############## from typing import List class Solution : def mostCompetitive ( self , nums : List [ int ], k : int ) -> List [ int ]: result = [ 0 ] * k idx = 0 remaining = len ( nums ) - k for i in range ( len ( nums )): while ( idx > 0 and nums [ i ] < result [ idx - 1 ] and remaining > 0 ): idx -= 1 remaining -= 1 if idx < len ( result ): result [ idx ] = nums [ i ] idx += 1 # remaining -= 1 # no remaining-- else : remaining -= 1 return result if __name__ == "__main__" : print ( Solution (). mostCompetitive ([ 3 , 5 , 2 , 6 ], 2 ))
```