Sliding Window Pattern - Part 1

This is a commonly used pattern that can be utilized in solving a number of coding interview-type questions associated with arrays.

When should one use this? Well, the problem description usually gives it away. Look out for problems which require inspecting, or calculating some value between elements in contiguous subarray chunks.

Let's elaborate with a straightforward example. Consider the problem which given an array of integers, requires us to return the maximum sum of any contiguous subarray of size k.

The input might take the form:

input_array = [2,4,6,1,9]
k = 3

The answer we are looking for in this example is 16 - this is the sum of the contiguous subarray of length 3 [6,1,9].

The most intuitive way of solving this algorithmically might resemble the following:

def max_subarray_sum(arr, k):
    # keeps track of the max sum encountered so far.
    max_sum = 0
    for i in range(0, len(arr) - k + 1):
        # holds the sum of the current window.
        curr_sum = 0
        for j in range(i, i + k):
            curr_sum += arr[j]
        max_sum = max(max_sum, curr_sum)
    return max_sum

Does this work? It does. However, we are carrying out a lot of unecessary operations when calculating the sum of each subarray. Consider the element 6 in our input array. It is used when calculating the sum of the [2,4,6], [4,6,1], and [6,1,9] subarrays. This makes the algorithm's time complexity O(N * K) where N is the number of elements in the array, and K is the length of the contiguous subarray.

How can we do better? Enter the Sliding Window Pattern.

Whenever we inspect a subarray, we can think of this as a sliding window. When we 'slide' the window, we don't need to recalculate its sum by iterating through every single element in it. Instead, all we have to do is subtract the value of the element that went out the window, and add the value of the element that just entered the window.

Using our previous example consider this:

window_before_sliding = [2,4,6]
window_sum = ([2,4,6])
12
window_after_sliding = [4,6,1]
# subtract 2 - element that went out the window.
# add 1 - elements that just entered the window.
window_sum = window_sum - 2 + 1
11

We can now see how we can use this idea to improve our earlier attempt at solving the problem:

def max_subarray_sum(arr, k):
    # keeps track of the max sum encountered so far.
    max_sum = 0
    # keeps track of the sum of the window currently being inspected.
    window_sum = 0
    # keeps track of the starting index of the window.
    window_start = 0
    for window_end in range(0, len(arr)):
        # add element to the sum of the window currently being inspected.
        window_sum += arr[window_end]
        # condition to prevent sliding from happening before we form the first window of size k.
        if window_end >= k - 1:
            max_sum = max(max_sum, window_sum)
            # subtract value that leaving the window.
            window_sum -= arr[window_start]
            # slide the window forward.
            window_start += 1
    return max_sum

And that's it! Using this technique improves the time complexity of our solution to O(N), a significant improvement. Space complexity is constant O(1) in both cases, as we are not using any ancillary data structures.

What's next?

We have seen the Sliding Window Technique in action and we have seen how it can improve the time complexity when used to solve a problem such as max subarray sum.

This pattern however, truly shines when we use a sliding window of dynamic size. We will examine this technique in the next part of this series and see how it can be used to solve a range of more interesting and difficult problems.