Author avatar

Recnac

Algorithm Templates: Two Pointers - Part 2

Recnac

  • Feb 22, 2020
  • 12 Min read
  • 740 Views
  • Feb 22, 2020
  • 12 Min read
  • 740 Views

Introduction

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

In this guide (Part 2), we will focus on another two common usages:

  1. Left and right boundary
  2. Pointer-1 and pointer-2 from two sequences

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

Left and Right Boundary

Template

Another common usage is putting pointers on the left-most side and right-most side. One pointer starts from the beginning, while the other pointer starts from the end. They move toward each other until they meet in the middle.

1
2
3
4
5
6
7
8
9
10
11
12
# left & right boundary: left-> <-right
def left_right_boundary(self, seq):
    left, right = 0, len(seq) - 1
    while left < right:
        # left index moves when satisfy the condition
        if self.left_condition(left):
            left += 1
        # right index move when satisfy the condition
        if self.right_condition(right):
            right -= 1
        # process logic before or after pointers movement
        self.process_logic(left, right)
Python

To better understand the theory of left and right boundary, you can refer to the following example chart.

two pointers - left right boundary

In general, the algorithm can be used in two ways based on this technology:

  1. Left and right pointers form an interval to process.
  2. These two pointers carry information and handle the logic in each iteration.

Examples

The most classic and famous example is binary search. We find the target by shrinking the lower and upper bounds continuously. We cut off the half of the interval in each iteration. The following example is a version with both lower and upper bounds included.

1
2
3
4
5
6
7
8
9
10
11
12
# [lo, hi] version, modify to [lo, hi) version as you need
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        # find the target, change to your comparison condition as you need
        if arr[mid] == target:
            break
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
python

Let's take a look at a practical example with two pointers and binary search technique.

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

1
2
3
4
5
6
7
8
9
10
11
# [167] https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
def twoSum(numbers: 'List[int]', target: 'int') -> 'List[int]':
    left, right = 0, len(numbers) - 1
    while left < right:
        if numbers[left] + numbers[right] == target:
            return [left + 1, right + 1]
        if numbers[left] + numbers[right] < target:
            left += 1
        else:
            right -= 1
    return [0, 0]
python

Let's make it a little more difficult. Upgrade the two-sum problem to four-sum.

Find all unique quadruplets in the array which gives the sum of target.

