Find the Most Competitive Subsequence
MedPrompt
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 <= 1050 <= nums[i] <= 1091 <= 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
mostCompetitiveof sizekwith a placeholder value (e.g.,Integer.MAX_VALUE). - Define a recursive function
backtrack(start, current). - Inside
backtrack(start, current):- If
current.size() == k:- Compare
currentwithmostCompetitive. - If
currentis lexicographically smaller, updatemostCompetitivewith the elements ofcurrent. - Return.
- Compare
- Add a pruning step: if the number of elements picked (
current.size()) plus the number of remaining elements innums(nums.length - start) is less thank, we can't form a valid subsequence, so we return early. - Iterate
ifromstarttonums.length - 1:- Add
nums[i]tocurrent. - Call
backtrack(i + 1, current). - Remove the last element from
current(this is the backtracking step).
- Add
- If
- 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
startIndexindicates the starting position innumsfor the current recursive call to prevent duplicate combinations. currentSubsequenceis the list of numbers we have picked so far.- Base Case: If
currentSubsequence.size()equalsk, 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
startIndextonums.length - 1. For each elementnums[i], we add it tocurrentSubsequenceand make a recursive callfindSubsequences(i + 1, currentSubsequence). After the call returns, we backtrack by removingnums[i]fromcurrentSubsequenceto 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.
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 }}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.
Solutions
Solution
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 ; } }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.