This is the start of my data structures and algorithms (DSA) blog! Every week I’ll be picking a DSA problem and walking through how to upgrade your algos from brute force to efficient solutions. Follow me to keep up with my weekly posts!
What is the 2-Pointer Technique?
It’s one of the most common algorithm solving techniques that uses — as the name implies — 2 pointers to keep track of the two positions in an array/list. As you’ll see in the examples, this can turn many O(n²) solutions into O(n), one-pass solutions.
Common uses
- Comparing elements at opposite ends of an array
- Maintain a subsequence/window of element
This week I’ll be taking a look at the first common use but you can find links to other problems that use the 2-pointers technique at the end.
Container With Most Water
Link to the detailed problem description on LeetCode
Problem
Given an array, arr, of n non-negative integers where each element, arr[i] represents the height of a wall at position i. Find the two positions where when using the walls at those positions, can hold the most water.
Brute Force
We can check every pair of positions and compute the amount of water that pair can hold. After we find the amount, we compare it to the largest amount we’ve have found so far.
This solution requires O(n²) time and O(1) space.
How to Optimize?
We ask ourselves what is repeated/unnecessary work that we are doing in our brute force solution?
Well we know that the amount of water two walls can hold is constrained by the smaller wall — ex) If arr[0] = 5 and arr[2] = 4, the walls can hold 2*4=8 units of water. That means in order to find a greater pair of walls, we need to replace the smaller wall. This should help us reduce the number of pairs we check. Ok, that’s intuition #1.
You might ask yourself, but the width is changing too, how can we account for that while changing the positions of the walls?
Great question. We know that the maximum width is when we use the first and last wall so as we check more walls in between, the width will decrease. That’s intuition #2.
Let’s combine those 2 intuitions: So if we started at the maximum possible width (#2) and replaced the lower wall each time in search of a higher wall (#1), we will be finding the maximum water contained for each lower constraining wall. That might sound confusing but take a look at this example:
arr = [5,1,7,6,10]If we start at the first and last position:wall_first = 5
wall_last = 10
width = 4So here we have a width of 4, constrained by height 5 which gives us a total of 20.Now let's replace the lower wall.wall_first = 1
wall_last = 10
width = 3This gives us a total of 3 which isn't the new max.What if we swapped the other way?wall_first = 5
wall_last = 6
width = 3Here we have a width of 3, constrained by the same height of 5. We know this will never result in a new total because we kept our constraining value the same and only reduced the width.
I hope that example helped show why this process works.
At this point, you should be thinking about how we keep track of those two positions — that’s where the 2-pointer technique comes in. Check it out in code:
Notice how we initialize our 2-pointers at the ends of the array and then either increment our left pointer or decrement our right pointer at each iteration.
This solution requires O(n) time and O(1) space because we check every wall once!
Conclusion
Adding the 2-pointer technique to your algorithms repertoire will help make your solutions much more efficient.
If you want more practice, try some of these: