Contents

Effective LeetCode: Understanding the Sliding Window Pattern

Identifying patterns among questions is quite an effective strategy when you are grinding LeetCode in preparation for your upcoming software engineering interviews. In this article, you will develop intuitions about Sliding Window pattern. You will also get a template approach to write code to solve these problems. I will also walk you through some LeetCode questions to show how to apply the template and at the end, there will be some LeetCode exercises for you to practice what you learn.

Why Should One Focus on Programming Question Patterns?

Whether you like them or not, solving programming challenges is a prevalent part of software engineering interviews. Most newbies and seasoned developers turn to leetcode.com to find a wide set of questions and discussion forums to help their interview preparations. However, many are baffled upon finding a more than a thousand questions on the website and not knowing where to start from. Many people in LeetCode and other discussion forums have shared their learning paths with other learners in the form of compiled list of questions that vary from difficulty level, question types, interviewing company and so on. A common occurring themes among those recommendations is to spend time on identifying patterns among questions. It helps in reinforcing your brain to think about the solution in more general terms so that you don’t have to cram your memory with specific details for individual questions. This way you will be better prepared to take on such programming challenges that may quiz you on a diverse range of Data Structure and Algorithm questions.

Through a series of articles on these patterns, I will share the tips and tricks from what I have learned while solving LeetCode problems. And hopefully it will help you to prepare more effectively and faster for your software programming rounds of interviews.

Sliding Window Pattern

Generally speaking, in sliding window problems, you would be given a sequence of values, and your task will be to return the best solution given a limiting constraint. The best solution would be defined in terms of a maximum or minimum value that occurs in a range or “window” over the given sequence. I know, it sounds a bit too generic. So, let’s try to materialize the idea with a fun example.

An Intuitive Analogy

Let’s assume you are playing an Animal-Crossing-meets-SIMS game. And you are in-charge of many cute little characters currently living on different islands in the game doing some fun tasks.

/img/posts/leetcode-sliding-window/intro.png

This game allows these characters to collaborate such that they can visit other islands and do tasks together. However, in order to connect any two islands, you will have to make some standard-length connecting bridges. And, some of the islands may be farther away from each other, so they may require more than one connecting bridge. For simplicity, we are going to assume that the islands are located linearly as shown in the figure.

/img/posts/leetcode-sliding-window/intro_bridges.png

As you play new quests in the game, and finish daily tasks, you can unlock more of these connecting bridges. But at any given point of time, you will have a limited number of bridges in your collection.

Now your task is to use the available bridge count and connect the islands such that you end up with maximum possible number of characters connected with each other.

Say if you had 2 bridges available, would you choose move 1 or move 2 from below?

/img/posts/leetcode-sliding-window/two_actions.png

With move 1, you connect the first two islands and the two characters on those islands together. However, with move 2, you connect the last three islands and four of your characters together. So the second move give you the best answer. As an exercise, can you think of any other moves in the above setting? What results would you get in those?

While thinking of a solution to the above questions, you were given a constraint (limited number of available bridges) and you found an optimized solution (maximum number of characters connected). Because there were a limited number of islands and characters, you were able to simply eyeball and easily come up with a solution that was the best with the given constraint. But as you can imagine, the things can get a lot trickier if you have tens of thousands of islands with thousands of characters living on them and maybe hundreds of bridges available at your disposal. So, let’s summon the coder in you and formulate this problem as a programming challenge.

The Sliding Window Approach

First, we are going to represent the arrangement of islands, bridges and characters in terms of a sequence of values, i.e. an array. So, let’s assume that an index in array with value -1 mean an empty location between islands where you could build a bridge, value 0 signifies the presence of a bridge at that location, and any other number is simply a count of the number of characters on the island at that index.

/img/posts/leetcode-sliding-window/make_array.png

So your goal is to find the maximum count for connected characters given a fixed number of bridges, B (for example, B=2). Before jumping into code, we need to first develop solid intuitions about Sliding Window approach and how it can help us in this problem.

As you saw in the last section, we got our solution from a contiguous subsequence, i.e. a subarray.

/img/posts/leetcode-sliding-window/subarray.png

This subarray highlighted in red, is what we call a window. The left end, L, of the window is at index 3 and right end, R, is at index 7 (assuming index start at 0). This window spans over 5 array elements, so we can also say that the window length is 5. In Sliding Window pattern problems, we will calculate multiple solutions over varying length of the window, but we will only save the most optimal solution.

A naïve approach could be to evaluate the input array for all possible length of windows, i.e. all possible placements for windows of length 1, 2, 3, 4, … , 8 (size of array), and calculate the result for each window, but save only the optimal value (maximum, in our example). However, as any seasoned LeetCode-er will tell you, your program will easily hit a Time Limit Exceeded wall even with a moderate sized array, because you have way too many potential solutions in your search space. So we need a better solution.

