Algorithm Templates: Two Pointers - Part 1
Let's learn about the Two Pointers technique to algorithm templates and two main variations of this technique.
Sep 3, 2020 • 9 Minute Read
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:
- Describing the concept using an algorithm template and flow chart
- 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:
- Old and new state: old, new = new, cur_result
- Slow and fast runner: slow-> fast->->
- Left and right boundary: |left-> ... <-right|
- Pointer-1 and pointer-2 from two sequences: p1-> p2->
- 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.
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.
# slow & fast runner: slow-> fast->->
def slow_fast_runner(self, seq):
# initialize slow runner
slow = seq[0] # for index: slow = 0
# fast-runner grows each iteration generally
for fast in range(seq): # for index: range(len(seq))
#slow-runner grows with some restrictions
if self.slow_condition(slow):
slow = slow.next # for index: slow += 1
# process logic before or after pointers movement
self.process_logic(slow, fast)
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.
# [26] https://leetcode.com/problems/remove-duplicates-from-sorted-array/
def removeDuplicates(nums: 'List[int]') -> int:
if not nums:
return 0
slow = 0
for fast in range(1, len(nums)):
# if current element is not duplicate,
# slow runner grows one step and copys the current value
if nums[slow] != nums[fast]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
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.
# [19] https://leetcode.com/problems/remove-nth-node-from-end-of-list/
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def removeNthFromEnd(head: 'ListNode', n: int) -> 'ListNode':
dummy = ListNode(0)
dummy.next = head
slow, fast = dummy, dummy
# fast runner moves n step first
for i in range(n):
fast = fast.next
# slow and fast moves together
while fast.next:
slow, fast = slow.next, fast.next
slow.next = slow.next.next
return dummy.next
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.
# old & new state: old, new = new, cur_result
def old_new_state(self, seq):
# initialize state
old, new = default_val1, default_val2
for element in seq:
# process current element with old state
old, new = new, self.process_logic(element, old)
To better explain the principle of old and new state, I've drawn an example of state transition.
From the flowchart, we can see there are three process steps in each iteration:
- Calculate cur_result based on old_state and cur_element of the sequence.
- Before assigning cur_result to new_state, store the value of new_state to old_state first.
- Regard cur_result as the new_state.
After traversing the whole sequence, the results are calculated based on old_state and new_state.
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.
# [509] https://leetcode.com/problems/fibonacci-number/
def fibonacci(n: int) -> int:
a, b = 0, 1
for i in range(n + 1):
a, b = b, a + b
return a
An example with the current element involved:
Determine the maximum amount of money you can steal tonight without robbing adjacent houses.
# [198] https://leetcode.com/problems/house-robber/
def rob(nums: 'List[int]') -> int:
last, now = 0, 0
for i in nums:
last, now = now, max(last + i, now)
return now
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.
# [21] https://leetcode.com/problems/merge-two-sorted-lists/
# first make sure that a is the "better" one (meaning b is None or has larger/equal value). Then merge the remainders behind a.
def mergeTwoLists(a: 'ListNode', b: 'ListNode') -> 'ListNode':
if not a or b and a.val > b.val:
a, b = b, a
if a:
a.next = mergeTwoLists2(a.next, b)
return a
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.
# [91] https://leetcode.com/problems/decode-ways/
def numDecodings(s: str) -> int:
if len(s) > 0 and s[0] > '0':
a, b = 1, 1
else:
return 0
for i in range(1, len(s)):
if s[i] == '0':
if s[i - 1] > '2' or s[i - 1] == '0':
return 0
a, b = 0, a
elif s[i - 1] == '1' or (s[i - 1] == '2' and s[i] < '7'):
a, b = b, a + b
else:
a, b = b, b
return b
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:
- Algorithm Templates: Introduction
- Algorithm Templates: Two Pointers - Part 1
- Algorithm Templates: Two Pointers - Part 2
- Algorithm Templates: Two Pointers - Part 3
I hope you enjoyed it. If you have any questions, you're welcome to contact me at recnac@foxmail.com.