Two-Pointer Technique: Opposite Ends

1. The Opposite-Ends Two-Pointer Pattern

In the previous lesson, both our pointers moved in the same direction but at different speeds. In this pattern, we initialize two pointers, one at the very beginning of an array (left) and one at the very end (right), and then systematically move them inward.

This approach is particularly powerful when dealing with sorted arrays, as the sorted nature of the data allows us to make intelligent decisions about which pointer to move, drastically improving efficiency over a brute-force approach.

Let's start with the canonical problem for this pattern.

2. The Foundation: Two Sum on a Sorted Array

The problem Two Sum II - Input Array Is Sorted (LeetCode 167) is a perfect introduction.

Problem: Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.

A brute-force solution would use nested loops to check every pair of numbers, resulting in an O(n²) time complexity. We can do much better.

By placing one pointer at the start (left) and one at the end (right), we can check the sum of the elements at these pointers. Because the array is sorted, we can use the result of this sum to make a decisive move:

• If current_sum < target, we need a larger sum. The only way to guarantee a larger sum is to move the left pointer to the right.
• If current_sum > target, we need a smaller sum. The only way to guarantee a smaller sum is to move the right pointer to the left.
• If current_sum == target, we have found our pair.

This process continues until the pointers meet or cross, having checked all potential pairs in a single O(n) pass.

To see this in action, please study the following resource.

3. Scaling Up: The 3Sum Problem

Now let's tackle a more complex problem, 3Sum (LeetCode 15), which is a staple of FAANG interviews.

Problem: Given an integer array nums, return all the unique triplets [nums[i], nums[j], nums[k]] such that nums[i] + nums[j] + nums[k] == 0.

The key insight for 3Sum is to reduce it to the 2Sum II problem we just solved. Here's how:

1. Sort the array: This is a mandatory first step. It costs O(n log n) but enables the efficient two-pointer approach and simplifies duplicate handling.
2. Iterate through the array: Use a loop to fix one number, let's call it a (from nums[i]).
3. Solve 2Sum II: For the remainder of the array (from index i+1 to the end), find two numbers (b and c) that sum up to -a. This is exactly the 2Sum II problem with target = -a.

The main challenge in 3Sum is handling duplicates to ensure the solution set is unique. Sorting is a huge help here. If we encounter the same number multiple times in our main loop, we can simply skip it to avoid generating duplicate triplets.

The following video provides an excellent, detailed walkthrough of the entire process, including the crucial logic for skipping duplicates.

Mastering the 3Sum pattern is a significant step. It combines sorting, the two-pointer technique, and careful duplicate handling—all essential skills for coding interviews.

4. A Different Logic: Container with Most Water

Let's look at one more problem that uses the opposite-ends pointer setup but applies a different logic for moving them: Container with Most Water (LeetCode 11).

Problem: You are given an integer array height of length n. Find two lines that, together with the x-axis, form a container that can hold the most water.

The area of water a container can hold is determined by its width and the height of its shorter side.
Area = width * min(height[left], height[right])

We start with pointers at the widest possible configuration (left = 0, right = n-1). To find a potentially larger area, we must shrink the container by moving one of the pointers inward. Which one?

• If we move the pointer at the taller wall, our width decreases, and the new height will either be the same or smaller (it's still limited by the shorter wall). The area can only decrease.
• If we move the pointer at the shorter wall, our width decreases, but we have a chance of finding a new, much taller wall that could create a larger area, compensating for the reduced width.

This greedy choice—always moving the pointer of the shorter wall—is the key to solving this problem in O(n) time.

The following image provides a great visual breakdown of this logic.

For a code implementation that matches this logic, you can refer back to the dev.to article.

Conclusion

In this lesson, we dissected the powerful "opposite-ends" two-pointer pattern. This is a must-know technique for your LeetCode toolkit.

Key Takeaways:

• The Opposite-Ends Two-Pointer pattern is ideal for problems involving pairs or triplets in sorted arrays.
• For sum-based problems (2Sum II, 3Sum), you move pointers based on whether the current_sum is smaller or larger than the target.
• For optimization problems (Container with Most Water), you make a greedy choice at each step about which pointer to move to prune the search space effectively.
• This pattern consistently reduces time complexity from O(n²) or O(n³) to O(n log n) (dominated by sorting) or O(n) (if the array is already sorted).

Preview of the Next Lesson:
We will continue building on the two-pointer theme by exploring how it can be used to partition arrays. We will specifically look at the famous Dutch National Flag problem, which uses a three-pointer variation to sort an array of three unique elements in a single pass. See you then