1673. Find the Most Competitive Subsequence

Problem Description

In this problem, we are given an array nums of integers and another integer k. Our task is to find the most competitive subsequence of the array nums that has a size of k. A subsequence here means a sequence that can be derived by deleting any number of elements (including zero) from the array without changing the order of the remaining elements.

A subsequence is considered more competitive if at the first point of difference between two subsequences, the number in the more competitive one is smaller. For example, the subsequence [1,3,4] is more competitive than [1,3,5] because, at their first differing position, 4 is smaller than 5.

To put it another way, we are looking for the smallest lexicographically subsequence of length k from the given array, where "smallest" refers to the subsequence that would come first if you listed all possible subsequences of the given length in numerical order.

Intuition

The intuition behind approaching this problem lies in maintaining a stack that can help us keep track of potential candidates for the most competitive subsequence. Here's the thought process:

We move through the array and for each element, we decide if it should be included in the stack (which represents the current most competitive subsequence we have built up).
We apply two checks while considering to push an element onto the stack: a. If the current element is smaller than the top of the stack (last element in our current subsequence), it could lead to a more competitive subsequence. So we might want to remove the larger elements from the top of the stack. b. However, we can only remove elements from the stack if we are sure that we can still complete our subsequence of size k. In other words, there must be enough elements left in the array to fill the stack after popping. This is guaranteed when len(stk) + n - i > k where stk is the stack, n is the number of elements in nums, and i is the current index.
After considering the above two points, if our stack size is less than k, we push the current element onto the stack as a potential candidate for the most competitive sequence. We keep doing this until we have scanned through all elements in the array.
After the loop finishes, the stack contains the most competitive subsequence of size k.

The stack effectively stores the smallest numbers seen so far and pops the larger ones that could be replaced by the following smaller numbers to maintain the competitiveness of the sequence. By the time the scanning of the array is complete, we have the most competitive subsequence.

Learn more about Stack, Greedy and Monotonic Stack patterns.

Solution Approach

The solution uses a stack as a data structure to implement a greedy approach. Here's a step-by-step breakdown of the algorithm:

