 Recnac

# Algorithm Templates: Two Pointers - Part 3

• Sep 3, 2020
• 1,996 Views
• Sep 3, 2020
• 1,996 Views

## Introduction

This is the third part of a three-part series on Algorithm Templates: Two Pointers. In the second part, we delved into two other types of two pointers technique. Check it out if you missed it.

In this guide (Part 3), we will focus on the last advanced usage: sliding window. We will also talk about three pointers as an extension.

For each type, we will learn about it through two steps:

1. Describing the concept by algorithm template and flow chart
2. Providing typical examples to help you understand application scenarios and how to use it

## Start and End of Sliding Window

### Template

Sliding window is a useful algorithm technique for typical scenarios. Using the template can greatly simplify the logic of the algorithm. There is a premise: we should determine whether it is suitable for our particular scenario, and we need to make a reasonable abstraction. This template is inspired by these two discussions in LeetCode:

The template for sliding window is a little difficult to understand. So we'll start with a simple version, which focuses only on the two pointers. We use `start` and `end` pointers to make up a window. Then we move these two pointers to make the window slide.

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
``````# start & end of sliding window: |start-> ... end->|
# short version of sliding window, focus on two pointers
def start_end_sliding_window(self, seq):
start, end = 0, 0
while end < len(seq):
# end pointer grows in the outer loop
end += 1

# start pointer grows with some restrict
while self.start_condition(start):
# process logic before pointers movement
self.process_logic1(start, end)
# start grows in the inner loop
start += 1

# or process logic after pointers movement
self.process_logic2(start, end)``````
Python From the above template and diagram, we can see that the `end` pointer grows in the outer loop while the `start` pointer grows in the inner loop. The logic of sliding window should be processed either before the start pointer grows or at the end of the outer loop. We will discuss the specific logic in the following template.

Here is a more specific version of sliding window:

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
``````# more specific version of sliding window
# s - source sequence, p - pattern or restrict sequence
def sliding_window_template_with_examples(s, p):
# initialize the hash map
# counter is used to record current state, usually use Counter or defaultdict
counter = Counter(p)
# two pointers, boundary of sliding window
start, end = 0, 0
# condition checker, update it when trigger some key changes
# the initial value depend on your situation
count = 0
# result, return int (such as max or min) or list (such as all index)
res = 0

# loop the source sequence from begin to end
while end < len(s):
counter[s[end]] += 1
# update count based on some condition
if counter[s[end]] > 1:
count += 1
# end pointer grows in the outer loop
end += 1

# count condition, the condition may be different
while count > 0:
'''
update res here if finding minimum
'''
# increase start pointer to make it invalid or valid again
counter[s[start]] -= 1
# update count based on some condition
if counter[s[start]] > 0:
count -= 1
# start pointer grows in the inner loop
start += 1
'''
update res here if finding maximum
'''
# the result logic may be different
res = max(res, end - start)
return res``````
python

Based on the first version, we added more logical components in this template.

• `counter` is usually defined as a hashmap (`defaultdict` or `Counter` in Python). It is used to record the current state.
• `count` works as a condition checker. We update it when triggering some key changes. It is mainly used for the condition of the inner loop.
• `res` represents the result to achieve. The data type of `res` depends on the requirement, such as int (max or min) or list (get all index).

To make the process more clear, I made a flow chart: From the perspective of process flow, the algorithm is divided into the outer loop and inner loop.

• As we mentioned before, the `end` pointer grows in each outer iteration while the `start` pointer grows in each inner iteration.
• The outer loop handles the logic of the `end` pointer. We update `counter[s[end]]`, which affects the update of `count`. In that way, it will affect the inner loop indirectly.
• The inner loop handles the logic of the `start` pointer. We update `counter[s[start]]` and `count` in the same way.
• If finding minimum, we update `res` logic at the beginning of the inner loop. If finding maximum, we update `res` logic at the end of the outer loop.

It should be noted that this template is only for the most common processes. It demonstrates the core idea of the algorithm, but it needs to be reformed or decorated for a more complex scene. Many parts need to be adjusted according to the actual scenario, such as the definition of the inner loop condition, the way to update `counter`, and how to calculate `res`.

### Examples

Maybe you're still confused about how to use the sliding window technique. Don't worry. We'll get familiar with it through a couple of typical examples with variations.

