Shortest Supersequence

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
2 upvotes
Asked in companies
FacebookApple

Problem statement

Given two arrays ‘SMALL’ and ‘LARGE’, you need to find the length of the shortest sub-array of ‘LARGE’ array, that contains all elements of the ‘SMALL’ array. It is given that elements in the ‘SMALL’ sub array can be in any order.

Note 
All the elements in the ‘SMALL’ array are distinct.
For Example 
Let us say 'SMALL' = [ 3,6 ] and 'LARGE' = [ 8, 6, 9, 3, 1, 2, 6].

Subarray [ 1,3 ] (from index 1 to index 3) and [ 3,6 ] have all the elements that are present 

In ‘SMALL’ array. The length of the sub-array [ 1, 3 ] is shorter. Therefore required answer = 3
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test contains two integers ‘M’ and ‘N’ - the number of elements in the ‘LARGE’ and ‘SMALL’ array respectively.

The third line of each test case contains ‘M’ space-separated integers that make up ‘LARGE’.

The fourth line of each test case contains ‘N’ space-separated integers that makeup ‘SMALL’.
Output Format 
For each test case, print an integer denoting the length of the shortest sub-array of ‘LARGE’ having all elements of ‘SMALL’.

If no such subarray exists, return ‘-1’.
Note 
You are not required to print anything; it has already been taken care of. Just implement the function and return the matrix.
Constraints 
1 <= T <= 50
1 <= M,N <= 10^4
1 <= LARGE[ i ] , SMALL[ i ] <=10^8

Time Limit: 1 sec
Sample Input 1
2
6 3
5 10 15 5 2 13
15 10 2 
5 2
7 4 1 9 8
9 6
Sample Output 1
4
-1
Explanation For Sample Input 1
Test Case 1: The ‘LARGE’ array is [5, 10, 15, 5, 2, 13] and ‘LARGE’ = [15, 10, 2].

Subarray [10, 15,5, 2] has all elements of the ‘LARGE’ array. Therefore answer = 4.

Test Case 2: There is no sub-array having elements of the ‘LARGE’ array. Therefore answer = -1.
Sample Input 2
2
3 1
22 45 17
17 
6 2
4 6 8 9 5 4
8 4
Sample Output 2
1
3
Hint

Try to find all super sequences.

Approaches (3)
Naive Approach

We will iterate through the ‘LARGE’ array and find all the shortest super sequences starting from every index of the ‘LARGE’ array and print the shortest of all.

 

Now the main task is to find the supersequence starting from an element at any index ‘ i ‘ of ‘large’ array.

 

For finding the supersequence starting from the ‘i - th’ element of the ‘LARGE’ array, we will iterate from large[ i ] and find the first nearest(index) of all the elements in the ‘small’ array. The maximum value of all the indices will be the end of the supersequence. 

 

For example, if LARGE = [ 1,4 ,6,7] and SMALL = [ 4, 6]. For i = 0 , index of ‘4’ = 1, index of ‘6’ =2. As ‘2’ is maximum, so index = 2 will be the end of supersequence starting from ‘1’.

 

Algorithm:

 

  • Take a variable ‘RES’ to store the result (initialized to INT_MAX)
  • To find supersequence starting from every LARGE[ i ]. Run a loop of ‘ i ‘ from ‘0’ to ‘M-1’
  • Find ‘END’ of supersequence for every value of ‘ i’.
  • Run a loop ‘ j’ from 0 to N-1 to find the nearest of all elements in the ‘small’ array.
  • Run a loop ‘ k ‘ from ‘ i ‘ to M-1
  • If (LARGE[ k ] = SMALL [j]) , we found nearest of ‘SMALL’ [ j ]. Update END= max( END, k ) and break the loop.
  • If for any element SMALL[ j ] , there is no nearest in LARGE[ i…..M-1], this means there can not be any supersequence starting from LARGE[ i ] or from any element in right of LARGE[ i ]. So we will break all loops in this case and return res.
  • Update RES.as RES = min(RES, END- i +1) as END- i +1 will be length of supersequence.
  • Return RES.
Time Complexity

O(M^2 * N), where M and N are sizes of the ‘LARGE’ and ‘SMALL’ array.

 

For every element in ‘LARGE’ array, we have done M * N operations. Therefore Complexity is O(M^2 * N)

Space Complexity

O(1)

 

We have not used any data structure. Therefore space complexity is O(1).

Code Solution
(100% EXP penalty)
Shortest Supersequence
Full screen
Console