 New update is available. Click here to update.

# Shortest Supersequence

Last Updated: 8 Mar, 2021
Difficulty: Moderate

## 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
``````
##### 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
``````