Algorithm Templates: Two Pointers - Part 1
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.
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)
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 + 1Let'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.nextOld 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)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_resultbased onold_stateandcur_elementof the sequence. - Before assigning
cur_resulttonew_state, store the value ofnew_statetoold_statefirst. - Regard
cur_resultas thenew_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.
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 aAn 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 nowIn 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 aA 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 bFrom 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].