What is the sliding window algorithm? #

Let’s first demonstrate what is the sliding window approach and why we use it by solving this problem: Minimum Size Subarray Sum - LeetCode

Problem description #

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4] Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1] Output: 0

Constraints:

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104

A naive solution #

A brute force solution could be trying every possible subarray and calculating the sum of the numbers in the subarray. If the sum is larger than target, we update the minLength if the length of the subarray is less than the current minimum.

int minLength = Integer.MAX_VALUE;
        
for (int i = 0; i < nums.length; ++i) {
    int sum = 0;
    for (int j = i; j < nums.length; ++j) {
        sum += nums[j];

        if (sum > target) {
            minLength = Math.min(minLength, j - i + 1);
        }
        break;
    }
}

The problem is that there are a lot of duplicated calculations due to many subarrays sharing a common overlap.

If we can somehow memorize the summation for the overlap, we no longer need to calculate the sum of the overlapping area twice.

Sliding window approach #

The idea is to use a sliding window to keep track of the subarray we are visiting:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int res = Integer.MAX_VALUE, sum = 0, windowStart = 0;
        for (int windowEnd = 0; windowEnd < nums.length; ++windowEnd) {
            sum += nums[windowEnd];

            while (sum >= target) {
                res = Math.min(res, windowEnd - windowStart + 1);
                sum -= nums[windowStart++];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

• Each iteration, we enlarge the window size by incrementing windowEnd by 1, and add the number into sum
• If sum > target, which means we have a valid subarray (window), we update res if possible
• If sum > target, the subarray already satisfies the requirement, in order to get the smallest such subarray, we shrink the window size by incrementing the left boundary — windowStart

Compared with the $O(n^2)$ native solution, we achieve $O(n)$ by leveraging the sliding window algorithm, which always keeps track of a valid window that satisfies the requirements.

Problems requiring a map #

A sliding window can be easily integrated with other data structures like a map, to keep track of more sophisticated information within the window. Let’s take a look at 567. Permutation in String

Problem statement #

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is the substring of s2.

Example 1:

Input: s1 = “ab”, s2 = “eidbaooo” Output: true Explanation: s2 contains one permutation of s1 (“ba”).

Example 2:

Input: s1 = “ab”, s2 = “eidboaoo” Output: false

Constraints:

• 1 <= s1.length, s2.length <= 104
• s1 and s2 consist of lowercase English letters.

Solution #

The idea is very similar:

• We keep track of a window by recording the char frequencies in a map.
• Each iteration:
  • Enlarge the current window by moving the windowEnd pointer
  • Update the map to reflect the newly-added char
  • If all chars from s1 are stored in the current window, return true
  • If the size of our window is larger than s1.length(), then we need to shrink it by incrementing the windowStart pointer and updating the map
• If the iteration ends, then s2 is not a permutation of s1, return false

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        Map<Character, Integer> charCntMap = new HashMap<>();

		// init, storing the frequencies of chars in s1 into a map
        for (char ch : s1.toCharArray()) {
            charCntMap.put(ch, charCntMap.getOrDefault(ch, 0) + 1);
        }

        int windowStart = 0, cnt = charCntMap.size();

        for (int windowEnd = 0; windowEnd < s2.length(); ++windowEnd) {
            char ch = s2.charAt(windowEnd);
            // update map
            if (charCntMap.containsKey(ch)) {
                charCntMap.put(ch, charCntMap.get(ch) - 1);
                if (charCntMap.get(ch) == 0) {
                    --cnt;
                }
            }

			// the window is larger than s1, shrink the window and update the map
            if (windowEnd - windowStart + 1 > s1.length()) {
                ch = s2.charAt(windowStart++);

                if (charCntMap.containsKey(ch)) {
                    charCntMap.put(ch, charCntMap.get(ch) + 1);
                    if (charCntMap.get(ch) == 1) {
                        ++cnt;
                    }
                }
            }

			// all chars are present in current window, return true
            if (cnt == 0) {
                return true;
            }
        }
        
        return false;
    }
}

Similar problems：

• 219. Contains Duplicate II
• 904. Fruit Into Baskets

Problems using a set #

In this problem—3. Longest Substring Without Repeating Characters, instead of using a map, a set data structure is utilized to record “presences” of chars in the sliding window.

Problem description #

Given a string s, find the length of the longest substring without duplicate characters.

Example 1:

Input: s = “abcabcbb” Output: 3 Explanation: The answer is “abc”, with the length of 3. Note that "bca" and "cab" are also correct answers.

Example 2:

Input: s = “bbbbb” Output: 1 Explanation: The answer is “b”, with the length of 1.

Example 3:

Input: s = “pwwkew” Output: 3 Explanation: The answer is “wke”, with the length of 3. Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

Solution #

The idea is not too much different from the previous one. Instead of using a map to store char frequencies, in this problem we are only interested in the presence of chars.

At each iteration:

1. We first enlarge the window by 1 as usual.
2. If the char denoted by windowEnd is already present in the set, we need to shrink the window until it is valid, i.e., the window contains no duplicated char:
   • To do so, we shrink the window by moving the left boundary until the same char added in a previous iteration is excluded
3. After the exclusion, we are sure the window meets with the requirement, we then update the maximal length of a valid window we have met.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0, windowStart = 0;

        Set<Character> set = new HashSet<>();

        for (int windowEnd = 0; windowEnd < s.length(); ++windowEnd) {
            char ch = s.charAt(windowEnd);

			// shrink the sliding window until it is legal
            while (set.contains(ch)) {
                set.remove(s.charAt(windowStart++));
            }
        
             set.add(ch);
             // the window is valid now, update res
             res = Math.Max (res, windowEnd - windowStart + 1);
        }
        
        return res;
    }
}

Recap #

The sliding window algorithm is based on iteration, at each iteration, we:

• First, move the right boundary of the sliding window forward by 1
• Update data, no matter it is the summation of elements in the window, or is the frequencies of chars
• Shrink the window if it is invalid by moving the left boundary until the requirement is met. Update any necessary data during the process.

Other sliding window LeetCode problems #

• 424. Longest Repeating Character Replacement
• 643. Maximum Average Subarray I
• 845. Longest Mountain in Array
• 1004. Max Consecutive Ones III
• 1052. Grumpy Bookstore Owner
• 1658. Minimum Operations to Reduce X to Zero