Find the Most Competitive Subsequence

Medium
1408.

Find the Most Competitive Subsequence

Find the Most Competitive Subsequence is a medium coding problem on arrays, greedy and stack, asked in Amazon, Google and Uber interviews.

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^5
  • 0 <= nums[i] <= 10^9
  • 1 <= k <= nums.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var mostCompetitive = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • 0 <= nums[i] <= 10^9
  • 1 <= k <= nums.length

Hints for Find the Most Competitive Subsequence

  1. Hint 1

    This is the 'smallest subsequence of length k' problem: earlier positions dominate later ones.

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

  3. 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 than k items.

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

  1. Scan nums with index i, keeping a stack st of the chosen elements.
  2. While st is non-empty, its top is greater than nums[i], and st.length - 1 + (n - i) >= k, pop.
  3. If st.length < k, push nums[i].
  4. After the scan, st holds exactly k elements — 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 k elements.

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 st

Java

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