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:
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, new = new, cur_result
|left-> ... <-right|
|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.
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 2 3 4 5 6 7 8 9 10 11
# slow & fast runner: slow-> fast->-> def slow_fast_runner(self, seq): # initialize slow runner slow = seq # 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.
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 2 3 4 5 6 7 8 9 10 11 12
#  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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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
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 2 3 4 5 6 7
# 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:
cur_elementof the sequence.
new_state, store the value of
After traversing the whole sequence, the results are calculated based on
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.
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 2 3 4 5 6
#  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.
1 2 3 4 5 6
#  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.
1 2 3 4 5 6 7 8
#  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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
#  https://leetcode.com/problems/decode-ways/ def numDecodings(s: str) -> int: if len(s) > 0 and s > '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.
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]