Coding Patterns: Sliding Window

In Coding Patterns series, we will try to recognize common patterns underlying behind each algorithm question, using real examples from Leetcode.

First, we will introduce Sliding Window pattern which is very useful to solve problems in which you are asked to find the longest/shortest string, subarray, or a desired value which you need to calculate from subarrays.

Problem: Maximum Average Subarray

LeetCode 643 - Maximum Average Subarray I [easy]

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example:

Input: [1, 12, -5, -6, 50, 3], k = 4
Output: 12.75
Explanation: Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

Brute Force Solution

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        max_average = 0.0

        for i in range(len(nums) - k + 1):
            _sum = 0.0  # find sum of next k elements

            for j in range(i, i + k):
                _sum += nums[j]

            average = _sum / k  # calculate the average of selected k elements
            max_average = max(max_average, average)  # update max_average

            if len(nums) == 1:  # if there is only 1 element in nums
                return average

        return max_average

Time Complexity: O(N*k) where N is the number of elements in the input array.

This solution exceeds the time limit defined by Leetcode and is not accepted.

If we check our example array again: [1, 12, -5, -6, 50, 3] for k = 4, there are 3 overlapping elements between subarrays [1, 12, -5, -6] and [12, -5, -6, 50]. Can we somehow reuse the _sum we have calculated for the overlapping elements to make our solution more efficient?

Sliding Window Solution

To be able to reuse the _sum from the previous subarray, we will subtract the element going out of the window and add the element now being included in the sliding window.

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        average = []
        _sum, start = 0, 0
        for end in range(len(nums)):
            _sum += nums[end]  # add the next element

            if end >= k - 1:
                average.append(_sum / k)  # calculate the average
                _sum -= nums[start]  # subtract the element going out
                start += 1  # slide the window

        return max(average)

Time Complexity: O(N) where N is the number of elements in the input array.

How to identify?

So we want to be able to identify the problems that sliding window pattern works.

• The problem involves a data structure that is ordered and iterable like arrays, strings, etc.
• The problem is asking to find a subrange in an array/string, contiguous longest, shortest, average or target value.
• There is an apparent naive or brute force solution that runs in O(N²), O(2^N) or some other large time complexity.

The amazing thing about sliding window problems is that most of the time they can be solved in O(N) time and O(1) space complexity.

Similar LeetCode Problems

• LeetCode 3 - Longest Substring Without Repeating Characters [medium]
• LeetCode 30 - Substring with Concatenation of All Words [hard]
• LeetCode 76 - Minimum Window Substring [hard]
• LeetCode 209 - Minimum Size Subarray Sum [medium]
• LeetCode 424 - Longest Repeating Character Replacement [medium]
• LeetCode 438 - Find All Anagrams in a String [medium]
• LeetCode 567 - Permutation in String [medium]
• LeetCode 904 - Fruit Into Baskets [medium]
• LeetCode 1004 - Max Consecutive Ones III [medium]