Find the Most Competitive Subsequence solution and explanation
Google
9 more videos on this problem
Lexicographically Smallest Subsequence | Find the Most Competitive Subsequence | Leetcode 1673Pepcoding · 34:18 · 10K views
Leetcode 1673. Find the Most Competitive SubsequenceFraz · 12:57 · 7K views
Find the Most Competitive Subsequence | Live Coding with Explanation | Leetcode #1673Algorithms Made Easy · 7:32 · 2K views
Find the Most Competitive Subsequence | Leetcode 1673 | Live coding sessionCoding Decoded · 7:52 · 1K views
Find the Most Competitive Subsequence | LeetCode 1673 | Stack | GoogleNaresh Gupta · 10:29 · 1K views
1673. (Medium) Find the Most Competitive Subsequence - Daily Leetcode (Day 72)yeetcode · 5:41 · 1K views
LeetCode 1673. Find the Most Competitive Subsequence - Interview Prep Ep 112Fisher Coder · 12:51 · 877 views
LeetCode 1673. Find the Most Competitive Subsequence | Visualization | PythonAH Tech · 6:48 · 764 views
LeetCode 1673. Find the Most Competitive SubsequenceHappy Coding · 12:33 · 719 views
1673. Find the Most Competitive Subsequence (Leetcode Medium)Programming Live with Larry · 31:43 · 513 views
The 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 <= 1050 <= nums[i] <= 1091 <= k <= nums.length
Approach overview
Problem Overview: Given an integer array nums and an integer k, return the most competitive subsequence of length k. A subsequence is considered more competitive if at the first position where two subsequences differ, the one with the smaller number is chosen.
Approach 1: Using a Stack for Maintaining Order (Greedy + Monotonic Stack) (Time: O(n), Space: O(k))
This approach builds the answer using a monotonic increasing stack. You iterate through the array and maintain a stack that stores the current best subsequence. While the current element is smaller than the top of the stack and you still have enough remaining elements to fill k, pop the stack. This ensures larger elements earlier in the subsequence get replaced with smaller ones, making the sequence lexicographically smaller. After handling removals, push the current number if the stack size is still less than k. Each element is pushed and popped at most once, giving O(n) time complexity and O(k) space. This pattern appears frequently in monotonic stack problems and is a standard technique when maintaining optimal order while scanning an array.
Approach 2: Greedy Strategy with Direct Modification (Time: O(n), Space: O(k))
This approach applies the same greedy principle but manages the result array directly instead of an explicit stack structure. Iterate through nums while tracking how many elements can still be removed. If the current element is smaller than the last element in the result and removals are still allowed, remove the previous element to improve competitiveness. Continue this process until the order condition is satisfied. Then append the current number if the result size is below k. Conceptually, this is still a stack-like process but implemented using direct array modification. The algorithm processes each element once, producing O(n) time complexity with O(k) extra space.
The key insight behind both solutions is greedy ordering: whenever a smaller value appears and removing a previous value still allows building a length k subsequence, removing the larger value improves the final sequence. The constraint on remaining elements ensures the subsequence length remains achievable.
Recommended for interviews: The monotonic stack approach is what most interviewers expect. It demonstrates understanding of greedy decisions, stack-based ordering, and array traversal patterns. Recognizing when to remove earlier elements to maintain a lexicographically smaller sequence is a common theme in greedy and stack problems. Explaining why each element is pushed and popped at most once clearly shows mastery of the O(n) optimal solution.
Approach 1: Using a Stack for Maintaining Order
This approach uses a stack to build the competitive subsequence. The basic idea is to iterate through the array and maintain a stack where the final size is k. For each element, we decide whether it should be added to the stack or replace the top element of the stack, which ensures the stack remains a competitive sequence.
We will replace the top element of the stack if the current element is smaller and there are enough elements left to fill the required subsequence size.
This method ensures that the maintained sequence is minimal and competitive, based on the problem constraints.
def most_competitive(nums, k):
stack = []
to_remove = len(nums) - k
for num in nums:
while stack and stack[-1] > num and to_remove > 0:
stack.pop()
to_remove -= 1
stack.append(num)
return stack[:k]
# Example usage
nums = [3, 5, 2, 6]
result = most_competitive(nums, 2)
print(result)import java.util.ArrayDeque;
public class Solution {
public int[] mostCompetitive(int[] nums, int k) {
int[] result = new int[k];
ArrayDeque<Integer> stack = new ArrayDeque<>();
int to_remove = nums.length - k;
for (int num : nums) {
while (!stack.isEmpty() && stack.peek() > num && to_remove > 0) {
stack.pop();
to_remove--;
}
stack.push(num);
}
while (stack.size() > k) {
stack.pop();
}
for (int i = k - 1; i >= 0; i--) {
result[i] = stack.pop();
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {3, 5, 2, 6};
int[] result = sol.mostCompetitive(nums, 2);
for (int num : result) {
System.out.print(num + " ");
}
}
}#include <vector>
#include <iostream>
using namespace std;
vector<int> mostCompetitive(vector<int>& nums, int k) {
vector<int> stack;
int to_remove = nums.size() - k; // number of optional removals
for (int num : nums) {
while (!stack.empty() && stack.back() > num && to_remove > 0) {
stack.pop_back();
to_remove--;
}
stack.push_back(num);
}
stack.resize(k);
return stack;
}
int main() {
vector<int> nums = {3, 5, 2, 6};
int k = 2;
vector<int> result = mostCompetitive(nums, k);
for (int num : result) cout << num << " ";
return 0;
}function mostCompetitive(nums, k) {
const stack = [];
let to_remove = nums.length - k;
for (const num of nums) {
while (stack.length > 0 && stack[stack.length - 1] > num && to_remove > 0) {
stack.pop();
to_remove--;
}
stack.push(num);
}
return stack.slice(0, k);
}
// Example usage
const nums = [3, 5, 2, 6];
const result = mostCompetitive(nums, 2);
console.log(result);#include <stdio.h>
void mostCompetitive(int* nums, int numsSize, int k) {
int stack[k], top = 0;
for (int i = 0; i < numsSize; i++) {
while (top > 0 && stack[top - 1] > nums[i] && top + (numsSize - i) > k) {
top--;
}
if (top < k) {
stack[top++] = nums[i];
}
}
for (int i = 0; i < k; i++) {
printf("%d ", stack[i]);
}
}
int main() {
int nums[] = {3, 5, 2, 6};
int k = 2;
mostCompetitive(nums, 4, k);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] MostCompetitive(int[] nums, int k) {
Stack<int> stack = new Stack<int>();
int to_remove = nums.Length - k;
foreach (var num in nums) {
while (stack.Count > 0 && stack.Peek() > num && to_remove > 0) {
stack.Pop();
to_remove--;
}
stack.Push(num);
}
int[] result = new int[k];
for (int i = k - 1; i >= 0; i--) {
result[i] = stack.Pop();
}
return result;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {3, 5, 2, 6};
int[] result = sol.MostCompetitive(nums, 2);
Console.WriteLine(string.Join(" ", result));
}
}This Python function uses a list to simulate a stack to find the most competitive subsequence. As with other solutions, it adds elements directly if they maintain a competitive order and can pop elements if a better candidate comes along and removals are still permissible.
Time Complexity: O(n).
Space Complexity: O(k).
Approach 2: Greedy Strategy with Direct Modification
This approach builds upon the idea that maintaining a competitive subsequence can be achieved by iteratively reducing and replacing elements in a greedy fashion, focusing directly on modifications to an output array.
This strategy is slightly different from a pure stack-based approach as it directly handles result index placement while keeping track of candidates for subsequences and managing the required number of subsequence slots.
def find_most_competitive(nums, k):
result = [0] * k
j = 0
for i, num in enumerate(nums):
while j > 0 and result[j-1] > num and j + len(nums) - i > k:
j -= 1
if j < k:
result[j] = num
j += 1
return result
# Example usage:
nums = [2, 4, 3, 3, 5, 4, 9, 6]
print(find_most_competitive(nums, 4))import java.util.Arrays;
public class Solution {
public int[] findMostCompetitive(int[] nums, int k) {
int[] result = new int[k];
int j = 0;
for (int i = 0; i < nums.length; i++) {
while (j > 0 && result[j - 1] > nums[i] && j + nums.length - i > k) {
j--;
}
if (j < k) {
result[j++] = nums[i];
}
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {2, 4, 3, 3, 5, 4, 9, 6};
int[] result = sol.findMostCompetitive(nums, 4);
System.out.println(Arrays.toString(result));
}
}#include <vector>
#include <iostream>
using namespace std;
vector<int> findMostCompetitive(vector<int>& nums, int k) {
vector<int> result(k);
int j = 0;
for (int i = 0; i < nums.size(); i++) {
while (j > 0 && result[j - 1] > nums[i] && j + nums.size() - i > k) {
j--;
}
if (j < k) {
result[j++] = nums[i];
}
}
return result;
}
int main() {
vector<int> nums = {2, 4, 3, 3, 5, 4, 9, 6};
int k = 4;
vector<int> result = findMostCompetitive(nums, k);
for (int num : result) cout << num << " ";
return 0;
}function findMostCompetitive(nums, k) {
const result = new Array(k);
let j = 0;
for (let i = 0; i < nums.length; i++) {
while (j > 0 && result[j - 1] > nums[i] && j + nums.length - i > k) {
j--;
}
if (j < k) {
result[j++] = nums[i];
}
}
return result;
}
// Example usage
const nums = [2, 4, 3, 3, 5, 4, 9, 6];
console.log(findMostCompetitive(nums, 4));#include <stdio.h>
void findMostCompetitive(int* nums, int numsSize, int k) {
int result[k];
int j = 0;
for (int i = 0; i < numsSize; i++) {
while (j > 0 && result[j - 1] > nums[i] && j + numsSize - i > k) {
j--;
}
if (j < k) {
result[j++] = nums[i];
}
}
for (int i = 0; i < k; i++) {
printf("%d ", result[i]);
}
}
int main() {
int nums[] = {2, 4, 3, 3, 5, 4, 9, 6};
int k = 4;
findMostCompetitive(nums, 8, k);
return 0;
}using System;
public class Solution {
public int[] FindMostCompetitive(int[] nums, int k) {
int[] result = new int[k];
int j = 0;
for (int i = 0; i < nums.Length; i++) {
while (j > 0 && result[j - 1] > nums[i] && j + nums.Length - i > k) {
j--;
}
if (j < k) {
result[j] = nums[i];
j++;
}
}
return result;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {2, 4, 3, 3, 5, 4, 9, 6};
var result = sol.FindMostCompetitive(nums, 4);
Console.WriteLine(string.Join(", ", result));
}
}The solution provides a Pythonic direct construction of the desired subsequence, focusing on allocated index slots in the result array directly.
Time Complexity: O(n).
Space Complexity: O(k).
Approach 3: Stack
We traverse the array nums from left to right, maintaining a stack stk. During the traversal, if the current element nums[i] is less than the top element of the stack, and the number of elements in the stack plus n-i is greater than k, then we pop the top element of the stack until the above condition is no longer satisfied. At this point, if the number of elements in the stack is less than k, then we push the current element into the stack.
After the traversal, the elements in the stack are the answer.
The time complexity is O(n), and the space complexity is O(k). Where n is the length of the array nums.
function mostCompetitive(nums: number[], k: number): number[] {
const stk: number[] = [];
const n = nums.length;
for (let i = 0; i < n; ++i) {
while (stk.length && stk.at(-1)! > nums[i] && stk.length + n - i > k) {
stk.pop();
}
if (stk.length < k) {
stk.push(nums[i]);
}
}
return stk;
}func mostCompetitive(nums []int, k int) []int {
stk := []int{}
n := len(nums)
for i, v := range nums {
for len(stk) > 0 && stk[len(stk)-1] > v && len(stk)+n-i > k {
stk = stk[:len(stk)-1]
}
if len(stk) < k {
stk = append(stk, v)
}
}
return stk
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using a Stack for Maintaining Order | Time Complexity: Space Complexity: |
| Greedy Strategy with Direct Modification | Time Complexity: Space Complexity: |
| Stack | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack for Maintaining Order (Monotonic Stack) | O(n) | O(k) | General optimal solution. Best when maintaining lexicographically smallest subsequence while scanning once. |
| Greedy Strategy with Direct Modification | O(n) | O(k) | When implementing greedy logic without explicitly using a stack structure. |
Frequently asked questions
Is Find the Most Competitive Subsequence easy or hard?
Find the Most Competitive Subsequence is classified as a Medium problem. The challenge comes from recognizing the greedy rule and implementing the monotonic stack correctly. Once the pattern is identified, the algorithm becomes a straightforward linear scan.
Find the Most Competitive Subsequence Python/Java solution
Python and Java solutions typically implement the monotonic stack pattern. Iterate through nums, pop from the stack while the top element is larger than the current value and enough elements remain, then push the current value if the stack size is below k. This produces an O(n) solution in both languages.
How to solve Find the Most Competitive Subsequence in O(n)?
Scan the array once while maintaining a monotonic increasing stack. For each number, remove larger elements from the stack if enough remaining elements exist to still reach length k. Then push the current number if the stack has fewer than k elements. This greedy process ensures the smallest possible subsequence while keeping the complexity O(n).
What is the best approach for Find the Most Competitive Subsequence?
The best approach uses a greedy monotonic stack. Iterate through the array while maintaining an increasing stack of elements in the subsequence. If the current number is smaller than the stack top and enough elements remain to still build length k, pop the larger value. This guarantees the lexicographically smallest subsequence in O(n) time and O(k) space.
Is Find the Most Competitive Subsequence asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Amazon, Google, and Meta because it tests greedy reasoning and monotonic stack patterns. Interviewers often expect candidates to identify that earlier larger elements should be removed when a smaller element appears and enough elements remain.
What data structure is used in Find the Most Competitive Subsequence?
A stack is the primary data structure used in the optimal solution. Specifically, a monotonic increasing stack helps maintain the smallest possible sequence while processing the array. The stack stores elements of the current subsequence and allows efficient removal of larger previous values.
What is the time complexity of Find the Most Competitive Subsequence?
The optimal solution runs in O(n) time where n is the length of the array. Each element is pushed to the stack once and popped at most once, so the total number of operations is linear. The space complexity is O(k) because the resulting subsequence contains exactly k elements.