Two-Pointer vs Sliding window
The two-pointer algorithm is an excellent technique for working with pairs, separating data, finding ranges (or subsequences) in sequences, or even finding a cycle in a linked list.
The Sliding window uses one pointer and one variable for the window size to find a window within the sequence.
Two-Pointer
Two-pointer technics consist in comparing values at the two pointers. The most famous usages are the “Fast/Slow” and the “Start/End” pointers technics.
Fast/Slow
Linked Lists are composed of nodes pointing to other nodes, which could end up with a node in the list pointing to another node present earlier in the list, leading to a circle (never able to reach the end).
And the technic to discover this kind of circle is the fast-slow pointers. We have two pointers at the head of the list and move the slow pointer by one node and the fast by two nodes; if they reach the end (one node pointing to nil), there is no circle; if they meet, there is a circle.
Here is the code:
As you can see, it’s straightforward, creates two pointers, makes them move at different speeds, and if they meet, bingo!
Start/End
The two-sum is an easy and famous interview question (you will see it in a later article), where you need to find the presence of 2 elements (a pair) in the integer array in which the sum is equal to a target. For this two-pointer algorithm, let’s focus only on a sorted array.
Here is the code:
We start here by initializing the two pointers with the first and last index of the array. Then we loop until the pointers meet (there is no such pair). For each run loop, we calculate the sum of the two values of our pointers; if the sum is equal to the target, bingo, we find the pair. Otherwise, if the sum is lower than the target, we increment the start index; if the sum is greater than the target, we decrement the end index.
As you can see, there are three things to think about when we are making any two pointers algorithms:
- starting point: where pointers 1 and 2 should be located, both in the beginning? Both at the end? One on each edge? Middle?
- speed: are the two pointers moving at the same rate? One faster? Moving only one pointer at a time?
- stop conditions: when to stop the algorithm? Met each other? Reached an edge? Found a targeted value? Looped through the array again?
If you want another variation, have a look at the “The Dutch national flag” (you will see it in a later article) problem (tip: you will need three-pointers, but the logic is the same).
Sliding window
The sliding window technic is used to check some subparts of a sequence. For this, we need only one pointer that shows the start of the subpart and an integer that indicates the size of the subpart (window). There are two variants, one with fixed window size and one with a flexible one.
Fixed window size
The fixed-sized window is more straightforward, as the main idea is that at each run of the loop, we add a new element and remove one.
Let’s see with the most famous example, “find the max sum of K consecutive integers within the array” (window size K is fixed).
Here is the code:
First, we check that the array is larger than the expected window, or we return nil. Then we create the first window with the first K number. Then we iterate from K to the end of the array; if the current sum exceeds the max sum, we set the max sum with the current max value. Finally, we return the max value.
Very easy, we create the first window, add the next number, and remove the one outside the new window.
Flexible window size
The flexible-sized window is a bit more complicated because we need two logics, the first is when to update the size of the window, and the second is when to update the pointer to a new location.
Let’s see with the most famous example, “find the max sum of consecutive integers within the array” (There is no size limit K for the window, and it can have negative numbers).
Here is the code:
First, we check that the array is not empty, or we sent 0 as the max sum. Secondly, we declare two variables, max sum and current sum (set with 0). Third, we iterate through each number.
If the current number is negative, there is nothing we can do, then we add it to the current sum and continue. If the current number is positive, there are two options; if the current sum is negative, we replace the current sum with the current number; if positive, we add it to the current sum. Then we check if the current sum is greater than the max sum; if so, we replace it. Eventually, we return the max sum.
As you see, it is straightforward; you need to provide the two conditions where you expand the window and when you move the window.
Comparaison
As you see, both two-pointers and sliding-window are both simple, similar, and even related. They bring time complexity from O(n2) to O(n). The sliding window can be done with two pointers or one pointer and one size.
