Two-Pass, Two-Pointer: What’s the Difference?
A breakdown of two problem solving techniques, and when to use them.
The two-pointer technique is commonly used to optimize solutions to string, array, or linked-list coding problems. In naive solutions, searching for a set of elements in one of those data structures, in the worst-case, can have a polynomial-time complexity such as O(n²), O(n³), O(n⁴), etc. However, using the two-pointer technique on sorted data, the time complexity is reduced to O(n). On the other hand, although the two-pass approach is also used to solve string, array, or linked-list coding problems, it might not necessarily be an optimal solution.
What is the two-pass approach?
The two-pass approach uses two independent loops to solve a problem; the first loop used extracts some information about the state of the input, and the second loop uses that information to solve the problem.
For example, Sort Colors is a coding problem offered on Leetcode. The crux of the problem is to sort all the objects in-place such that the same colors (numbers) are adjacent, with numbers sorted from 0 to 2.
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]Although the two-pass approach allows us to solve the problem in the worst-case time of O(n), the space complexity is also O(n). O(n) is due to the need to store the number of occurrences for each number/color in a data structure (I used an array, but the same would hold for a hash map, because it still takes up multiple slots in memory).
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function(nums) {
const colorMap = [0, 0, 0]
// record the number of occurences for each number/color
for (let i of nums) {
colorMap[i] += 1
}
let start = 0
for (let key = 0; key < 3; key++) {
// use colorMap to change nums in-place
}
}However, there are instances where using the two-pass approach produces an optimal space complexity, for example, in the Leetcode problem Move Zeros. In this problem, all zeros in the input must be at the end of the array, and it must happen in-place.
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]In this case, the first loop in the two-pass approach counts the number of zero occurrences in the input, and the data is stored as an integer variable. Therefore, the space complexity is O(1).
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
let count = 0
for (x of nums) {
count += x == 0 ? 1 : 0
}
let ptr = 0
let found = 0
while (ptr < nums.length && found != count) {
//solve using the count
}
};What’s the two-pointer approach?
The two-pointer approach uses two variables to trace over each element in a data structure. However, unlike the two-pass approach, the two-pointer technique provides us with a bit of flexibility to look-ahead, look-behind, and compare different windows of data. It analyzes the state of the input and transforms it with each iteration of the loop.
There are two types of two-pointer techniques.
Equi-directional: Both pointers start from the beginning, but one is a fast-running pointer, whereas the second pointer is a slow-running pointer. The slow-running pointer is updated when some condition is met. This two-pointer technique can help us analyze different windows of the input, explore and compare subsets of the input, or detecting cycles in an input.
Here’s is an example solution of Sort Colors, using the Equi-directional approach. Notice, the slow pointer is only updated once the fast pointer has searched the entire array. There’s a lot more to this solution than this sample I’ve provided, but this is the basic idea.
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function(nums) {
let slow_pointer = 0 // slow pointer
let fast_pointer = n+1 // fast pointer
// other variables ...
while (slow_pointer < nums.length) {
/// do a lot of work here .....fast_pointer ++; // updated on every iterationif (fast_pointer >= nums.length) {
slow_pointer = nxt
nxt = slow_pointer + 1
fast_pointer = nxt
// ... other variables
}
}
};
Opposite Directional: Two pointers starting from different ends of the input. They move towards each other until some condition is met. This two-pointer technique can help us move data efficiently within the input, compare different ends of the input, and it can also detect cycles.
In this sample solution of Move Zeros, both pointers are moving towards each other, given a particular condition. In the opposite directional approach, there isn’t necessarily a “fast pointer” or “slow pointer,” the idea is that both pointers are move at relatively the same speed until they overlap.
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
...
let pointerA = 0
let pointerB = nums.length - 1
while (pointerA != pointerB) {
if (nums[pointerA] == 0) {
// ... do something then, update pointer
pointerB--;
} else {
pointerA++
}
}
}So how do you know when to use what?
Firstly, you can’t think of an optimal solution if you don’t know what solution you’re optimizing. The two-pointer technique is an optimization technique, so unless you’re 101% confident in your solution, I believe, it might not be the best technique to jump into as a naive solution.
My rule of thumb is, if you encounter a problem that has your two-pass-approach-senses tingling, then opt for the two-pass approach first. You can’t go wrong with using it as your naive solution to start, and once you fleshed out your answer, you can analyze your code to determine if you can cut costs.
It also makes excellent talking points during an interview. Remember, interviews are about assessing your problem-solving skills, not about how quickly you can conjure up an optimal solution.
You can show off your skills talking about:
- Worst-case time and space complexity
- Discussing why the two-pass approach is efficient or inefficient
- Discussing ways to cut costs in your naive solution
- Discussing how the two-pointer technique could be implemented and possibly pseudo-code a solution.
As an interviewer, I would be much more impressed by a person who gave me a detailed, thorough analysis of a solution than someone who gave me an optimal solution right off the bat. So, never be afraid or ashamed to opt for a naive solution, like the two-pass approach first.
You cannot go wrong with understanding both approaches. During your practice, I highly suggest solving problems using both and do a thorough analysis of both, as if you were in an interview. You’ll become a sharper problem solver and build those critical communication skills necessary for interacting with your future team.
Happy coding!
