Converging Pointers: Pair and Triple Sum

The Setup: Two Sum on a Sorted Array

Consider LeetCode 167: you have a sorted array of integers and a target sum. You need to find two numbers that add up to the target. The classic Two Sum problem is usually solved with a hash map in $O(n)$ time, but when the array is already sorted, there is a more elegant approach that uses $O(1)$ extra space: converging pointers.

The idea is simple. Place one pointer at the very beginning of the array and another at the very end. Compute their sum. If the sum is too small, the only way to make it bigger is to move the left pointer rightward, toward larger values. If the sum is too large, move the right pointer leftward, toward smaller values. If the sum matches the target, you have found your pair.

Let us walk through a concrete example. Given the array [2, 7, 11, 15] with target 9:

• Left = 0 (value 2), Right = 3 (value 15). Sum = 17, which is greater than 9, so move right to index 2.
• Left = 0 (value 2), Right = 2 (value 11). Sum = 13, still too large, so move right to index 1.
• Left = 0 (value 2), Right = 1 (value 7). Sum = 9. That matches the target. Return indices [0, 1].

Here is the code:

def two_sum_sorted(numbers, target):
    lo, hi = 0, len(numbers) - 1
    while lo < hi:
        s = numbers[lo] + numbers[hi]
        if s < target:
            lo += 1
        elif s > target:
            hi -= 1
        else:
            return [lo + 1, hi + 1]  # 1-indexed

Why It Works: You Never Skip a Valid Pair

The correctness of converging pointers is not immediately obvious. Why can we be sure that moving a pointer inward never skips over the answer?

Here is the key insight. Suppose the answer involves indices i and j where i < j. At some point during execution, one of two things is true: either lo <= i and hi >= j, meaning the answer is still "between" our pointers, or we have already found it. When the sum is too small and we increment lo, we know that numbers[lo] + numbers[hi] < target. Since numbers[hi] >= numbers[j] (because hi >= j and the array is sorted), if even numbers[hi] is not enough to make the sum large enough, no index between lo and hi would work with lo either. So it is safe to discard lo. The symmetric argument applies when the sum is too large.

3Sum: The Classic Interview Problem

LeetCode 15 asks you to find all unique triplets in an array that sum to zero. This is one of the most frequently asked interview problems, and the converging pointers technique is at its heart.

The strategy is to reduce 3Sum to Two Sum. Sort the array first. Then iterate through each element, fix it as the first number of the triplet, and run the two-pointer scan on the remaining elements to the right. Since you need nums[i] + nums[lo] + nums[hi] == 0, you are effectively looking for a two-sum target of -nums[i] in the subarray from i+1 to the end.

The tricky part is handling duplicates. If you find a valid triplet and then the next value of lo is the same as the current one, you would produce the same triplet again. So after finding a match, skip over duplicate values for both lo and hi. Similarly, at the outer loop level, skip over duplicate values of nums[i].

Let us trace through [-1, 0, 1, 2, -1, -4]. After sorting, the array becomes [-4, -1, -1, 0, 1, 2].

• i = 0 (value -4): target for two-sum is 4. Scanning from index 1 to 5, no pair sums to 4.
• i = 1 (value -1): target is 1. lo = 2 (value -1), hi = 5 (value 2). Sum = -1 + 2 = 1. Match. Record [-1, -1, 2]. Move lo to 3, hi to 4. Sum = 0 + 1 = 1. Match. Record [-1, 0, 1]. Now lo = 4, hi = 3, inner loop ends.
• i = 2 (value -1): same as nums[1], so skip to avoid duplicate triplets.
• i = 3 and beyond: remaining elements are non-negative, so no triplet can sum to zero.

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

Here is the complete code:

def three_sum(nums):
    nums.sort()
    res = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
    return res

3Sum Closest

For LeetCode 16, instead of finding a triplet that sums to exactly zero, you find the triplet whose sum is closest to a given target. The structure is identical, namely sort, fix one element, two-pointer scan, but instead of checking for equality, you track the closest sum seen so far. Each time you compute a triplet sum, compare abs(s - target) against your current best, and update if it is smaller. Then move the pointers the same way: if the sum is less than the target, move lo right; if greater, move hi left.

