Find the Most Competitive Subsequence

Moderate
0/80
Average time to solve is 30m
2 upvotes
Asked in company
Adobe

Problem statement

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).
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
4
2 1 4 3 
2
5
7 4 1 3 6
3

Sample Output 1:

1 3
1 3 6

Explanation of Sample Output 1:

Test Case 1 :  

Given arr = {2, 1, 4, 3} and C = 2. Among all the subsequences of size 2: {2, 1}, {2,  4}, {2, 3}, {1, 4}, {1, 3} and {4, 3}, the subsequence {1, 3} is the most competitive.


Test Case 2 : 

Given arr = {7, 4, 1, 3, 6} and C = 3. Among all the subsequences of size 3: {7, 4, 1}, {7, 4, 3}, {7, 4, 6}, {7, 1, 3}, {7, 1, 6}, {4, 1, 3}, {4, 1, 6}, {4, 3, 6} and {1, 3, 6}, the subsequence {1, 3, 6} is the most competitive.

Sample Input 2:

2
6
3 10 8 13 25 7
3
4
8 8 8 8
2

Sample Output 2:

3 8 7
8 8
Hint

In a subsequence, the lesser the integer at the left, the greater is the chances of it being the most competitive. Can you build the subsequence from left to right with the above idea?

Approaches (2)
Lexicgraphically Smallest Ordering

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’.
Time Complexity

O(C * N), where ‘N’ is the total number of integers in ‘ARR’, and ‘C’ is the size of the most competitive subsequence.

 

Since the outer loop runs ‘C’ times within which O(N) time will be required in the worst case to find the minimum element.

Space Complexity

O(1),

 

Since constant space has been used here, therefore, space complexity here is of constant order O(1).

Code Solution
(100% EXP penalty)
Find the Most Competitive Subsequence
Full screen
Console