Leetcode is Easy! The Sliding Window Pattern.

Follow up to the Two Pointer Approach.

7 min readDec 21, 2019

Introduction

Today we’ll be learning about the Sliding Window pattern. I’ll go through an overview, walk through the 3 keys steps with an example, and give you a general set of rules to use. As usual, I’ll leave you with a list of practice questions so you can internalize and master the approach yourself.

Overview

Sliding Window is an extension of the two pointer approach where we use two pointers (left and right) to create a “window”. The problem will ask us to return the maximum or minimum subrange that satisfies a given condition. Thus the “window” in between our left and right pointers will be that subrange we are looking for. The sliding window involves expanding and contracting our “window” to find the optimal range.

I’m not going to reinvent the wheel, so go and read up on the details on this amazing Medium post by csgator here. My post serves as an extension of csgator’s post. He goes into the details and inner workings whereas I’ll talk about generalizations and high-level strategy we can remember in order to solve these types of problems in high-pressure interview situations.

We’ll be covering Max Consecutive Ones II in the walkthrough. Open the Leetcode link here and follow along.

3 Key Steps

The Sliding Window boils down to 3 key steps.

Expand our window
Meet the condition and process the window
Contract our window

In code, these 3 key points will create a structure that looks like this.

SLIDING WINDOW PSEUDOCODEdef sliding_window(nums):    # Iterate over elements in our input
        # Expand the window
        # Meet the condition to stop expansion
            # Process the current window   
            # Contract the window

Before we do any of the fun expanding and contracting, we need to think about the condition. What is the condition where we will STOP expanding the window?

Well, it’s always defined by our problem. The problem statement for our walkthrough is below:

MAX CONSECUTIVE ONES II Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.Input: [1,0,1,1,0]
Output: 4

This description is confusing, but we can rephrase it as “Find the largest window that has at most one 0 in it”. Remember, the window will be created as the space (indices) in between our left and right pointers.

So what is the condition that prompts us to stop expanding our window? If we have seen more than one 0.

In other words, we need to expand our window until we have seen two 0’s. Let’s use a variable, count_of_zeroes to keep track of how many 0’s we’ve seen.

CONDITION TO STOP EXPANSIONcount_of_zeroes == 2:

Let’s revisit our code structure to add what we just discussed.

def sliding_window(nums):    left, right = 0, 0        # Intialize our window's bound
    count_of_zeroes = 0       # Track how many 0’s are in the window    # Iterate over elements in our input
    while right < len(nums):        # Expand the window        # Meet the condition to stop expansion
        while count_of_zeroes == 2:            # Process the current window   
            # Contract the window        right += 1

So we expand our window by incrementing right until we have seen TWO 0’s . But wait, how do we know if we’ve seen one 0 or two 0's?

Before we can expand the window, we need to check if the number at the ‘right’ index is a 0. If it is a 0, increment the count of zeroes we’ve seen in our current window.

if nums[right] == 0:
    count_of_zeroes += 1

So let’s add that to our code structure.

def sliding_window(nums):left, right = 0, 0        # Intialize our window's bound
count_of_zeroes = 0       # Track how many 0’s are in the window# Iterate over elements in our input
while right < len(nums):    # Expand the window 
    if nums[right] == 0:        
        count_of_zeroes += 1    # Meet the condition to stop expansion
    while count_of_zeroes == 2:        # Process the current window
        # Contract the window    right += 1

Ok, so now we’ve expanded our window until we’ve met our condition to stop, which means we have TWO 0’s inside our current window.

Now what?

Well, let’s process the current subarray to check if it’s our maximum length we’ve seen so far. Let’s keep track of our maximum length overall as global_max. The space between the right and left pointers is the length of our current window so we can calculate the space by right-left.

global_max = max(global_max, right - left)

So let’s initialize the global_max variable, return it at the end of our algorithm, and add the check if it’s overall max AFTER we’ve met our condition to stop expanding.

Notice below, the right-left calculation works because we don’t actually increment right until AFTER we process the current window.

