Last Updated: 7 Apr, 2021
Find the Most Competitive Subsequence
Moderate
Asked in company
You are given an array of integers, ‘ARR’, and a positive integer, ‘C’. Your task is to return the most competitive subsequence of ‘ARR’ of size ‘C’.
Given ‘a1’ and ‘a2’ as subsequences (of the same size) of ‘ARR’. Subsequence ‘a1’ is said to be more competitive than subsequence ‘a2’ if, at the first non-matching position in ‘a1’ and ‘a2’, subsequence ‘a1’ has an integer less than the corresponding integer in ‘a2’.
Note:
1) A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
2) Given arr = {1, 3, 4, 5, 6} and C = 3, subsequence {1, 3, 4} is more competitive than {1, 3, 5} because at the first non-matching position, i.e., at index 2, 4 (in first subsequence) < 5 (in second subsequence).
Input Format:
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains an integer ‘N’ representing the total number of integers in ‘ARR’.
The second line of each test case contains 'N' space-separated integers representing the array elements.
The last line of each test case contains an integer ‘C’ representing the size of the most competitive subsequence.
Output Format:
For each test case, return the most competitive subsequence.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= C <= N <= 10^3
0 <= ARR[ i ] <= 10 ^ 9
Time limit: 1 second
Approaches
Since we have to find the most competitive subsequence of size ‘C’, it can be interpreted as filling ‘C’ slots in the lexicographically smallest order to achieve our solution.
For filling the first slot (slot at index ‘0’), we should pick the smallest number in the range: index ‘0’ to index ‘N - C’ since we have to preserve at least ‘C - 1’ integers to be picked in the future for the rest of ‘C - 1’ slots.
For filling the second slot (slot at index ‘1’), the range would become: ‘index of previous picked integer + 1’ to index ‘N - C + 1’.
Similarly, for filling the ‘i’th slot, the range would be: ‘INDEX' of previous picked integer + 1’ to ‘N - C + i’.
So, we will build our solution by picking the smallest number in the corresponding range.
Algorithm:
- Declare a vector of integers, ‘RESULT’ to store the most competitive subsequence of ‘ARR’.
- Declare two integer variables, ‘START_INDEX’ and ‘END_INDEX’. Initialize ‘START_INDEX’ by ‘0’ and ‘END_INDEX’ by ‘N - C + 1’.
- Run a loop while C is greater than 0.
- Declare an integer variable, ‘MIN_ELEMENT_INDEX’. Find the index of the minimum element in ‘ARR’ in the range [START_INDEX, END_INDEX) and store it in ‘MIN_ELEMENT_INDEX’.
- Declare an integer variable, ‘MIN_ELEMENT’ and assign ‘ARR[MIN_ELEMENT_INDEX]’ to it.
- Push the ‘MIN_ELEMENT’ in ‘RESULT’.
- Decrement the ’C’ by 1.
- Increment the ‘END_INDEX’ by 1.
- In the end, return ‘RESULT’.
We can use a monotonically increasing stack to build a lexicographically smallest subsequence.
For this purpose, we will check whether the current element is smaller than the last inserted element in the stack. If yes, we can replace it with the current element to get a lexicographically smaller subsequence.
Before replacing, we have to make sure that there are enough elements in the remaining of the input, ‘ARR’ to form a ‘C’ size sequence. At any iteration ‘i’, after removing the last inserted element from the stack, there are ‘STACK.SIZE() - 1’ integers in the stack. Also, there will be ‘N - i’ integers that can still be pushed.
So, if ‘STACK.SIZE() - 1 + N - i >= C’, we can pop the stack.
Otherwise, if the stack contains less than ‘C’ elements, we can insert into the stack.
Finally, the stack will contain the most competitive sequence.
Algorithm:
- Create a vector of int, ‘STACK’ to store the most competitive subsequence of ‘ARR’.
- Run a loop for i = 0 to N - 1.
- Run a loop while ‘STACK’ is not empty and ‘STACK.SIZE() - 1 + N - i >= C’ and the current element is smaller than the last inserted element in the ‘STACK’.
- Pop the last inserted element from the ‘STACK’.
- If the size of ‘STACK’ is less than ‘C’.
- Push ‘ARR[ i ]’ in the ‘STACK’.
- Run a loop while ‘STACK’ is not empty and ‘STACK.SIZE() - 1 + N - i >= C’ and the current element is smaller than the last inserted element in the ‘STACK’.
- In the end, return ‘STACK’.