Imagine you have a sorted array and need to find a pair of elements that satisfy some condition - say, two numbers that sum to a target. The brute-force approach checks every pair: pick one element, scan the rest. That is O(n^2). Can we do better?

Yes, and the key insight is monotonicity. In a sorted array, the elements increase from left to right. This creates a powerful property: if you place one pointer at the start and another at the end, the sum of the two pointed-to elements tells you exactly which pointer to move.

• If the sum is too small, the left element is too low. Moving the left pointer rightward increases the sum.
• If the sum is too large, the right element is too high. Moving the right pointer leftward decreases the sum.
• If the sum matches the target, you found your answer.

Each step eliminates at least one candidate position. Since there are n positions total, the algorithm terminates in at most n steps - O(n) time.

Why does this work? Consider the sorted array [1, 3, 5, 7, 9] with target 10. Start with left = 0 (value 1) and right = 4 (value 9). The sum is 10 - found it. But suppose the target were 8. The sum 1 + 9 = 10 is too large, so move right to index 3 (value 7). Now 1 + 7 = 8 - found it. Each decision is forced by the sort order: moving left increases the sum, moving right decreases it. There is no ambiguity.

The general template looks like this:

1def two_pointer_template(arr, target):
2    left, right = 0, len(arr) - 1
3    while left < right:
4        current = arr[left] + arr[right]
5        if current == target:
6            return [left, right]
7        elif current < target:
8            left += 1
9        else:
10            right -= 1
11    return []  # no pair found

This template is the foundation for every problem in this lesson. The variations come from what you compute at each step (sum, area, distance), what you do when you find a match (return immediately, collect results, skip duplicates), and how many pointers you use (two for pair problems, two plus an outer loop for triplet problems).

Why not use a hash map? For unsorted arrays, a hash map solves two-sum in O(n) time and O(n) space. But when the array is already sorted, two pointers achieve O(n) time with O(1) space. No extra data structure needed. If the problem hands you sorted input, two pointers is almost always the right approach.

The classic application of two pointers is Two Sum II: given a sorted array numbers and a target, find two numbers that add up to the target and return their 1-indexed positions. The array is guaranteed to have exactly one solution.

This is a direct application of the template from the previous section. The only twist is 1-indexed output - add 1 to both indices before returning.

1def two_sum(numbers, target):
2    left, right = 0, len(numbers) - 1
3    while left < right:
4        current_sum = numbers[left] + numbers[right]
5        if current_sum == target:
6            return [left + 1, right + 1]
7        elif current_sum < target:
8            left += 1
9        else:
10            right -= 1
11    return []

Let us trace through an example. Given numbers = [2, 7, 11, 15] and target = 9:

Three steps to find the answer in a 4-element array. The brute force would check up to 6 pairs.

Why does the algorithm never skip the correct pair? This is the correctness argument that interviewers care about. Suppose the answer is at indices (i, j) where i \< j. At some point during execution, either left = i or right = j (or both). If left = i and right > j, then numbers[left] + numbers[right] > target (because numbers[right] >= numbers[j] and numbers[left] + numbers[j] = target). So right moves leftward toward j. Similarly, if right = j and left \< i, the sum is too small and left moves toward i. The pointers converge on the answer from both sides.

Edge cases to consider:

• Negative numbers: The array [-3, -1, 0, 2, 4] with target 1 works identically. The sort order guarantees monotonicity regardless of sign.
• Duplicate values: [1, 1, 3, 5] with target 2 returns [1, 2]. The algorithm handles duplicates naturally because it compares sums, not values.
• Minimum array size: The array [-1, 0] with target -1 has left = 0, right = 1, sum = -1, match on the first step.

The time complexity is O(n) because each pointer moves at most n - 1 positions. The space complexity is O(1) - only two integer variables.

The 3Sum problem asks: given an array of integers, find all unique triplets that sum to zero. This is harder than two sum for two reasons - you need to find all solutions (not just one), and you must avoid duplicate triplets.

The key insight is reduction: a 3-element problem reduces to a 2-element problem. Fix one element with an outer loop, then use two pointers on the remaining subarray to find pairs that sum to the negation of the fixed element.

1For each element nums[i]:
2    Find all pairs (nums[left], nums[right]) where
3    nums[left] + nums[right] = -nums[i]
4    using two pointers on nums[i+1 ... n-1]

First, sort the array. This enables two pointers on the inner search and makes duplicate skipping straightforward.

Let us trace through nums = [-1, 0, 1, 2, -1, -4]:

Step 1: Sort. The array becomes [-4, -1, -1, 0, 1, 2].

Step 2: Outer loop, i = 0, nums[i] = -4. Need pairs summing to 4 in [-1, -1, 0, 1, 2]. Left = 1 (value -1), right = 5 (value 2). Sum = -1 + 2 = 1 < 4, move left. Left = 2 (value -1), sum = -1 + 2 = 1 < 4, move left. Left = 3 (value 0), sum = 0 + 2 = 2 < 4, move left. Left = 4 (value 1), sum = 1 + 2 = 3 < 4, move left. Left = 5, left meets right, no pair found.

