Find the most competitive subsequence

Array Stack Greedy Monotonic Stack

52.7% acceptance

Feb 25, 2026

2181

106

Given an integer array nums and a positive integer k, return the most competitive subsequence of nums of size k. A subsequence a is more competitive than b if in the first position where they differ, a has a number less than b.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn most_competitive(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let k = k as usize;
    let n = nums.len();
    let mut stack: Vec<i32> = Vec::with_capacity(k);
    for (i, &num) in nums.iter().enumerate() {
      // Pop if: current num is smaller, we can still reach k elements after popping
      while !stack.is_empty()
        && *stack.last().unwrap() > num
        && stack.len() + (n - i) > k
      {
        stack.pop();
      }
      if stack.len() < k {
        stack.push(num);
      }
    }
    stack
  }
}