CODEWITHSUNDEEP
c++calgorithm
mousey
mousey

Reputation: 11901

Finding the smallest window

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.

Upvotes: 5

Views: 841

Answers (2)

Nikita Rybak
Nikita Rybak

Reputation: 68006

countLet's call window 'minimal' if it can't be reduced. I.e., after increasing its left border or decreasing its right border it's no longer valid window (doesn't contain all elements from B). There three in your example: [0, 2], [2, 6], [6, 7]

Let's assume say that you already found leftmost minimal window [left, right]. ([0, 2] in your example) Now we'll just slide it to the right.

// count[x] tells how many times number 'x'
// happens between 'left' and 'right' in 'A'
while (right < N - 1) {
    // move right border by 1
    ++right;
    if (A[right] is in B) {
        ++count[A[right]];
    }

    // check if we can move left border now
    while (count[A[left]] > 1) {
        --count[A[left]];
        ++left;
    }

    // check if current window is optimal
    if (right - left + 1 < currentMin) {
        currentMin = right - left + 1;
    }
}

This sliding works because different 'minimal' windows can't contain one another.

Upvotes: 3

Artelius
Artelius

Reputation: 49089

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.

Upvotes: 4

Related Questions