Find the Most Competitive Subsequence

Med

#1535Time: 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`.

Patterns

Greedy

Data structures

Array Stack Monotonic Stack

Prompt

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 <= 10⁵
0 <= nums[i] <= 10⁹
1 <= k <= nums.length

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    int[] mostCompetitive;3    int k;4    int[] nums;5 6    public int[] mostCompetitive(int[] nums, int k) {7        this.mostCompetitive = null;8        this.k = k;9        this.nums = nums;10        backtrack(0, new java.util.ArrayList<>());11        return mostCompetitive;12    }13 14    private void backtrack(int start, java.util.List<Integer> current) {15        // Pruning: if remaining elements are not enough to form a k-length subsequence16        if (current.size() + (nums.length - start) < k) {17            return;18        }19 20        if (current.size() == k) {21            int[] currentArr = current.stream().mapToInt(i -> i).toArray();22            if (mostCompetitive == null || isMoreCompetitive(currentArr, mostCompetitive)) {23                mostCompetitive = currentArr;24            }25            return;26        }27 28        for (int i = start; i < nums.length; i++) {29            current.add(nums[i]);30            backtrack(i + 1, current);31            current.remove(current.size() - 1); // backtrack32        }33    }34 35    private boolean isMoreCompetitive(int[] a, int[] b) {36        for (int i = 0; i < a.length; i++) {37            if (a[i] < b[i]) {38                return true;39            }40            if (a[i] > b[i]) {41                return false;42            }43        }44        return false; // they are equal45    }46}

Complexity

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`.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public int[] mostCompetitive(int[] nums, int k) {3        // Use an array as a stack for O(k) space complexity.4        int[] stack = new int[k];5        int len = 0; // Pointer for the top of the stack6        int n = nums.length;7 8        for (int i = 0; i < n; i++) {9            // Condition to pop:10            // 1. Stack is not empty (len > 0).11            // 2. The top of the stack is greater than the current element.12            // 3. We have enough elements left to form a k-length subsequence.13            //    (len - 1) is the new stack size after pop.14            //    (n - i) is the number of remaining elements in nums (including current).15            //    So, (len - 1) + (n - i) >= k.16            while (len > 0 && stack[len - 1] > nums[i] && (len - 1 + n - i >= k)) {17                len--; // Pop the element18            }19            20            // If the stack has space, push the current element.21            if (len < k) {22                stack[len] = nums[i];23                len++; // Push the element24            }25        }26        27        return stack;28    }29}

Complexity

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`.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class 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 ; } };

1class 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 ))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem