Sliding Window: Minimal Window of Array

Sliding Window

Sliding window is a common seen technique in solving algorithm, it has a few elements:

  • Window start and end
  • Status of elements in the window
  • Window extends to the right according to the status
  • Window shrinks to the right according to the status
  • Window stops moving at certain condition.

sliding-window-page-1

Before we discuss sliding window algorithm, we must understand:

  • Any problem can be solved by sliding window can be solved by enumerating all possible combinations
  • Sliding window skipped some of the combinations to speed up

So the key to sliding window application is to prove:

No need to check the skipped combinations.

Let’s take a look at two questions and their solution and then come back to the discussion of sliding window.

Minimum Size Subarray Sum problem

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

Observations

From the description we have the following observations:

  • The elments are positive: sum of window increase/decrease as we expand/shrink window
  • The condition is sum >= s: when sum >= s we should expand, then shrink
  • Target at minimum subarray size: then have to shrink then window as much as possible

Looks like sliding window algorithm can be applied to this problem, but we have to answer the following questions:

What combinations are skipped?

We may simply the example above: [2,3,1,2] and s = 7
The following are combinations that will be visited:

  • [2]
  • [2, 3]
  • [2, 3, 1]
  • [2, 3, 1, 2]
  • [3, 1, 2]

The combinations that are skipped are:

  • [3, 1]
  • [1]
  • [1, 2]
  • [2]

And the [3, 1] was skipped when we shrink the window at [2, 3, 1, 2].

Is it correct to skip these combinations?

Consider about the target: sum >= s.

  • If [3, 1] >= s, then when the window grows from [2, 3] to [2, 3, 1] it will stop there because sum([2, 3, 1]) > sum([3, 1]) > 2
  • If it stopped, [3, 1] will be visited
  • But since it didn’t stop, [3, 1] is < s, no need to visit.

To make this prove more generic:

  • Assume the window stopped at [i, j]
  • Then j is the first element from i to n that makes sum(i, j) >= s
  • In another way, any sub window [i, k] where k < i will make sum(i, k) < s, so these sub window can be skipped.

Algorithm

Based on the discussion above, we come to the following algorithm:

while right < n:
    sum += num[right ++]
    while (sum > s):
        minLen = Math.min(minLen, right - left)
        sum -= num[left++]

Notice how the important principle we discussed in the beginning are applied in this algorithm:

  • Window: Use left and right boundary to represent a window
  • Stop condition: right boundary stops at the end
  • Status update:update status of window every time the window moves
  • Move condition: expand the window when the status did not mets requirement
  • Move condition: Shrink the window while the status meets requirements

Implementation

The following is the implementation of the algorithm:

public int minSubArrayLen(int s, int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int windowSum = 0;
    int minLen = nums.length + 1;
    for (int left = 0, right = 0; right < nums.length; right ++) {
        windowSum += nums[right];
        while (windowSum >= s) {
            minLen = Math.min(minLen, right - left + 1);
            windowSum -= nums[left ++];
        }
    }
    return minLen == nums.length + 1 ? 0 : minLen;
}

Minimum Window Substring problem

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the empty string “”.

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Observations

We have the following observation about the problem:

  • Target at finding the minimal window that contains all characters in T
  • Sliding window characters can be applied to it: expand the window will increase the occurrence of certain character.

What combinations are skipped?

Let’s also simply the given examble to ADBEC, the following are combinations visited:

  • [A]
  • [A, D]
  • [A, D, B]
  • [A, D, B, E]
  • [A, D, B, E, C]
  • [D, B, E, C]

The combinations that are skipped are:

  • [D, B]
  • [D, B, E]
  • [B]
  • [B]
  • [B, E]
  • [B, E, C]

[D, B, E] are skipped when we shrink from [A, D, B, E, C] to [D, B, E, C].

Is it correct to skip these combinations?

The correctness can be proved similar to the process in the above question:

Let’s assume at window [i, j] it meets the targeting requirement, then the implication is that it does not meet the requirement at any sub window [i, k] where k < j. When any combination of these sub windows can be safely skipped.

Algorithm

The key is to find a way to:

  • Record the status of the window

Use a char map to record the occurrence of each character in the window.

  • Indication of the window meets requirement

This indication must be able to grow or decrease incrementally. A special count works

  • The count increase only when stats[ch] < target[ch], decrease when stats[ch] < target[ch]

where stats[ch] is the occurrence of ch in the window and target[ch] is the target occurrence of ch.

Implementation

The algorithm is very similar to the question above, the implementation is as below:

public String minWindow(String s, String t) {
    char[] tCh = new char[128];
    char[] sCh = new char[128];

    for (char ch : t.toCharArray()) {
        tCh[ch] ++;
    }

    String ret = "";
    int count = 0;
    int minWindowSize = Integer.MAX_VALUE;

    for (int left = 0, right = 0; right < s.length();) {
        char chRight = s.charAt(right ++);
        if (sCh[chRight]++ <= tCh[chRight]) {
            count ++;
        }

        while (count == t.length()) {
            if (right - left < minWindowSize) {
                minWindowSize = right - left;
                ret = s.substring(left, right);
            }

            char chLeft = s.charAt(left++);
            if (sCh[chLeft]-- < tCh[chLeft]) {
                count --;
            }
        }
    }

    return minWindowSize == Integer.MAX_VALUE ? "" : ret;
}

Sliding window application principle

Sliding window characteristics:

  • Sliding window has a start and end
  • Sliding window has status that indicate the status of the window
  • Sliding window grows/shrink toward one direction

Sliding window application principles:

  • Sliding window skipped some combinations to improve efficiency, to use sliding window needs to prove these combinations can be skipped.

In terms of implementation, here is the key ideas:

  • Use nested loop to move window: outer loop to expand the window, inner loop to shrink the window
  • The outer loop stop condition is the right boundary meets array end
  • The inner loop stop condition is the status of the window meets requirement, as long as it still meets requirement, shrink the window as possible.

Questions and follow ups:

  • If we change the question to Maximum Size subarray, does the sliding window algorithm still work?

Maximum size subarray does not need to apply sliding window: find out the sum of the entire array, if it meets requirements, it is the max window, otherwise no sub window works.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s