Problem

Given an integer array nums and a positive integer k, return _the mostcompetitive subsequence of _nums of sizek.

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.

Examples

Example 1

1
2
3

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

1
2

Input: nums = [2,4,3,3,5,4,9,6], k = 4
Output: [2,3,3,4]

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
  • 1 <= k <= nums.length

Solution

Method 1 – Monotonic Stack (Greedy)

Intuition

To find the most competitive subsequence of size k, we want the lexicographically smallest possible sequence. We can use a monotonic stack to greedily keep the smallest elements, popping from the stack when a smaller element is found and we still have enough elements left to reach size k.

Approach

  1. Initialize an empty stack.
  2. Iterate through the array:
    • While the stack is not empty, the current element is smaller than the top of the stack, and there are enough elements left to fill the subsequence, pop the stack.
    • Push the current element onto the stack.
  3. After processing, the first k elements of the stack form the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        vector<int> stk;
        int n = nums.size();
        for(int i=0;i<n;++i) {
            while(!stk.empty() && nums[i]<stk.back() && stk.size()+n-i-1>=k) stk.pop_back();
            if(stk.size()<k) stk.push_back(nums[i]);
        }
        return stk;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func mostCompetitive(nums []int, k int) []int {
    stk := []int{}
    n := len(nums)
    for i, x := range nums {
        for len(stk) > 0 && x < stk[len(stk)-1] && len(stk)+n-i-1 >= k {
            stk = stk[:len(stk)-1]
        }
        if len(stk) < k {
            stk = append(stk, x)
        }
    }
    return stk
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        int[] stk = new int[k];
        int top = 0, n = nums.length;
        for(int i=0;i<n;++i) {
            while(top>0 && nums[i]<stk[top-1] && top+n-i-1>=k) top--;
            if(top<k) stk[top++]=nums[i];
        }
        return stk;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun mostCompetitive(nums: IntArray, k: Int): IntArray {
        val stk = ArrayList<Int>()
        val n = nums.size
        for (i in nums.indices) {
            while (stk.isNotEmpty() && nums[i] < stk.last() && stk.size + n - i - 1 >= k) stk.removeAt(stk.size-1)
            if (stk.size < k) stk.add(nums[i])
        }
        return stk.toIntArray()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def mostCompetitive(self, nums: list[int], k: int) -> list[int]:
        stk = []
        n = len(nums)
        for i, x in enumerate(nums):
            while stk and x < stk[-1] and len(stk) + n - i - 1 >= k:
                stk.pop()
            if len(stk) < k:
                stk.append(x)
        return stk
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn most_competitive(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let n = nums.len();
        let mut stk = Vec::new();
        for (i, &x) in nums.iter().enumerate() {
            while let Some(&last) = stk.last() {
                if x < last && stk.len() + n - i - 1 >= k as usize {
                    stk.pop();
                } else {
                    break;
                }
            }
            if stk.len() < k as usize {
                stk.push(x);
            }
        }
        stk
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    mostCompetitive(nums: number[], k: number): number[] {
        const stk: number[] = [];
        const n = nums.length;
        for(let i=0;i<n;++i) {
            while(stk.length && nums[i]<stk[stk.length-1] && stk.length+n-i-1>=k) stk.pop();
            if(stk.length<k) stk.push(nums[i]);
        }
        return stk;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums, as each element is pushed and popped at most once.
  • 🧺 Space complexity: O(k), for the stack of size at most k.