Let’s solve the above problem that had a constraint of 2 bridges with a Sliding Window approach.

In a sliding Window based solution, we will generally start from the left of the array and with a window of size 1, i.e. both the left and right ends, L and R respectively, of the window will be at index 0. At each step, we also calculate the current answer, i.e. the current number of connected characters inside the window, and save the most optimal solution, i.e. the maximum count so far.

/img/posts/leetcode-sliding-window/step_1.png

Now, let’s expand the window by moving the right end, R, as much as our constraint allows us (think of this as an outer loop in the code). The constraint in this example being the count of available bridges (B = 2).

/img/posts/leetcode-sliding-window/step_2_1.png

We used one bridge, but we do have one more left. So we keep expanding to right.

/img/posts/leetcode-sliding-window/step_2_2.png

We are out of bridges to use, but we can still move to the right, as there’s an island there and our constraint will still hold (max 2 bridges).

/img/posts/leetcode-sliding-window/step_2_3.png

We now have 2 connected characters, which is also our best answer so far. But we also have a problem, we can’t move to the right because that’s an empty slot and we are out of bridges to use. So now we will start to shrink our window from the left marker one step at a time, and keep doing it until we are allowed to move R to the right and still satisfy our constraint (think of it as another loop inside the outer one).

/img/posts/leetcode-sliding-window/step_2_4.png

At this point, we still can’t move R to the right, because we are out of bridges. So let’s move L to the right one more time and reclaim one bridge.

/img/posts/leetcode-sliding-window/step_2_5.png

Now we’re back on track. Moving R to the right requires a new bridge, but we do have that in inventory.

/img/posts/leetcode-sliding-window/step_2_6.png

Moving R to the right is still valid, so let’s do it.

/img/posts/leetcode-sliding-window/step_2_7.png

Moving R requires a bridge. So we go back to moving L to the right, and reclaim one bridge with the very first move.

/img/posts/leetcode-sliding-window/step_2_8.png

Moving R will make us use the bridge that we have in inventory.

/img/posts/leetcode-sliding-window/step_2_9.png

We can still move R more to the right.

/img/posts/leetcode-sliding-window/step_2_10.png

We can’t move R anymore. That brings us to the end of our algorithm. The best answer that we have is 4, which is also the most optimal answer. 😊

Notice the followings:

  • We started with 2 markers left (L) and right (R) at index 0
  • R moved to the right towards the end of the array (we can use an outer loop for this)
  • Inside the above looping process, if we hit a state where moving R will force us to break the constraint, we move L to the right till we reach a state where R can be moved again (we can use another loop here)
  • At each state during this process, we save the current answer and update the best answer variable if this value is better than the previous one

You can also think of the approach in terms of a template like this:

/img/posts/leetcode-sliding-window/template.png

… and that’s it. That’s all you need to write a program that uses Sliding Window approach to find an optimal solution. Let’s make this understanding more concrete with the help of an actual LeetCode question.

Solving LeetCode Problems with Sliding Window Pattern

LeetCode 1004: Max Consecutive Ones III

Let’s try to apply what we you have learned above and solve this LeetCode problem: https://leetcode.com/problems/max-consecutive-ones-iii/

You are given an array input that has 0s and 1s. You are given a constraint that you can change only K number of values from 0 to 1. And, your task is to find the longest subarray that contains only 1s.

So, we are looking for the maximum window size (i.e. R - L + 1), such that the window contains all 1s, and given the constraint that we can change up to K number of values in the window from 0 to 1.

Let’s first setup some basic variables:

1
2
3
current_change_count = 0 # This is our "inventory", i.e. a count for the number of changes from 0 to 1
L = 0 # This is the left marker of our Sliding Window
answer = -1 # This is the variable that will store the best answer

Based on the earlier template, we need an outer loop, that will move R to the right.

1
2
for R in range(len(A)): # Here A is the input array
	...

Inside the for loop, we need to update our “inventory”, i.e. current_change_count, if required i.e. if the value of the current position is 0, we need to make it 1 to include it in the window

1
2
if A[R] == 0:
    current_change_count += 1

And we need an inner loop to move L to the right, if required i.e. if the constraint “current_change_count <= K” doesn’t hold.

1
2
3
4
while current_change_count > K and L < len(A):
    if A[L] == 0:
        current_change_count -= 1
    L += 1

Finally we save the current answer as the best answer, if required, i.e. if the current window length (R-L+1) is greater than answer.

1
answer = max(answer, R-L+1)

So, our complete solution will be:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        if not A:
            return 0
                
        current_change_count = 0
        L = 0
        answer = -1
        
        for R in range(len(A)):
            if A[R] == 0:
                current_change_count += 1
            
            while current_change_count > K and L < len(A):
                if A[L] == 0:
                    current_change_count -= 1
                L += 1
                
            answer = max(answer, R-L+1)
        
        return answer