The sliding window technique is mainly used to solve the substring search problem. First, let's look at an example of finding minimum. As the template shows, we should put the result logic at the beginning of the inner loop.

Given a string S and a string T, find the minimum window in S which will contain all the characters in T.

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
``````#  https://leetcode.com/problems/minimum-window-substring/
def minWindow(s: str, t: str) -> str:
counter = Counter(t)
count, start, end, res = len(t), 0, 0, [float('inf'), 0]
while end < len(s):
counter[s[end]] -= 1
# consider duplicate char in t
if counter[s[end]] >= 0:
count -= 1
end += 1
# valid in while
while count == 0:
# update minimum here, inner while loop
if end - start < res:
res = (end - start, start)

counter[s[start]] += 1
if counter[s[start]] > 0:
count += 1
start += 1
return s[res:res + res] if res != float('inf') else ''``````
python

Here is an example with no pattern involved:

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

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
``````#  https://leetcode.com/problems/longest-substring-without-repeating-characters/
def lengthOfLongestSubstring(s: str) -> int:
# create a default dict to maintain state
counter = defaultdict(int)
count, start, end, res = 0, 0, 0, 0
while end < len(s):
counter[s[end]] += 1
if counter[s[end]] > 1:
count += 1
end += 1
while count > 0:
counter[s[start]] -= 1
if counter[s[start]] > 0:
count -= 1
start += 1
# update maximum here
res = max(res, end - start)
return res``````
python

Besides substring problems, we can also apply sliding window to other similar scenarios.

You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.

What is the total amount of fruit you can collect with this procedure?

In this problem, we need to find the length of the longest sub-array with no more than two distinct integers (fruit types).

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
``````#  https://leetcode.com/problems/fruit-into-baskets/
def totalFruit(tree: 'List[int]') -> int:
counter = defaultdict(int)
count, start, end, res = 0, 0, 0, 0

while end < len(tree):
counter[tree[end]] += 1
if counter[tree[end]] == 1:
count += 1
end += 1
while count > 2:
counter[tree[start]] -= 1
if counter[tree[start]] == 0:
count -= 1
start += 1
res = max(res, end - start)
return res``````
python

A more complex example with complex match policy:

Given a non-empty string containing only digits, determine the total number of ways to decode it.

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
``````#  https://leetcode.com/problems/substring-with-concatenation-of-all-words/
def findSubstring(s: str, words: 'List[str]') -> 'List[int]':
if not words:
return []
word_len, res = len(words), []

# start offset from 0 to word_len, and step is word_len
for i in range(word_len):
# reset state every epoch
counter = Counter(words)
start, < len<, count = i, i, len(words)
while end < len(s):
cur_word = s[end:end + word_len]
# check is not necessary here, just for performance
if cur_word in counter:
counter[cur_word] -= 1
if counter[cur_word] >= 0:
count -= 1
end += word_len
if count == 0:
res.append(start)
# not use a while, use length restriction to ensure consecutive words
if end - start == word_len * len(words):
cur_word = s[start:start + word_len]
if cur_word in counter:
counter[cur_word] += 1
if counter[cur_word] > 0:
count += 1
start += word_len
return res``````
python

From the above examples, we can see that the sliding window technique simplifies the complexity of the algorithm problem and breaks down the problem into logical parts of the template.

## Three Pointers

Based on two pointers, we can extend to more variations, such as three pointers. The idea is similar. With the abstraction of pointers, we simplify the logic and improve the efficiency of the program.

Let's take a classic example of three pointers.

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
``````#  https://leetcode.com/problems/sort-colors/
def sortColors(nums):
red, white, blue = 0, 0, len(nums) - 1

while white <= blue:
if nums[white] == 0:
nums[red], nums[white] = nums[white], nums[red]
white += 1
red += 1
elif nums[white] == 1:
white += 1
else:
nums[white], nums[blue] = nums[blue], nums[white]
blue -= 1``````
python

## Conclusion

In this guide, we learned about the final type of the two pointers technique: sliding window. This template is a bit difficult but very useful in particular scenarios. In addition, we learned three pointers as an extension of two pointers.

To access the complete code, you can download Algorithm Templates from Github. I hope some of them will be useful for you.

If you like this series, please stay tuned. I will update more algorithm templates in the future.

This guide is part of a series on the two pointers technique:

I hope you enjoyed it. If you have any questions, you're welcome to contact me at [email protected]

12