Initialize an empty list called stk which will be treated like a stack. This will be used to store the elements of the most competitive subsequence.
Determine the length of the input array nums and store it in a variable n.
Loop through each element v and its index i in the array using enumerate(nums).
Inside the loop, there is a while loop with a compound condition that is used to decide whether the top element should be popped from the stack:
- The stack should not be empty (there's an element to potentially pop).
- The current element v is less than the last element in the stack (stk[-1]). This check is important because a smaller element makes a subsequence more competitive.
- There are still enough elements left in nums (after ith index) to fill the stack to a length of k (the condition len(stk) + n - i > k ensures this).
If the above conditions are met, the top element of the stack is popped because keeping it would make our subsequence less competitive. We continue popping until the conditions fail, meaning we either exhaust the stack or the current element v is not smaller than the last in stk or there aren't enough elements remaining to reach length k.
After the while loop, a check ensures that we only add elements to stk if its length is less than k. Otherwise, our subsequence would exceed the desired length.
We append the current element v to the stack if the length of the stack is less than k.
After iterating over all elements in nums, the list stk will contain exactly k elements, which forms the most competitive sequence possible, and thus is returned.

During each iteration, the algorithm greedily tries to make the subsequence as small as possible by comparing the current number with the ones already in stk. This use of a stack allows the algorithm to keep the subsequence always in a competitive state by ensuring that each new added number would not make it any worse compared to other potential subsequences.

The main algorithmic patterns used here are:

Greedy algorithm: Making local optimal choices at each step with the hope of finding a global optimum, i.e., the most competitive subsequence.
Stack: Providing a way to keep track of elements and efficiently facilitate the necessary add and remove operations as per competitive conditions.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have the following array nums and integer k:

nums = [3, 5, 2, 6]
k = 2

We want to find the most competitive subsequence of size k from nums.

Following the solution approach:

Initialize an empty stack stk.
Determine the length of nums, which is n = 4.
Begin iterating through nums:
- At index i = 0, v = 3, there is nothing to pop because stk is empty. We add 3 to stk.
- At index i = 1, v = 5, there is nothing to pop because 5 is not less than the last element in stk, which is 3. Since len(stk) < k, we add 5 to stk.
- At index i = 2, v = 2, v is less than the last element in stk (which is 5) and len(stk) + (n - i) > k (2 elements in stk + 2 elements left in nums > 2). So we pop 5 from stk and add 2.
- At index i = 3, v = 6, there is nothing to pop since 6 is greater than the last element in stk (which is 2). However, len(stk) is already k, so we don’t add 6 to stk.
After the loop finishes, stk = [2, 3] which forms the most competitive subsequence because it is lexicographically the smallest subsequence of length k that we can form from nums.

The resulting most competitive subsequence is [2, 3]. The stack has helped us maintain the potential candidates for the subsequence efficiently, ensuring at each step that any larger numbers that could be replaced by smaller ones and do not contribute to the competitiveness are removed.

Solution Implementation

1class Solution:
2    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
3        # Initialize an empty list to use as a stack
4        stack = []
5        # Get the total number of elements in nums
6        num_len = len(nums)
7      
8        # Iterate over the indices and values of nums
9        for i, value in enumerate(nums):
10            # While stack is not empty and the last element in stack is greater than the current value
11            # and there are enough remaining elements to replace and still build a sequence of length k
12            while stack and stack[-1] > value and len(stack) + num_len - i > k:
13                # Pop the last element from the stack
14                stack.pop()
15            # If the stack contains fewer than k elements, append the current value
16            if len(stack) < k:
17                stack.append(value)
18      
19        # Return the stack which now contains the most competitive subsequence of length k
20        return stack
21

1class Solution {
2
3    public int[] mostCompetitive(int[] nums, int k) {
4        // Use a deque as a stack to maintain the most competitive sequence.
5        Deque<Integer> stack = new ArrayDeque<>();
6        int n = nums.length;
7
8        // Iterate over the array elements.
9        for (int i = 0; i < nums.length; ++i) {
10            // While the stack is not empty, and the current element is smaller than the top element of the stack,
11            // and there are enough elements remaining to form a sequence of length k
12            // we pop the stack since the current element gives a more competitive sequence.
13            while (!stack.isEmpty() && stack.peek() > nums[i] && stack.size() + n - i > k) {
14                stack.pop();
15            }
16          
17            // If the stack size is less than k, we can push the current element onto the stack.
18            if (stack.size() < k) {
19                stack.push(nums[i]);
20            }
21        }
22      
23        // Create an array to store the most competitive sequence.
24        int[] answer = new int[stack.size()];
25        // Pop elements from the stack to fill the answer array in reverse order
26        // since the elements in deque are in reverse order of the required sequence.
27        for (int i = answer.length - 1; i >= 0; --i) {
28            answer[i] = stack.pop();
29        }
30        // Return the array containing the most competitive sequence
31        return answer;
32    }
33}
34

1#include <vector>
2
3class Solution {
4public:
5    // Function to find the most competitive subsequence of `nums` with size `k`
6    std::vector<int> mostCompetitive(std::vector<int>& nums, int k) {
7        std::vector<int> stack; // Stack to store the most competitive subsequence
8        int numsSize = nums.size(); // Store the size of the input vector
9      
10        // Iterate over all the elements in the input vector
11        for (int i = 0; i < numsSize; ++i) {
12            // While the stack is not empty, the last element in the stack is greater than
13            // the current number, and the potential size of the competitive subsequence
14            // is still greater than `k`, pop the last element from the stack
15            while (!stack.empty() && stack.back() > nums[i] && stack.size() + numsSize - i > k) {
16                stack.pop_back();
17            }
18            // If the size of the stack is less than `k`, we can add the current number
19            // to the subsequence
20            if (stack.size() < k) {
21                stack.push_back(nums[i]);
22            }
23        }
24        // Return the most competitive subsequence
25        return stack;
26    }
27};
28

1function mostCompetitive(nums: Array<number>, k: number): Array<number> {
2    let stack: Array<number> = []; // Stack to store the most competitive subsequence
3    let numsSize = nums.length; // Store the length of the input array
4
5    // Iterate over all the elements in the input array
6    for (let i = 0; i < numsSize; ++i) {
7        // While the stack is not empty and the last element in the stack is greater than
8        // the current element, and there are enough remaining elements to reach a
9        // competitive subsequence of size `k`, pop the last element from the stack
10        while (
11            stack.length > 0 &&
12            stack[stack.length - 1] > nums[i] &&
13            stack.length + numsSize - i > k
14        ) {
15            stack.pop();
16        }
17
18        // If the current size of the stack is less than `k`, we can add the current element
19        // to the subsequence
20        if (stack.length < k) {
21            stack.push(nums[i]);
22        }
23    }
24
25    // Return the most competitive subsequence
26    return stack;
27}
28
29// Example usage:
30// let result = mostCompetitive([3, 5, 2, 6], 2);
31// result would be [2, 6]
32

Time and Space Complexity

Time Complexity

The time complexity of the code is O(n), where n is the length of the input list nums. Even though there is a nested loop caused by the while loop within the for loop, each element is pushed to and popped from the stack at most once. This guarantees that each operation is bounded by 2n (each element pushed and popped at most once), which simplifies to O(n).

Space Complexity

The space complexity is O(k) since we are using a stack to keep track of the most competitive subsequence, which, according to the problem, can have a maximum length of k. No other data structures are used that grow with the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don’t know