def sliding_window(nums):    left, right = 0, 0        # Our window bounds
    count_of_zeroes = 0       # Track how many 0’s are in the window
    global_max = 0            # Track the maximum, overall    # Iterate over elements in our input
    while right < len(nums):        # Expand the window 
        if nums[right] == 0:        
            count_of_zeroes += 1        # Meet the condition to stop expansion
        while count_of_zeroes == 2:            # Process the current window
            global_max = max(global_max, right - left)            # Contract the window        right += 1   return global_max

So now we’ve checked if this is the longest we’ve seen. Let’s contract our window by incrementing left in order to get a window with less than two 0's.

But wait, before we increment left, we need to check if the number at the ‘left’ index is a 0. If it is a 0, decrement the count of zeroes we’ve seen in our current window. Notice, this is the exact OPPOSITE of our expansion step.

if nums[left] == 0:
    count_of_zeroes -= 1
left += 1

So let’s add this to our code.

def sliding_window(nums):    left, right = 0, 0        # Our window bounds
    count_of_zeroes = 0       # Track how many 0’s are in the window
    global_max = 0            # Track the maximum, overall    # Iterate over elements in our input
    while right < len(nums):        # Expand the window 
        if nums[right] == 0:        
            count_of_zeroes += 1        # Meet the condition to stop expansion
        while count_of_zeroes == 2:             # Process the current window
            global_max = max(global_max, right - left)            # Contract the window
            if nums[left] == 0:
                count_of_zeroes -= 1
            left += 1        right += 1    return global_max

As a final step, we need to handle an edge case where the maximum subarray is actually the end of the array. See below:

[1, 0, 0, 1, 1, 1, 1, 1]
       l                 rWe never process the current window above because count_of_zeroes never has a chance to equal 2. So do this check at the end:if count_of_zeroes < 2:
    global_max = max(global_max, right-left)

Let’s add that into our code for the final result:

def sliding_window(nums):    left, right = 0, 0        # Our window bounds
    count_of_zeroes = 0       # Track how many 0’s are in the window
    global_max = 0            # Track the maximum, overall    # Iterate over elements in our input
    while right < len(nums):        # Expand the window 
        if nums[right] == 0:        
            count_of_zeroes += 1        # Meet the condition to stop expansion
        while count_of_zeroes == 2:        # Process the current window
            global_max = max(global_max, right - left)        # Contract the window
            if nums[left] == 0:
                count_of_zeroes -= 1
            left += 1        right += 1    if count_of_zeroes < 2:
        global_max = max(global_max, right-left)    return global_max

General Rules

Sliding Window is all about defining a condition to stop expanding, expanding our window until we meet that condition, processing the current window, contracting our window until we can start expanding again until our window has considered the entire string or array.

We will always need these 3 variables:

Window Bounds — I use left and right. Some prefer low and high, or i and j. Whatever you choose, be consistent between problems.
Track Condition — Here we used ‘count_of_zeroes’. Try to be as descriptive as possible so when you read your code the variable name makes sense. It helps logically.
Return Value — Here we used ‘global_max’. Again, it doesn’t matter what you choose, but be consistent. I use ‘global_max’ and ‘global_min’ for all my sliding window problems.

My thought process is always as follows:

Define condition to stop expanding our window
Expand our window until we meet that condition but before expanding the window, process the element at the ‘right’ index.
If we meet our condition to stop expanding, process the current window.
Contract our current window, but before contracting, process the element at the ‘left’ index.
Process Edge Cases.

Once you understand that basic thought process, the only thing you’ll need to change is the condition at which we stop expanding and how we process the left and right elements.

In Leetcode’s Max Consecutive Ones series (I, II, III), you literally just change the condition where we stop expanding the window.

Max Consecutive Ones I 
Given a binary array, find the maximum number of consecutive 1s in this array.Stop Expanding when count_of_zeroes == 1
Max Consecutive Ones II
Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.Stop Expanding when count_of_zeroes == 2
Max Consecutive Ones III
Given an array A of 0s and 1s, we may change up to K values from 0 to 1. Return the length of the longest (contiguous) subarray that contains only 1s.Stop Expanding when count_of_zeroes > K

Practice

Practice the questions below and get into the habit of writing your sliding window algorithms in the same way. Use the same variable names, expand/contract structure, edge cases processing, etc. so that the approach becomes automatic. Once it is automated, this will free up valuable space in your brain for higher-level thinking.