Welcome to Subscribe On Youtube

1673. Find the Most Competitive Subsequence

Description

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

Solutions

Given an array A, the task is to identify a subsequence of length k that is the smallest in lexicographic order.

The strategy involves using a “monotonic stack”.

The process of finding a subsequence of length k essentially boils down to removing len(A) - k elements from A. We maintain a counter r to track the number of deletions allowed, initially set to len(A) - k.

We then utilize a stack that maintains a strictly increasing order from the bottom to the top. If the stack isn’t empty and the element at the top of the stack is greater than the new element being considered, and if deletions are still allowed (r > 0), we pop the top of the stack and decrement r by 1.

This popping process continues until either the stack becomes empty, the element at the top of the stack is less than or equal to the new element, or no more deletions are allowed (r = 0). At this juncture, the new element is pushed onto the stack (unless the stack has reached the desired subsequence length, in which case we need to further decrement r by 1 for any additional element that cannot be added to the stack).

The resulting sequence formed by the elements in the stack from bottom to top represents the desired subsequence. To validate the efficacy of this algorithm, it suffices to recognize that opting for deletion (specifically, popping the top of the stack) whenever permissible invariably yields a more optimal solution than choosing not to delete.

This approach ensures that the final subsequence is the smallest possible in lexicographic order by strategically removing elements that would otherwise result in a lexicographically larger sequence.

  • class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        Deque<Integer> stk = new ArrayDeque<>();
        int n = nums.length;
        for (int i = 0; i < nums.length; ++i) {
            while (!stk.isEmpty() && stk.peek() > nums[i] && stk.size() + n - i > k) {
                stk.pop();
            }
            if (stk.size() < k) {
                stk.push(nums[i]);
            }
        }
        int[] ans = new int[stk.size()];
        for (int i = ans.length - 1; i >= 0; --i) {
            ans[i] = stk.pop();
        }
        return ans;
    }
}

  • 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.size() && stk.back() > nums[i] && stk.size() + n - i > k) {
                stk.pop_back();
            }
            if (stk.size() < k) {
                stk.push_back(nums[i]);
            }
        }
        return stk;
    }
};

  • class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        stk = []
        n = len(nums)
        for i, v in enumerate(nums):
            while stk and stk[-1] > v and len(stk) + n - i > k:
                stk.pop()
            if len(stk) < k: # eg. input [1,2,3,4,5], k=3
                stk.append(v)
        return stk

#############

class Solution: # no variable 'remaining'
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        result = [0] * k
        idx = 0

        for i in range(len(nums)):
            while idx > 0 and result[idx - 1] > nums[i] and (idx + (len(nums) - i) > k):
                idx -= 1

            if idx < len(result):
                result[idx] = nums[i]
                idx += 1

        return result

##############

from typing import List

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:

        result = [0] * k
        idx = 0
        remaining = len(nums) - k

        for i in range(len(nums)):
            while(idx > 0 and nums[i] < result[idx - 1] and remaining > 0):
                idx -= 1
                remaining -= 1

            if idx < len(result):
                result[idx] = nums[i]
                idx += 1
                # remaining -= 1 # no remaining--
            else:
                remaining -= 1

        return result


if __name__ == "__main__":
    print(Solution().mostCompetitive([3,5,2,6], 2))


  • func mostCompetitive(nums []int, k int) []int {
	stk := []int{}
	n := len(nums)
	for i, v := range nums {
		for len(stk) > 0 && stk[len(stk)-1] > v && len(stk)+n-i > k {
			stk = stk[:len(stk)-1]
		}
		if len(stk) < k {
			stk = append(stk, v)
		}
	}
	return stk
}

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

All Problems

All Solutions