You've seen how the two-pointer technique can efficiently solve problems on sorted arrays and strings. Now, let's apply this powerful pattern to more complex scenarios. We'll break down three classic problems that might seem daunting at first but become manageable with a clever two-pointer strategy.

The challenge is to find all unique triplets in an array of integers that add up to zero. For example, in the array [-1, 0, 1, 2, -1, -4], the triplets [-1, -1, 2] and [-1, 0, 1] both sum to zero.

A brute-force approach would use three nested loops to check every possible combination of three numbers. This works, but it's slow, with a time complexity of $O(n^3)$. We can do much better.

The key is to transform the problem into something we already know how to solve. If we sort the array first, we can iterate through it with one pointer, and for each element, use a two-pointer approach to find the other two numbers. It turns a Three-Sum problem into a series of Two-Sum problems.

Here's the strategy:

1. Sort the array. This is crucial and allows us to use the two-pointer search.
2. Loop through the array with a single index, let's call it i. The value nums[i] will be the first number in our potential triplet.
3. For each nums[i], set up two more pointers: left at i + 1 and right at the end of the array.
4. Our target sum for the pair is now -nums[i]. We look for nums[left] + nums[right] == -nums[i].

• If the sum is too small, we need a larger number, so we increment left.
• If the sum is too large, we need a smaller number, so we decrement right.
• If we find a match, we've found a triplet! We add it to our results.

To avoid duplicate triplets, we need to be careful. After finding a valid triplet, we must advance our left and right pointers past any identical adjacent elements. Similarly, in our main loop, if we encounter an element nums[i] that's the same as the previous one, we skip it.

The time complexity is dominated by the sorting step and the nested loop structure. Sorting takes $O(n \log n)$. The main loop runs about $n$ times, and the inner two-pointer loop runs in $O(n)$ time. This gives us a total time complexity of $O(n \log n + n^2)$, which simplifies to $O(n^2)$. This is a significant improvement over the $O(n^3)$ brute-force method. The space complexity is $O(1)$ if we don't count the space for the output, as we modify the array in-place.

Imagine an array of non-negative integers where each number represents the height of a vertical line. The problem is to find two lines that, together with the x-axis, form a container that can hold the most water. The width of the container is the distance between the lines, and the height is limited by the shorter of the two lines.

The two-pointer approach is perfect here. We'll place one pointer at the beginning (left) and one at the end (right) of the heights array. These two lines form our initial container. We calculate its area and then try to find a better one.

How do we move the pointers? The container's width is right - left. To potentially increase the area, we need a greater height, as the width will only decrease. The height is constrained by the shorter of the two lines. If we move the pointer pointing to the taller line, the new height will either be the same or shorter, and the width will be smaller. This cannot result in a larger area.

Therefore, we should always move the pointer that points to the shorter line inward. This gives us a chance of finding a taller line that could compensate for the reduced width.

Since we traverse the array with two pointers that only move towards each other, each element is visited at most once. This gives us a time complexity of $O(n)$. The space complexity is $O(1)$ because we only use a few variables to store the pointers and the maximum area.

This is another classic problem. Given an array of non-negative integers representing an elevation map, how much rainwater can be trapped between the bars after it rains?

The amount of water trapped above any given bar depends on the height of the tallest bars to its left and its right. Specifically, the water level above a bar is min(max_left, max_right) - current_height. If this value is negative, no water is trapped.

A straightforward solution involves iterating through each bar, then finding the max height on its left and right sides. This would be an $O(n^2)$ solution. We can optimize this by pre-calculating the maximum heights to the left and right of every position in two separate arrays, which brings the time complexity down to $O(n)$ but uses $O(n)$ space.

Can we do even better and solve it in $O(1)$ space? Yes, with two pointers.

We start with a pointer at each end: left and right. We also maintain two variables, left_max and right_max, which track the maximum height seen so far from the left and right ends, respectively.

At each step, we compare the heights at the left and right pointers. If height[left] is less than height[right], it means the water level at the left pointer is determined by left_max. Why? Because we know there's a bar to the right (height[right]) that is at least as tall. So, the water trapped at height[left] is left_max - height[left]. After calculating, we move left one step to the right.

Conversely, if height[right] is less than or equal to height[left], the water level at the right pointer is determined by right_max. We calculate the trapped water as right_max - height[right] and move right one step to the left.

This two-pointer approach processes each element once, giving it a time complexity of $O(n)$. And since we only use a handful of variables to keep track of our state, the space complexity is a highly efficient $O(1)$. This solution showcases the power of two pointers to solve complex problems with optimal space usage.

These problems demonstrate that with a bit of creative thinking, the two-pointer technique can be adapted to solve a wide range of challenges far beyond simple pair-finding.