Two Pointer Algorithms: Sliding Window
What are two pointer algorithms, and how can we use them?
I’m glad I get to write you again, thanks to everyone who subscribed last week, you kept my head spinning.
I spent this week thinking of an interesting example for two pointer algorithms and it was quite the journey. And now, I will proceed to explain what two pointer algorithms are, and in particular, the sliding window technique as I would to a five year old.
Two Pointer Algorithms
“Two heads are better than one” is an adage as old as time itself. If you’ve not heard of it before, now you have, if you had before, then there’s another adage you should know; “no knowledge is a waste”. Two pointer algorithms believe that two are better than one if they act as one.
So what does this mean?
Say this house has 20 rooms. If I lost my phone and asked you to help me find it, you’d have to go to each room yourself in search of my phone. This can take you anything from a few minutes to a few years depending on where I placed my phone. However, if you had a friend to help you, you would cut down the search time by half. You can start from room 1, while your friend starts from room 20. When you meet your friend in room 10, you should have found the phone or come to conclude that the phone isn’t in the house. We can see how it is faster if you and your friend go searching rather than going by yourself.
A good example of an applicable problem for two pointer algorithm is reversing the vowels in a string. Two pointer algorithm can also be used to solve the famous two sum problem (if the array is sorted).
The sliding window is a two pointer algorithm that maintains the two pointers (you and your friend) at a specific distance (say room 1 and room 3), and moves you across the house one step(room) at a time. In this example (my missing phone), it makes no logical sense to have you and your friend in room 1 and 3, then have you progress through the house one room at a time but we will deal with that in a moment.
I have found my phone.
As a reward for finding my phone, I have placed bags of candies in every room. You and your friend can go through every room but can only pick candies from three consecutive rooms. As a five year old, I do not need to remind you that your goal is to get as many candies as possible. I felt the need to remind you because those with vivid imagination (like myself) would start picking fancy candies.
Take a minute and think about this. You and your friend can only pick candies from three consecutive rooms, how would you agree when to pick the candies and from which rooms?
I’ll give you a minute. Think about it.
Alright. That was exciting. I hope.
The Sliding Window technique suggests that you and your friend start from room one, your friend then runs through room 2 and 3, notes the candies in those rooms and keeps count of them. When he gets to room 4, he asks you to move to room 2. At every point, your friend keeps a count of all the candies between yourself and him/her. When your friend gets to room 20, you should be in room 17. Your friend then screams to you, let’s go get the candies from room 11 to 13!
In good faith, we run to room 11 through 13, pick up our candies and go our merry way. You found my phone, and you got yourself tons of candy. I can’t think of a better way to start a week.
Two pointer algorithms optimises runtime/performance by utilising some sort of order on the data.
The order, as show in the example above, is not always a sorting order.
A popular example of a two pointer algorithm being used is in binary search. Below are other resources to learn and practice two pointer algorithms.
Thank you so much for reading. I hope at this point you are comfortable with the idea of two pointers and you have an idea of where it is applicable.
Read. Share. Subscribe.