1673. Find the Most Competitive Subsequence #

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 <= 105
0 <= nums[i] <= 109
1 <= k <= nums.length

Problem Summary #

Given an integer array nums and a positive integer k, return the most competitive subsequence of nums with length k. A subsequence of an array is a sequence obtained by deleting some elements from the array (possibly deleting no elements).

At the first position where subsequence a and subsequence b differ, if the number in a is less than the corresponding number in b, then we say subsequence a is more competitive than subsequence b (when they have the same length). For example, [1,3,4] is more competitive than [1,3,5]; at the first differing position, which is the last position, 4 is less than 5.

Solution Approach #

This problem is a typical monotonic stack problem. Using a monotonic stack can ensure that the relative positions of elements in the original array remain unchanged, which satisfies the requirement in the problem of deleting elements without moving elements. A monotonic stack can also ensure that each time an element is pushed onto the stack, the element is the smallest possible.
Similar problems include Problem 42, Problem 84, Problem 496, Problem 503, Problem 856, Problem 901, Problem 907, Problem 1130, Problem 1425, and Problem 1673.

Code #

package leetcode

// Monotonic stack
func mostCompetitive(nums []int, k int) []int {
	stack := make([]int, 0, len(nums))
	for i := 0; i < len(nums); i++ {
		for len(stack)+len(nums)-i > k && len(stack) > 0 && nums[i] < stack[len(stack)-1] {
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, nums[i])
	}
	return stack[:k]
}