Author avatar

Recnac

Algorithm Templates: Two Pointers - Part 1

Recnac

  • Sep 3, 2020
  • 9 Min read
  • 19,187 Views
  • Sep 3, 2020
  • 9 Min read
  • 19,187 Views

Introduction

As we learned in the introduction to this series of guides, algorithm templates show the core idea of an algorithm. By reusing and reforming these templates, you can easily apply them to new scenarios.

In this guide, we will focus on the two pointers technique, which involves using two pointers to keep track of indices, simplify logic, and save time and space.

We will talk about five variations of two pointers. For each type, we will learn about it through two steps:

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

Two Pointers

The pointer is a very important concept in C/C++, as well as in algorithms. Applied to an algorithm, the pointer can be used to represent the current element in a sequence (such as array or string). We can combine two pointers in different traversal ways to express the complex algorithm logic.

The two pointers technique is widely used in many algorithm scenarios. According to mechanism and usage, I have roughly classified them into five categories:

  1. Old and new state: old, new = new, cur_result
  2. Slow and fast runner: slow-> fast->->
  3. Left and right boundary: |left-> ... <-right|
  4. Pointer-1 and pointer-2 from two sequences: p1-> p2->
  5. Start and end of sliding window: |start-> ... end->|

The above list and the following overview diagram show the core idea of each type in a brief, not rigorous way, just to give you an overview.

two pointers - overview

In the following sections, we will further discuss each type with a code template, diagram, and examples in detail.

Slow and Fast Runner

Template

The first idea is to use two pointers as slow runner and fast runner. Each of them flags a key point during traversal. In general, fast runner grows each iteration and slow runner grows with some restrictions. By that, we can process logic based on these two runners.

1# slow & fast runner: slow-> fast->->
2def slow_fast_runner(self, seq):
3    # initialize slow runner
4    slow = seq[0]   # for index: slow = 0
5    # fast-runner grows each iteration generally
6    for fast in range(seq):     # for index: range(len(seq))
7        #slow-runner grows with some restrictions
8        if self.slow_condition(slow):
9            slow = slow.next    # for index: slow += 1
10        # process logic before or after pointers movement
11        self.process_logic(slow, fast)
python

two pointers - slow fast runner

It should be noted that this template is only for the most common process, and it should be reformed for a more complex scenario, such as the fastrunner also growing with some restrictions. It is most important to understand the idea of the algorithm. In this way, we can draw inferences and expand to a more complex algorithm scenario.

Examples

A classic example is to remove duplicates from a sorted array. We can use the fast runner to represent the current element and use the slow runner to flag the end of the new, non-duplicate array.

Given a sorted array nums, remove the duplicates in place such that each element appear only once and return the new length.

1# [26] https://leetcode.com/problems/remove-duplicates-from-sorted-array/
2def removeDuplicates(nums: 'List[int]') -> int:
3    if not nums:
4        return 0
5    slow = 0
6    for fast in range(1, len(nums)):
7        # if current element is not duplicate, 
8        # slow runner grows one step and copys the current value
9        if nums[slow] != nums[fast]:
10            slow += 1
11            nums[slow] = nums[fast]
12    return slow + 1
python

Let's take another example. Unlike the normal process, the fast runner moves a distance before the slow runner.

Given a linked list, remove the n-th node from the end of the list and return its head.

1# [19] https://leetcode.com/problems/remove-nth-node-from-end-of-list/
2class ListNode:
3    def __init__(self, x):
4        self.val = x
5        self.next = None
6            
7def removeNthFromEnd(head: 'ListNode', n: int) -> 'ListNode':
8    dummy = ListNode(0)
9    dummy.next = head
10    slow, fast = dummy, dummy
11	# fast runner moves n step first
12    for i in range(n):
13        fast = fast.next
14    # slow and fast moves together
15    while fast.next:
16        slow, fast = slow.next, fast.next
17
18    slow.next = slow.next.next
19    return dummy.next
python

Old and New State

Template

Another idea is to use two pointers as variables. In the whole algorithm process, variables store intermediate states and participate in the calculation to generate new states.

1# old & new state: old, new = new, cur_result
2def old_new_state(self, seq):
3    # initialize state
4    old, new = default_val1, default_val2
5    for element in seq:
6        # process current element with old state
7        old, new = new, self.process_logic(element, old)
Python

To better explain the principle of old and new state, I've drawn an example of state transition.

two pointers - new old state 1

From the flowchart, we can see there are three process steps in each iteration:

  1. Calculate cur_result based on old_state and cur_element of the sequence.
  2. Before assigning cur_result to new_state, store the value of new_state to old_state first.
  3. Regard cur_result as the new_state.

After traversing the whole sequence, the results are calculated based on old_state and new_state.

two pointers - new old state 2

Like slow and fast runner, this template represents just the typical usage. The above template and flowchart help you understand the idea. When you migrate to a complex scenario, you'll need to make some extensions and reforms.

Examples

A simple and classic example is calculating a Fibonacci number.

Each number is the sum of the two preceding ones, starting from 0 and 1.

1# [509] https://leetcode.com/problems/fibonacci-number/
2def fibonacci(n: int) -> int:
3	a, b = 0, 1
4	for i in range(n + 1):
5		a, b = b, a + b
6	return a
python

An example with the current element involved:

Determine the maximum amount of money you can steal tonight without robbing adjacent houses.

1# [198] https://leetcode.com/problems/house-robber/
2def rob(nums: 'List[int]') -> int:
3    last, now = 0, 0
4    for i in nums:
5        last, now = now, max(last + i, now)
6    return now
python

In a broader definition, these two variables we maintain are not necessarily the relationship between the former state and the latter state.

Here are two more general usages of the two pointers technique.

Merge two sorted linked lists and return a new list.

1# [21] https://leetcode.com/problems/merge-two-sorted-lists/
2# first make sure that a is the "better" one (meaning b is None or has larger/equal value). Then merge the remainders behind a.
3def mergeTwoLists(a: 'ListNode', b: 'ListNode') -> 'ListNode':
4    if not a or b and a.val > b.val:
5        a, b = b, a
6    if a:
7        a.next = mergeTwoLists2(a.next, b)
8    return a
python

A more complex example with branching logic and complex abstraction:

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

1# [91] https://leetcode.com/problems/decode-ways/
2def numDecodings(s: str) -> int:
3    if len(s) > 0 and s[0] > '0':
4        a, b = 1, 1
5    else:
6        return 0
7    for i in range(1, len(s)):
8        if s[i] == '0':
9            if s[i - 1] > '2' or s[i - 1] == '0':
10                return 0
11            a, b = 0, a
12        elif s[i - 1] == '1' or (s[i - 1] == '2' and s[i] < '7'):
13            a, b = b, a + b
14        else:
15            a, b = b, b
16    return b
python

From the above examples, we can see that the two pointers technique simplifies the complexity of algorithm problems and turns them into the definition and transformation of states.

Conclusion

In this guide, we have learned about a widely used algorithm: the two pointers technique.

First, we introduced the overview and classifications of this technique. Then we discuss slow and fast runner and old and new state using templates and examples.

In Part 2, we will continue to learn about two 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].