Step 3: Outer loop, i = 1, nums[i] = -1. Need pairs summing to 1 in [-1, 0, 1, 2]. Left = 2 (value -1), right = 5 (value 2). Sum = -1 + 2 = 1 = target. Found triplet [-1, -1, 2]. Advance both pointers. Left = 3 (value 0), right = 4 (value 1). Sum = 0 + 1 = 1 = target. Found triplet [-1, 0, 1]. Advance both pointers. Left = 4, right = 3, done.

Step 4: Outer loop, i = 2, nums[i] = -1. Same as i = 1 - skip because nums[2] == nums[1].

Step 5: Outer loop, i = 3, nums[i] = 0. Need pairs summing to 0 in [1, 2]. Sum = 3 > 0, move right. Done, no pair found.

Result: [[-1, -1, 2], [-1, 0, 1]].

Handling duplicates

Duplicate avoidance happens at three points:

1. Outer loop: if nums[i] == nums[i - 1], skip (we already processed this value as the fixed element).
2. Left pointer: after finding a triplet, advance left past all duplicates of nums[left].
3. Right pointer: after finding a triplet, advance right past all duplicates of nums[right].

1def three_sum(nums):
2    nums.sort()
3    result = []
4    for i in range(len(nums) - 2):
5        if i > 0 and nums[i] == nums[i - 1]:
6            continue  # skip duplicate fixed element
7        left, right = i + 1, len(nums) - 1
8        while left < right:
9            total = nums[i] + nums[left] + nums[right]
10            if total == 0:
11                result.append([nums[i], nums[left], nums[right]])
12                while left < right and nums[left] == nums[left + 1]:
13                    left += 1  # skip duplicate left
14                while left < right and nums[right] == nums[right - 1]:
15                    right -= 1  # skip duplicate right
16                left += 1
17                right -= 1
18            elif total < 0:
19                left += 1
20            else:
21                right -= 1
22    return result

Time complexity: Sorting is O(n log n). The outer loop runs n times, and each inner two-pointer scan is O(n). Total: O(n^2). This is optimal - you cannot do better than O(n^2) for 3Sum (this has been proven in theoretical computer science).

Space complexity: O(1) extra space (excluding the output list), since sorting is done in-place and two pointers use constant space.

Generalizing to k-sum

The same reduction applies to 4Sum, 5Sum, or any k-Sum. Fix one element, reduce to (k-1)-Sum. The base case is 2Sum, solved with two pointers. The time complexity is O(n^(k-1)): each level of recursion adds a factor of n from its loop, and the innermost 2Sum is O(n).

This problem uses two pointers in a different way. Instead of finding elements that sum to a target, you are maximizing an area.

Given an array height where height[i] represents a vertical line at position i, find two lines that together with the x-axis form a container that holds the most water. The area between lines at positions l and r is:

area = min(height[l], height[r]) * (r - l)

The water level is limited by the shorter line (water would spill over it), and the width is the distance between the two lines.

The greedy insight: Start with the widest container (left = 0, right = n - 1). At each step, move the pointer pointing to the shorter line inward. Why? Because the area is constrained by the shorter line. If you move the taller line inward, the width decreases and the height cannot increase beyond the shorter line - so the area can only decrease or stay the same. But if you move the shorter line inward, the width decreases but the height might increase enough to compensate, potentially yielding a larger area.

Let us prove this more carefully. Suppose height[l] \< height[r]. The current area is height[l] * (r - l). If we move r leftward to r - 1:

• Width decreases to r - l - 1
• New height is min(height[l], height[r-1]), which is at most height[l] (since height[l] is the shorter side)
• New area is at most height[l] * (r - l - 1), which is strictly less than height[l] * (r - l)

So keeping the shorter line and moving the taller line can never improve the area. The shorter line is the bottleneck. The only hope for improvement is replacing the shorter line with a potentially taller one.

1def max_area(height):
2    left, right = 0, len(height) - 1
3    best = 0
4    while left < right:
5        width = right - left
6        h = min(height[left], height[right])
7        best = max(best, h * width)
8        if height[left] < height[right]:
9            left += 1
10        else:
11            right -= 1
12    return best

Trace through height = [1, 8, 6, 2, 5, 4, 8, 3, 7]:

The maximum area is 49, formed by lines at indices 1 (height 8) and 8 (height 7).

Time complexity: O(n) - each step moves one pointer, total moves bounded by n.

Space complexity: O(1) - just three variables (left, right, best).

What if both heights are equal? When height[left] == height[right], moving either pointer is valid. Neither side can improve the area with the current opposing line, so both are equally "bottlenecked." The algorithm moves one arbitrarily (in the code above, it moves right). The correctness proof still holds: the optimal pair will be found regardless of which direction you choose when heights are tied.

Practice