Mastering Problem Solving: Two Pointers Technique

7 min readApr 4, 2024

The two-pointer technique is a widely used approach to solving problems efficiently, particularly scenarios involving arrays or linked lists. This method is highly efficient when traversing arrays or lists with two pointers moving at different speeds or in different directions.

In this blog post, we’ll dive into the concept, discuss how it works, demonstrate its application with examples, and solve a LeetCode problem to solidify our understanding.

Let’s start.

The Concept

The Two Pointers Technique is a method that involves using two pointers to traverse through an array. This technique is often used to solve problems more efficiently than using a single pointer or nested loops. Typically, the pointers traverse the array from both ends or at different speeds.

The technique is commonly used to find a solution that satisfies certain conditions or constraints. For example, it can be used to find pairs in a sorted array that add up to a specific target.

How does it work?

The key idea behind the Two Pointers Technique is to manipulate the pointers based on certain conditions, usually moving them closer to each other or adjusting their positions based on the problem’s requirements. By doing so, you can effectively reduce the time complexity of your solution.

Let’s illustrate the concept with a simple example.

Consider a scenario where we have a sorted array and want to find a pair of elements that sum up to a specific target.

Array: [2, 4, 6, 8, 10]
Target Sum: 12

We initialize two pointers, one at the beginning (left) and another at the end (right) of the array:

Compare Sum with Target: Calculate the sum of the elements at the positions indicated by the pointers (left and right). In this case, the sum is 2 + 10 = 12.
Check Sum against Target:

If the sum equals the target, we have found the pair (2, 10) that sums up the target, and we return it.
If the sum is less than the target, we need to increase the sum, so we move the left pointer to the right.
If the sum is greater than the target, we need to decrease the sum, so we move the right pointer to the left.

Let’s say we move the left pointer:

Now, we recalculate the sum: 4 + 10 = 14, which is greater than the target. So, we move the right pointer to the left:

Now, we recalculate the sum: 4 + 8 = 12, which is equal to the target. Hence, we found the pair (4, 8) that sums up the target.

After comparing with the target sum, the pointers are adjusted until the desired solution is reached.

11. Container With Most Water

Let’s demonstrate what is explained with a LeetCode example.

The Question

You are given an integer array height of length n. There are n vertical lines are drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented 
by array [1,8,6,2,5,4,8,3,7]. 
In this case, the max area of water (blue section) 
the container can contain is 49.

The Approach

I will explain the solution that first came to my mind. This solution is accepted but it is not the best practice to solve this problem. Remember, during an interview, we are expected to be able to solve the questions given, even if our solutions are not exactly optimal. The important thing is that you can come up with a solution even if it is brut-force but at the same time, you can think of ways that can improve your method.

Let’s dive in.

We will initialize two pointers to represent the beginning and end of the heights array. Additionally, we will create an array to hold the maximum areas calculated after each pointer movement.
We will enter a while loop that continues until end pointer crosses or equals start pointer.
While iterating through the loop, we will compare the heights of the positions indicated by the pointers.
We will calculate the width between the two pointers and the minimum height of the two lines. Using these values, we can calculate the container’s area formed by these two lines.
If the height of the line marked by the end pointer is higher, it means moving the start pointer towards the end pointer might result in a larger area. So, we move the start pointer one step to the right.
If the height of the line marked by the start pointer is higher or equal to the height of the line marked by the end pointer, we can move the end pointer one step to the left.
After determining which pointer to move, we calculate the area formed by the lines marked by the start and end pointers at their current positions. Then, we store this calculated area in our list of areas and ultimately return the maximum among those values.

Now that we have a clear plan to solve the problem, we can proceed with coding it.

var maxArea = function(height) {
    let start = 0, end = height.length - 1;
    let maxArea = []

    while(end >= start) {

        if(height[start] >= height[end]) {
            maxArea.push((end - start) * height[end])
            end--
        } else {
            maxArea.push((end - start) * height[start])
            start++
        }     
    }  
    return Math.max(...maxArea)
};

Space and Time Complexity

Time Complexity

The while loop iterates through the array from both ends toward the center, and it continues until the start pointer surpasses the end pointer. In the worst case, both pointers traverse the entire array once, resulting in a linear time complexity, denoted as O(n) due to the linear iteration through the input array.

Space Complexity

In the worst case, the maxArea array could potentially store an area for each pair of heights in the input array. Since the input array could have up to n elements, where n is the size of the input array, the maximum size of the maxArea array would also be n. Therefore, the space complexity contributed by the maxArea array is O(n).

What could have been different?

As we discussed earlier, the solution I shared with you is functional, but there is a more efficient way to solve the problem. Instead of sorting all the calculated areas and then finding the maximum, we can directly update the variable as we go to keep track of the maximum. This approach not only simplifies the code but also reduces the space complexity of our previous solution. By implementing this updated approach, we can improve the performance of our solution and optimize it further.

var maxArea = function(height) {
    let start = 0, end = height.length - 1;
    let maxArea = 0;

    while (end > start) {
        const width = end - start;
        const minHeight = Math.min(height[start], height[end]);
        const area = width * minHeight;
        maxArea = Math.max(maxArea, area);

        if (height[start] < height[end]) {
            start++;
        } else {
            end--;
        }
    }
    return maxArea;
};

In this version, maxArea is directly updated within the loop without the need to store all areas in an array. This improvement makes the solution more efficient and maintains its correctness. Now, the time complexity remains O(n) as before, but the space complexity is reduced to O(1) since we're not storing any additional data structures.

Conclusion

Two Pointers Technique offers a valuable approach to problem-solving. As with any new skill, it’s natural to encounter challenges along the way.

It’s important to look at challenges as opportunities for growth and learning. It’s essential to remember that even seasoned professionals were once beginners. By continuously improving your skills and seeking guidance when necessary, you’ll gradually build your expertise.

Let’s embark on this journey together, fostering a supportive environment where mistakes are welcomed as part of the learning process. With dedication and determination, you’ll soon find yourself confidently navigating through complex problems.

Happy coding, and may your journey be filled with continuous improvement and success!