Find the smallest window of input array that contains all the elements of query array

Question

Problem: Given an input array of integers of size n, and a query array of integers of size k, find the smallest window of input array that contains all the elements of query array and also in the same order.

I have tried below approach.

        int[] inputArray = new int[] { 2, 5, 2, 8, 0, 1, 4, 7 };
        int[] queryArray = new int[] { 2, 1, 7 };

Will find the position of all query array element in inputArray.

public static void SmallestWindow(int[] inputArray, int[] queryArray)
    {
        Dictionary<int, HashSet<int>> dict = new Dictionary<int, HashSet<int>>();

        int index = 0;
        foreach (int i in queryArray)
        {
            HashSet<int> hash = new HashSet<int>();
            foreach (int j in inputArray)
            {
                index++;
                if (i == j)
                    hash.Add(index); 
            }
            dict.Add(i, hash);
            index = 0;
        }
      // Need to perform action in above dictionary.??
    }

I got following dictionary

1. int 2--> position {1, 3}
2. int 1 --> position {6}
3. int 7 --> position {8}

Now I want to perform following step to findout minimum window

1. Compare int 2 position to int 1 position. As (6-3) < (6-1)..So I will store 3, 6 in a hashmap.

2. Will compare the position of int 1 and int 7 same like above.

I cannot understand how I will compare two consecutive value of a dictionary. Please help.

Answer 1

The algorithm:
For each element in the query array, store in a map M (V → (I,P)), V is the element, I is an index into the input array, P is the position in the query array. (The index into the input array for some P is the largest such that query[0..P] is a subsequence of input[I..curr])

Iterate through the array.
If the value is the first term in the query array: Store the current index as I.
Else: Store the value of the index of the previous element in the query array, e.g. M[currVal].I = M[query[M[currVal].P-1]].I.
If the value is the last term: Check if [I..curr] is a new best.

Complexity
The complexity of this is O(N), where N is the size of the input array.

N.B.
This code expects that no elements are repeated in the query array. To cater for this, we can use a map M (V → listOf((I,P))). This is O(NhC(Q)), where hC(Q) is the count of the mode for the query array..
Even better would be to use M (V → listOf((linkedList(I), P))). Where repeated elements occur consecutively in the query array, we use a linked list. Updating those values then becomes O(1). The complexity is then O(NhC(D(Q))), where D(Q) is Q with consecutive terms merged.

Implementation
Sample java implementation is available here. This does not work for repeated elements in the query array, nor do error checking, etc.