The Two-Pointer Approach
For the last five months, I have been studying data structures and algorithms and have been putting them to practice by solving coding challenges.
During my studies, I came across the infamous Binary Search algorithm. This is typically solved by creating pointers referencing different items in the list. I call Binary Search my “gateway algorithm” because this opened new doors to understanding how efficient and useful it is to keep track of several items at a time using pointers!
Let’s put it into practice solving a LeetCode problem called “Container With Most Water.” First, let’s tackle it using a Brute Force approach, then see if we can optimize it using the Two-Pointer approach.
Problem Statement:
Example 1:
Example 2:
Constraints:
The Brute Force Implementation
In this case, we are finding the area by comparing every possible pair of heights in the height array and returning the maximum area found.
This is a more intuitive approach however performance wise we see that the Time Complexity is Big O(n²) which isn’t that great. Now for the exciting part — optimizing it!
The Two-Pointer Implementation
The most important part to remember is that we have two pointers starting from the first and last in the array, which maximizes the area obtained because the width is at its widest. During every iteration, we calculate the maximum area and update the pointer with the shortest height to try and maximize the area.
The time complexity here is greatly increased to Big O(n), where n is the length of the given parameter and only requires one single pass. Boom, optimized!
Conclusion
Using a brute force approach can be intuitive and implemented much easier, but the implementation is usually not so efficient. Based on what we learned using pointers we can create a more optimized approach to our algorithm.
