Find the Most Competitive Subsequence — Problem & Solution
Find the Most Competitive Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find the Most Competitive Subsequence is a medium coding problem on arrays, greedy and stack, asked in Amazon, Google and Uber interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy, Stack, Monotonic Stack
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A subsequence keeps some elements of an array in their original order. Among subsequences of the same length, a is more competitive than b if, at the first position where they differ, a has the smaller number — for example [1,3,4] beats [1,3,5].
Given nums and a length k, return the most competitive subsequence of nums of size k.
Example 1
Input: nums = [4,1,7,3,8], k = 2
Output: [1,3]
Example 2
Input: nums = [5,4,3,2,1], k = 3
Output: [3,2,1]
Explanation: The first pick must leave room for two more elements, so it can only come from [5,4,3].
Example 3
Input: nums = [2,2,1,2], k = 3
Output: [2,1,2]
Constraints
1 <= nums.length <= 10^50 <= nums[i] <= 10^91 <= k <= nums.length
Hints for Find the Most Competitive Subsequence
Hint 1
This is the 'smallest subsequence of length k' problem: earlier positions dominate later ones.
Hint 2
Build the answer on a stack. When a smaller number arrives, the larger numbers on top of the stack would be better replaced — as long as enough elements remain to still reach length
k.Hint 3
Pop while the top is larger than the current number and
stack size - 1 + remaining elements >= k; push the current number if the stack has fewer thankitems.
How to solve Find the Most Competitive Subsequence
Greedy with a monotonic stack: a kept element should be thrown out the moment a smaller element appears after it, provided the remaining elements can still fill the subsequence to length k.
Approach
- Scan
numswith indexi, keeping a stackstof the chosen elements. - While
stis non-empty, its top is greater thannums[i], andst.length - 1 + (n - i) >= k, pop. - If
st.length < k, pushnums[i]. - After the scan,
stholds exactlykelements — the answer.
Why it works
Whenever top > nums[i] and enough elements remain, replacing the top by nums[i] makes the sequence smaller at that position, and the earliest differing position decides the comparison, so the pop can never hurt. The feasibility check guarantees the stack can still be filled to k. A stack left non-decreasing wherever a pop was allowed is exactly the lexicographically smallest feasible choice.
Complexity
- Time —
O(n) - Space —
O(k)
Pitfalls
- Without the remaining-count check the stack can end shorter than
k(e.g. a strictly decreasing array). - Pop on strictly greater only — popping equal values gains nothing and can waste needed elements.
- Do not push once the stack already holds
kelements.
Reference solution
Python
from typing import List
def mostCompetitive(nums: List[int], k: int) -> List[int]:
n = len(nums)
st = []
for i, x in enumerate(nums):
while st and st[-1] > x and len(st) - 1 + (n - i) >= k:
st.pop()
if len(st) < k:
st.append(x)
return stJava
public static int[] mostCompetitive(int[] nums, int k) {
int n = nums.length;
int[] st = new int[k];
int top = 0;
for (int i = 0; i < n; i++) {
while (top > 0 && st[top - 1] > nums[i] && top - 1 + (n - i) >= k) top--;
if (top < k) st[top++] = nums[i];
}
return st;
}C++
vector<int> mostCompetitive(vector<int>& nums, int k) {
int n = nums.size();
vector<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && st.back() > nums[i] && (int)st.size() - 1 + (n - i) >= k) st.pop_back();
if ((int)st.size() < k) st.push_back(nums[i]);
}
return st;
}JavaScript
var mostCompetitive = function(nums, k) {
var n = nums.length, st = [];
for (var i = 0; i < n; i++) {
while (st.length > 0 && st[st.length - 1] > nums[i] && st.length - 1 + (n - i) >= k) st.pop();
if (st.length < k) st.push(nums[i]);
}
return st;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms