Finding the smallest window

Question

Given two arrays A[n] and B[m], how can I find the smallest window in A that contains all the elements of B.

I am trying to solve this problem in O(n) time but I am having problem doing it. Is there any well know algorithm or procedure for solving it.

Answer 1

If m > n, A cannot contain all the elements of B (and hence we have an O(1) solution).

Otherwise:

• Create a hash table mapping elements of B to the sequence {0..m-1} (this is O(n) since m <= n) .
• Create an array C[m] to count occurences of the members of B (initialise to 0) in the current window.

• Create a variable z to count the the number of 0 elements of C (initialise to m).

• Create variables s and e to denote the start and end of the current window

• while e < n:
  • If z is nonzero, increment e and update C and z. O(1)
  • else consider this window as a possible solution (i.e. if it's the min so far, store it), then increment s and update C and z. O(1)

The while loop can be shown to have no more than 2n iterations. So the whole thing is O(n), I think.