4Sum and the kSum Generalization

With LeetCode 18, the pattern extends one level further: fix one element, then run 3Sum on the rest. This gives $O(n^3)$ time. The pattern generalizes recursively. For kSum, fix one element and solve (k-1)Sum on the remaining array. The base case is 2Sum, which you solve with converging pointers in $O(n)$. The total time complexity is $O(n^{k-1})$.

Container With Most Water

Converging pointers are not limited to sum problems. LeetCode 11 demonstrates this: you are given an array of heights and asked for the maximum area of water you can trap between two lines. The area between indices i and j is min(height[i], height[j]) * (j - i).

Start with lo = 0 and hi = n - 1, which gives the widest possible container. Compute the area. Then comes the key decision: which pointer do you move inward?

Move the pointer that points to the shorter line. The reason is greedy: the current area is limited by the shorter side. If you moved the taller side inward, the width decreases and the height cannot increase beyond the shorter side, so the area can only decrease or stay the same. But if you move the shorter side inward, the width decreases by 1, yet you might find a taller line that more than compensates. Moving the shorter side is the only move that has any chance of improving the answer.

def max_area(height):
    lo, hi = 0, len(height) - 1
    best = 0
    while lo < hi:
        area = min(height[lo], height[hi]) * (hi - lo)
        best = max(best, area)
        if height[lo] < height[hi]:
            lo += 1
        else:
            hi -= 1
    return best

Valid Triangle Number

LeetCode 611 puts this to work: you are given an array of side lengths and must count how many triplets form a valid triangle. The triangle inequality says that any two sides must sum to more than the third. If the array is sorted, the only condition you need to check is whether the two smaller sides sum to more than the largest side, since a <= b <= c means a + c > b and b + c > a are always satisfied.

Sort the array. Then iterate backwards, fixing each element as the largest side c. For the remaining elements to its left, use converging pointers: lo = 0 and hi = i - 1. If nums[lo] + nums[hi] > nums[i], then every index from lo to hi - 1 also works with hi (because those values are at least as large as nums[lo]), so add hi - lo to the count and move hi left. Otherwise move lo right.

def triangle_number(nums):
    nums.sort()
    count = 0
    for i in range(len(nums) - 1, 1, -1):
        lo, hi = 0, i - 1
        while lo < hi:
            if nums[lo] + nums[hi] > nums[i]:
                count += hi - lo
                hi -= 1
            else:
                lo += 1
    return count

Boats to Save People

Take LeetCode 881: you have an array of people's weights and a weight limit per boat. Each boat carries at most two people. Find the minimum number of boats.

Sort by weight. Use two pointers from the ends. If the lightest and heaviest person together fit within the limit, pair them and move both pointers inward. If they do not fit, the heaviest person rides alone, so move only the right pointer. Either way, one boat is used per step.

def num_rescue_boats(people, limit):
    people.sort()
    lo, hi = 0, len(people) - 1
    boats = 0
    while lo <= hi:
        if people[lo] + people[hi] <= limit:
            lo += 1
        hi -= 1
        boats += 1
    return boats

Squares of a Sorted Array

LeetCode 977 adds a twist: you are given a sorted array that may contain negative numbers and must return an array of the squares of each number, also in sorted order. The challenge is that negative numbers, once squared, might be larger than the positive numbers on the right.

Use two pointers starting at the two ends of the array. Compare absolute values. Whichever pointer has the larger absolute value produces the next-largest square. Fill the result array from the back, placing the larger square at the current position and moving that pointer inward.

def sorted_squares(nums):
    n = len(nums)
    res = [0] * n
    lo, hi = 0, n - 1
    for i in range(n - 1, -1, -1):
        if abs(nums[lo]) > abs(nums[hi]):
            res[i] = nums[lo] * nums[lo]
            lo += 1
        else:
            res[i] = nums[hi] * nums[hi]
            hi -= 1
    return res