LeetCode 1358: Number of Substrings Containing All Three Characters

Let’s take another example: https://leetcode.com/problems/number-of-substrings-containing-all-three-characters/

A valid window in this case is the one that satisfies the constraint that all of the three characters ‘a’, ‘b’ and ‘c’ are at least once present in the window.

Let’s setup some basic variables:

1
2
3
4
current_answer = 0
looking_for = [0, 0, 0] # We will save the count of 'a', 'b' and 'c' occurances in the window on the 3 indexes in this array/list
L = 0
best_answer = 0

The outer loop will simply be:

1
2
for R in S:
    ...

Our inventory, in this case, keeps track of the count of ‘a’, ‘b’ and ‘c’ in “looking_for” list. Since we know each character in the input will be one of the three characters, we can directly update the index like this:

1
looking_for[ord(R)-ord('a')] += 1

and the inner loop will move L to the right if the window has ‘a’, ‘b’ and ‘c’ occurring at least once.

1
2
3
4
while L < len(s) and looking_for[0] and looking_for[1] and looking_for[2]:
    looking_for[ord(s[L])-ord('a')] -= 1 # subtract count for the character at L
    L += 1
    current_answer += 1

The optimal answer will simply add up the overall answers found in the Sliding Window.

1
best_answer += current_answer

So, our complete solution will be:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        if len(s) < 3:
            return 0
        
        current_answer = 0
        looking_for = [0, 0, 0]
        L = 0
        best_answer = 0
        
        for R in s:
            looking_for[ord(R)-ord('a')] += 1
            
            while L < len(s) and looking_for[0] and looking_for[1] and looking_for[2]:
                looking_for[ord(s[L])-ord('a')] -= 1
                L += 1
                current_answer += 1
            
            best_answer += current_answer
        
        return best_answer

LeetCode 904: Fruit Into Baskets

Let’s solve yet another LeetCode question with this approach: https://leetcode.com/problems/fruit-into-baskets/

In this problem, we maintain an inventory of two baskets with a each count containing a fruit type (kind of a “key”), and a fruit count (kind of a “value”), so we can simply make it a hashmap, i.e. a Python dictionary. The constraint here is that we can only have maximum 2 baskets, with each having a unique fruit type. Our goal is to find the maximum count of fruits in both baskets.

First, we setup some basic variables:

1
2
3
L = 0
inventory_hashmap = {}
best_answer = 0

Then we setup an outer loop for moving R.

1
2
for R in range(len(tree)):
    ...

We update the inventory, i.e. our hashmap with keys representing the fruit type and the values representing the number of fruits picked during current window.

1
inventory_hashmap[tree[R]] = inventory_hashmap.get(tree[R], 0) + 1

Next, we move L to the right, and remove the corresponding count and fruit type from the inventory, if the constraint is broken.

1
2
3
4
5
while L < len(tree) and len(inventory_hashmap) > 2:
    inventory_hashmap[tree[L]]-= 1                
    if inventory_hashmap[tree[L]] == 0:
        del inventory_hashmap[tree[L]]
        L += 1

Finally, we update the best answer by finding the maximum value between the best answer so far, and the current number of fruits in our inventory.

1
best_answer = max(best_answer, sum(inventory_hashmap.values()))

Adding all the components together, our solution will be this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        if not tree:
            return 0
        
        L = 0
        inventory_hashmap = {}
        best_answer = 0
        
        for R in range(len(tree)):
            inventory_hashmap[tree[R]] = inventory_hashmap.get(tree[R], 0) + 1
            
            while L < len(tree) and len(inventory_hashmap) > 2:
                inventory_hashmap[tree[L]]-= 1                
                if inventory_hashmap[tree[L]] == 0:
                    del inventory_hashmap[tree[L]]
                L += 1
            
            best_answer = max(best_answer, sum(inventory_hashmap.values()))
        
        return best_answer

Summing Up

I hope these examples were good enough to drive home the intuitions required to build a Sliding Window based solution. I would also like to point out that the template that I talked explained in this article is the most common strategy with Sliding Window problems, however it is not the only kind of Sliding Window approach. As you saw, in our template, the right marker R moves faster than the left marker L, therefore this approach is sometimes referred to as Fast/Slow Sliding Window approach. There are other approaches like Fast/Catch-Up and Front/Back that I will talk about in a future post.

Exercise for the Readers

If you want to apply what you have learned in this article, and solve a few LeetCode challenges, then you can try your hand on the following Sliding Window problems on LeetCode website:

I also want to thank the LeetCode user wh0ami for compiling this list of questions and sharing this idea, in his C++ post at LeetCode discussion forums here.