The Two-Pointer Technique
In this second installment of my Algorithms and Data Structures Series, I explain a very common technique used in search algorithms: the two-pointer technique. The first installment, Sliding Window Problems in JavaScript, is not a prerequisite for understanding the material in this article, but it covers another common coding pattern useful for software engineering interview questions and can be read here.
Why Two Pointers?
Many questions involving data stored in arrays or linked lists ask us to find sets of data that fit a certain condition or criterion. Enter two pointers: we could solve these problems by brute force using a single iterator, but this often involves nesting loops, which increases the time complexity of a solution exponentially. Instead, we can use two pointers, or iterator variables, to track the beginning and end of subsets within the data, and then check for the condition or criterion.
Recognizing a Two-Pointer Problem
As I am currently strengthening my knowledge of data structures and algorithms, I have found that one of the most difficult things to do is to recognize when I need to use a two-pointer technique, and if I do, which type. This may be obvious to others, but since it was/is not to me, I am going to explain here in some detail.
The first clue that a two-pointer approach might be needed is that the problem asks for a set of elements — that fit a certain pattern or constraint — to be found in a sorted array or linked list. In a sorted array, there is additional information about the endpoints as compared to an unsorted array. For example, if an array of integers is sorted in ascending order, we know that the start position of the array is the smallest or most negative integer, and the end position is the greatest or most positive. Therefore, if a problem presents a sorted array, it is very likely able to be solved using a two-pointer technique where the pointers are initially assigned the values of the first and last members of the array. An example of this is illustrated below for further clarification. In a linked list, by contrast, the most likely solution will involve pointers moving in tandem to ‘look’ for the constraint or condition of the problem.
The second clue that a two-pointer approach might be needed is that the problem asks for something to be found in, inserted into, or removed from a linked list. Knowing the exact position or length of a linked list means moving through every node before that position (all nodes if length is needed). We know each node in the list is connected to the next node in the list until the tail of the list. In this case, tandem pointers or a fast and slow pointer approach will likely serve to solve the problem. An example of the fast and slow pointer approach is illustrated below.
Example: Two Sum Problem with Sorted Input Array
Problem: given an array sorted in increasing order, find two numbers such that they add up to a specific target. Return the indices of the two numbers.
Constraints: the input array is sorted ascending and will contain exactly one solution. The array is 1-indexed.
Pseudocode:
function(array, target){
set a left pointer to the first element of the array
set a right pointer to the last element of the array
loop through the array; check if left and right add to target
sum is less than the target, increase left pointer
sum is greater than the target, decrease right pointer
once their sum equals the target, return their indices
}The pseudocode illustrates the most classic case of a two-pointer problem, where the pointers start out as the ends of a sorted array. In this case, we are looking for two members of an array to add to a specific target value. Here is the real code, with the pseudocode left in as comments:
var twoSum = function(numbers, target) {
// set a left pointer to the first element of the array
let left = 1;
// set a right pointer to the last element of the array
let right = numbers.length
// loop through the array; check if left and right add to target
while(numbers[left - 1] + numbers[right - 1] !== target){
// sum is less than the target, increase left pointer
if(numbers[left - 1] + numbers[right - 1] < target){
left++
// sum is greater than the target, decrease right pointer
} else {
right--
}
}
// once their sum equals the target, return their indices
return[left, right]
};To practice this problem or try a different solution, check it out on LeetCode.
Example: Removing the nth Element from the End of a Linked List
Problem: write a function that accepts the head node of a linked list and a number n, and then removes the nth element from the end of the linked list.
Constraints: n will be less than the length of the linked list.
Pseudocode:
function(head, n) {
set up two pointers
initially, both should be equal to the head
check if the head is the only node + remove it
iterate the second pointer n places ahead of the first
if the second pointer is null, remove the head (because the head is the nth from the end if this is the case)
iterate both pointers until the second pointer is the tail
if there is a node two ahead of the first pointer, set it as the next node of the first pointer ('dropping' the nth node)
if there is no node two ahead of the first pointer, the first pointer is now the tail and its next should be set to null
return head
}The pseudocode illustrates how this is a two-pointer problem where the iterators move in tandem. Once the two pointers are a distance of n apart in the linked list, they move at the same pace until the second pointer reaches the tail. Here is the actual code, with pseudocode as comments:
var removeNthFromEnd = function(head, n) {
// set up two pointers
// initially, both should be equal to the head
let left = head;
let right = head; // check if the head is the only node + remove it
if(!head.next) return null // iterate the second pointer n places ahead of the first
let i = 0;
while(i++ < n){
right = right.next
} // if the second pointer is null, remove the head
// (because the head is the nth from the end if this is the case)
if(right === null){
return head = head.next
} // iterate both pointers until the second pointer is the tail
while(right && right.next){
right = right.next
left = left.next
}
// if there is a node two ahead of the first pointer,
// set it as the next node of the first pointer
// ('dropping' the nth node)
// if there is no node two ahead of the first pointer,
// the first pointer is now the tail and its next should
// be set to null
left.next = left.next.next ? left.next.next : null // return head
return head
};
To practice this problem or try a different solution, check it out on LeetCode.
Example: Finding the Middle of a Linked List
Problem: given the head of a singly-linked list, find and return the middle node of the list. If there are two middle nodes, return the second.
Constraints: the number of nodes will range from 1–100 inclusive.
Pseudocode:
function(head){
set a slow and a fast pointer to the head
iterate the pointers through the list
fast should move twice the speed of slow
once fast reaches the tail, slow will be at the middle
if there are two middles, slow will be at the second middle
return slow
}This is a simple problem of considering the linked list mathematically. The halfway point is half the distance to the endpoint, therefore if we have a slow pointer moving half the speed of the fast pointer, it will sit at the middle node when the fast pointer sits at the tail. Remember that we can define the tail node by the fact that its next node is null. Here is the actual code, with pseudocode as comments:
var middleNode = function(head) {
// set a slow and a fast pointer to the head
let slow = head;
let fast = head; // iterate the pointers through the list
while(fast !== null && fast.next !== null){
// fast should move twice the speed of slow
slow = slow.next
fast = fast.next.next
} // once fast reaches the tail, slow will be at the middle
// if there are two middles, slow will be at the second middle
// return slow
return slow
};
To practice this problem or try a different solution, check it out on LeetCode.
In this article, and as a part of my own knowledge-building, I have attempted to explain how a certain type of search algorithm can be written using the two-pointer approach. Whether the pointers start together and move in tandem, employ a fast and slow method, or start at opposite ends of an array, these methods save time by reducing the number of loops needed in our code. For more practice problems, check out LeetCode’s brief explanation of the technique and problem list here. For another great in-depth explanation that is not mine, check out this article.
