https://dunjudge.me/analysis/problems/918/
I faced this question in an technical phone interview at Google. This question has a lot of variants which I believe I had not practiced before on leetcode. I spend 45 minutes on the question got messed up on details. The interview has follow up questions as well which I was tested at.
I want to contribute this question as I feel there are no question like this for practice on leetcode and I have seen a lot fo similar types of questions on this:
https://stackoverflow.com/questions/5447561/find-shortest-subarray-containing-all-elements
A spanning subarray is a subarray containing all the elements in the original array. For example, let an
initial array, A = [1, 2, 3, 3, 2, 4, 1, 2, 2]. The subarray A0 = [3, 2, 4, 1, 2] is spanning because it contains all the
elements of A. However, the subarray B = [1, 2, 3] is not spanning because it missing the element 4 present
in A. Given an initial array A of length N , output the length of the shortest spanning subarray.
Input Format
The first line contains an integer N . The following line contains N space-separated integers representing the
elements of A.
Output Format
In a single line, output a single integer representing the length of the shortest spanning array.
Sample Input
10
1 2 3 3 2 3 4 1 2 2
Sample Output
4
Constraints
Subtask 1: [46 Marks] N ≤ 100
Subtask 2: [27 Marks] N ≤ 105
Subtask 4: [27 Marks] N ≤ 106
4-1
Comments (10)