Idea: With the help of the above example, the solution is very clear. We can use the left and right boundary to find the solution space. We can divide the four-sum problem to three-sum, and finally to two-sum.

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
42
43
44
45
# [18] https://leetcode.com/problems/4sum/
def fourSum(nums: 'List[int]', target: int) -> 'List[int]':
    result, n = [], len(nums)
    if n < 4: return result
    nums = sorted(nums)
    if sum(nums[-4:]) < target:
        return result

    for i in range(n - 3):
        # boundary checker, stop early
        if sum(nums[i:i + 4]) > target:
            break
        # right boundary checker
        if nums[i] + sum(nums[-3:]) < target:
            continue
        # skip same element, but keep the first one
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        # simplify the problem to three sum
        target2 = target - nums[i]
        for j in range(i + 1, n - 2):
            if sum(nums[j:j + 3]) > target2 or sum(nums[-3:]) < target2:
                break
            if nums[j] + sum(nums[-2:]) < target2:
                continue
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            # simplify the problem to two sum
            target3 = target2 - nums[j]
            left = j + 1
            right = n - 1
            while left < right:
                if nums[left] + nums[right] == target3:
                    result.append([nums[i], nums[j], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif nums[left] + nums[right] < target3:
                    left += 1
                else:
                    right -= 1
    return result
python

Here is an example in which we focus on the interval.

Find two lines, which together with x-axis form a container, such that the container contains the most water possible.

Idea: To help you understand, I've drawn an example diagram. We calculate the water area by the interval formed by the current left and right bounds.

two pointers - left right boundary example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# [11] https://leetcode.com/problems/container-with-most-water/
def maxArea(height: 'List[int]') -> int:
    left, right = 0, len(height) - 1
    area_max = (right - left) * min(height[left], height[right])

    while left < right:
        # judge which side decide the area (shorter height)
        if height[left] <= height[right]:
            last_height = height[left]
            # skip all the height less than current
            while height[left] <= last_height and left < right:  
                left += 1
        else:
            last_height = height[right]
            # skip all the height less than current
            while height[right] <= last_height and left < right:  
                right -= 1

        if left >= right:
            return area_max
        area_max = max(area_max, (right - left) * min(height[left], height[right]))
    return area_max
python

Pointer-1 and Pointer-2 from Two Sequences

Template

In some other scenarios, we need to compare in two sequences. Each pointer represents the current logical position in the corresponding sequence.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# p1 & p2 from two sequences: p1-> p2->
def pointers_from_two_seq(self, seq1, seq2):
    # init pointers
    p1, p2 = 0, 0       # or seq1[0], seq2[0]
    # or other condition
    while p1 < len(seq1) and p2 < len(seq2):
        # p1 index moves when satisfy the condition
        if self.p1_condition(p1):
            p1 += 1         # or p1 = next(seq1)
        # p2 index move when satisfy the condition
        if self.p2_condition(p2):
            p2 += 1         # or p2 = next(seq2)
        # process logic before or after pointers movement
        self.process_logic(p1, p2)
python

From the following example diagram, we can see that these two pointers are relatively independent. How they move forward is determined by their own strategies.

two pointers - pointers from two seq

Examples

Let's look at an example with multiple sequences.

Design a class which receives a list of words in the constructor and implements a method that takes two words, word1 and word2, and returns the shortest distance between these two words in the list.

Idea: First, we create a group of index sequences, locations, for each word. Every time shortest function is called, we pick up the corresponding sequences loc1 and loc2. Then we use two pointers, l1 and l2, to calculate the shortest distance. In each iteration, the smaller pointer moves one step forward.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# [244] https://leetcode.com/problems/shortest-word-distance-ii/
class WordDistance:
    def __init__(self, words: 'List[str]'):
        self.locations = defaultdict(list)
        # Prepare a mapping from a word to all it's locations (indices).
        for i, w in enumerate(words):
            self.locations[w].append(i)

    def shortest(self, word1: str, word2: str) -> int:
        loc1, loc2 = self.locations[word1], self.locations[word2]
        l1, l2 = 0, 0
        min_diff = float("inf")

        # Until the shorter of the two lists is processed
        while l1 < len(loc1) and l2 < len(loc2):
            min_diff = min(min_diff, abs(loc1[l1] - loc2[l2]))
            if loc1[l1] < loc2[l2]:
                l1 += 1
            else:
                l2 += 1
        return min_diff
python

Here is another example combined with backtracking.

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

Idea: Assign one pointer s_cur for the target string and another p_cur for the pattern. The two pointers record the current match position. When matching '*', match and star are the flags that help to backtrack if matching failed in greedy.

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
# [44] https://leetcode.com/problems/wildcard-matching/
def isMatch(s: str, p: str) -> bool:
    s_cur, p_cur, match, star = 0, 0, 0, -1

    while s_cur < len(s):
        # match sucess, both two pointers move forward
        if p_cur < len(p) and (s[s_cur] == p[p_cur] or p[p_cur] == '?'):
            s_cur += 1
            p_cur += 1
        # if matching star, record current state and try to match in greedy
        elif p_cur < len(p) and p[p_cur] == '*':
            match = s_cur
            star = p_cur
            p_cur += 1
        # backtrack if match failed
        elif star != -1:
            p_cur = star + 1
            match += 1
            s_cur = match
        else:
            return False
    # corner case: remove continuous star in the rest
    while p_cur < len(p) and p[p_cur] == '*':
        p_cur += 1

    if p_cur == len(p):
        return True
    else:
        return False
python

Conclusion

In this guide, we continued learning about two other types of the two pointers technique through templates and examples: left and right boundary and pointer-1 and pointer-2 from two sequences.

In the third part, we will continue to learn about other types 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.

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]

5