Bag of Tokens

Looking at LeetCode 948, you have tokens with values and a starting amount of power. Playing a token face-up costs its value in power but gains one score. Playing a token face-down costs one score but gains its value in power. Maximize your score.

The greedy strategy is clear once you sort. Use converging pointers. Spend power on the cheapest token (left pointer) to gain score. When you run out of power, sacrifice one score to gain power from the most expensive token (right pointer). Keep going as long as you can still gain score on the left.

def bag_of_tokens_score(tokens, power):
    tokens.sort()
    lo, hi = 0, len(tokens) - 1
    score = best = 0
    while lo <= hi:
        if power >= tokens[lo]:
            power -= tokens[lo]
            lo += 1
            score += 1
            best = max(best, score)
        elif score > 0:
            power += tokens[hi]
            hi -= 1
            score -= 1
        else:
            break
    return best

Max Number of K-Sum Pairs

LeetCode 1679 extends this idea: you are given an array and a target k, and must count the maximum number of pairs whose elements sum to k. Each element can be used at most once.

Sort the array and use converging pointers. If the sum of the two ends equals k, count the pair and move both pointers inward. If the sum is too small, move the left pointer right. If too large, move the right pointer left. This is essentially Two Sum but counting all pairs instead of stopping at the first.

def max_operations(nums, k):
    nums.sort()
    lo, hi = 0, len(nums) - 1
    count = 0
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s < k:
            lo += 1
        elif s > k:
            hi -= 1
        else:
            count += 1
            lo += 1
            hi -= 1
    return count

Complexity Analysis

For Two Sum on a sorted array, the two-pointer scan is $O(n)$ time and $O(1)$ space. If the array is not already sorted, sorting takes $O(n \log n)$.

3Sum runs the $O(n)$ two-pointer scan for each of the $n$ elements, giving $O(n^2)$ overall. 3Sum Closest has the same complexity. 4Sum is $O(n^3)$, and in general kSum is $O(n^{k-1})$.

Container With Most Water is $O(n)$ time and $O(1)$ space, since each step moves one pointer inward and the pointers meet after at most n steps.

Valid Triangle Number follows the same structure as 3Sum, an outer loop with a two-pointer inner loop, so it runs in $O(n^2)$ time after $O(n \log n)$ sorting. Boats to Save People, Squares of a Sorted Array, Bag of Tokens, and Max Number of K-Sum Pairs are all single-pass two-pointer scans after sorting, giving $O(n \log n)$ time dominated by the sort and $O(1)$ extra space (or $O(n)$ for Squares, which builds the output array).

The converging pointers pattern is one of the most versatile tools in the two-pointer family. Once you recognize that a problem involves searching over pairs in a sorted structure, this technique should be one of the first things you reach for.

Recognizing this pattern

You're probably looking at converging pointers when:

• The array is sorted (or sortable without losing the structure of the answer) and you need to find a pair, triple, or k-tuple satisfying a sum or comparison condition.
• The problem asks for $O(1)$ extra space, ruling out a hash map.
• Two pointers walking toward each other can monotonically tighten a predicate, since moving one end always rules out the other for the discarded index.
• The objective depends on both endpoints simultaneously, like min(height[i], height[j]) * (j - i) or a + b + c.

Common templates:

• Sorted two-sum: pointers from both ends, advance based on sum vs target. Example: Two Sum II - Input Array Is Sorted.
• Fix-one-then-two-pointer (kSum): outer loop fixes nums[i], inner converging pointers solve $(k-1)$Sum. Example: 3Sum.
• Greedy width-vs-height: move the limiting pointer to potentially improve a min/max-based objective. Example: Container With Most Water.
• Pair-and-discard counting: sort, then walk inward counting valid pairs in one pass. Example: Boats to Save People.
• Merge-from-the-ends: fill output back-to-front by comparing absolute magnitudes at the two endpoints. Example: Squares of a Sorted Array.