Two Pointers: Opposite Ends & kSum

Put one pointer at the left edge and one at the right edge, then walk them toward each other. At every step a single comparison tells you which pointer to move, so the whole scan is $O(n)$ . It shows up whenever the input is sorted (or can be sorted) and you're searching for a pair, checking a palindrome, or filling a result from the extremes.

The idea#

Sorting puts guaranteed extremes at the edges: the smallest value is on the left and the largest on the right. That's what makes the move rule safe, and it plays out a little differently in each of the three main uses:

Target sum. If nums[i] + nums[j] is too small, no partner of nums[i] to the left of j can help, so move i right. Too big, move j left. Each move throws away a whole row of pairs you'd otherwise check.
Palindrome. Characters match: move both inward. Mismatch: return false, or (if one deletion is allowed) try both skips.
Merge from the ends. Compare the two edges, take the better one, and fill the result from the back or front.

All three share one question behind every move: "with the data sorted, could any pair I'm skipping be better?" If the sorted order guarantees the extremes sit at the ends, you can argue that no pair you skipped could have been the answer.

How to spot it#

The clue in the problem usually names the pattern directly. Here's what to look for and how the scan adapts:

Clue	What to do
Sorted array + pair or target sum	Opposite ends, move by comparison
"Is it a palindrome?"	Compare the ends, move inward
Triplets or quadruplets summing to a target	Fix the outer elements, two-pointer the rest
Count pairs or triples under a bound	Opposite ends, add a whole range at once
Largest value could be at either end (squares, parabola)	Fill the result from the back
Pairing smallest with largest under a limit	Sort + greedy pairing (see Sort, Then Place or Pair)

Template#

The base shape is a pair search on sorted input. One comparison per step moves exactly one pointer.

sort items (carry original indices if you need them)
lo = 0, hi = n - 1
while lo < hi:
    value = combine(items[lo], items[hi])
    if value is too small:
        lo += 1                  # no partner left of hi can help items[lo]
    else if value is too big:
        hi -= 1
    else:
        record the pair
        lo += 1, hi -= 1         # then skip repeats if tuples must be unique

kSum: recurse down to the pair scan#

The pair scan finds two numbers. For triplets and larger tuples, peel off one element at a time until two are left, then run the pair scan above. The average-bound check prunes branches early: if target / k is outside the range of the remaining items, no k of them can add up to target.

k_sum(sorted items, target, k):
    if items is empty: return nothing
    avg = target // k
    if avg < smallest item or avg > largest item:
        return nothing           # every pick lies between the extremes
    if k == 2: return pair scan on items for target
    for each index i:
        if items[i] equals items[i - 1]: skip   # same first pick, same tuples
        for each tuple in k_sum(items after i, target - items[i], k - 1):
            record items[i] + tuple

3Sum is the k = 3 case: fix i, then run the pair scan on everything to its right. Each level adds a factor of n, so kSum costs $O(n^{k-1})$ .

Pitfalls#

These are the mistakes that most often cost a correct answer.

Duplicates. When the answer needs unique tuples, skip a fixed element when nums[i] == nums[i - 1], and after a hit skip repeated values on the inner pointers too.
i < j vs i <= j. Use < when the same element can't be used twice (pair sums), and <= when the middle element still needs processing (filling a result array).
Forgetting to sort. The move rule is only valid on sorted data. If the problem needs original indices, carry them along with the values.
Palindrome skipping. When skipping non-alphanumeric characters, use inner while loops guarded by i < j. Skipping once and then comparing can read past the bounds.

Once the pitfalls above feel routine, two related problems are good practice.

Worth exploring: Container With Most Water (LC 11, always move the shorter wall) and the $O(1)$ -space two-pointer version of Trapping Rain Water (LC 42). They are the natural next step after this pattern.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first three.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Two Sum II

This is the pair scan with no twist. The array is already sorted, and the answer uses 1-based indices.

Hint: Valid Palindrome II

At the first mismatch you have exactly two choices: skip the left character or skip the right one. If either remaining range is a palindrome, the answer is true.

Hint: 3Sum

Sort, fix i, and run the pair scan on everything to its right with target -nums[i]. Skip a fixed value equal to the previous one, and skip repeated values on the inner pointers after a hit.

Hint: 3Sum Closest

Use the same scan and the same move rule. At every step, compare abs(total - target) against the best so far.

Hint: 4Sum

Call the kSum recursion with k = 4 on the sorted array. Skip duplicate picks at every level.

Hint: 3Sum Smaller

Fix i. If nums[i] + nums[j] + nums[k] < target, every k' between j and k also works, so add k - j and move j. Otherwise move k down.

Hint: Valid Triangle Number

Once the sides are sorted a <= b <= c, a + b > c is the only check you need; the other two inequalities hold automatically. Fix c as the largest side. If nums[i] + nums[j] > c, every i' in [i, j) works, so add j - i and move j down.

Hint: Squares of a Sorted Array

The largest square sits at one of the two ends. Compare the ends and write the result from the back.

Hint: Sort Transformed Array

This generalizes the squares problem. With a >= 0 the parabola opens upward and the ends hold the largest values, so fill from the back. With a < 0 it opens downward, the ends hold the smallest values, and you fill from the front.

Hint: 4Sum II

Four separate arrays mean sorting lines nothing up, so hash instead. Store every pair sum from the first two arrays in a map, then look up -(c + d) for every pair from the other two. That turns $O(n^4)$ into $O(n^2)$ .

Hint: Container With Most Water

Start with the widest pair. The shorter wall caps the area, so moving the taller one can never help. Always move the shorter side inward and keep the best area.

Hint: Valid Palindrome

Skip non-alphanumeric characters from both ends with str.isalnum() and compare lowercase letters as the pointers meet. You don't need to build a cleaned copy first.

Key takeaways#

Sorting puts guaranteed extremes at the edges, and that is what makes "move the left if too small, the right if too big" correct.
kSum is recursion down to a two-pointer base case; skip duplicate picks at every level.
Counting problems add a whole range (k - j) per success instead of enumerating it.
At a palindrome mismatch with one deletion allowed, try both skips.
If the input can't be sorted usefully, hash the complement instead.

Core idea#

Start one pointer at each end of a sorted array and walk them toward each other. One comparison per step decides which pointer moves, so the scan is $O(n)$ .

Key points#

Sorting puts guaranteed extremes at the edges. That makes the move rule safe.
Sum too small: move the left pointer right. Too big: move the right pointer left.
Each move discards a whole row of pairs that cannot be the answer.
3Sum: fix i, then two-pointer the part to its right. kSum recurses down to the two-pointer case.
Counting: one success settles a range. Add k - j (3Sum Smaller) or j - i (Valid Triangle Number).
Valid Palindrome II: at the first mismatch, try skipping the left and the right character.
Unsorted separate arrays (4Sum II): hash pair sums and look up -(c + d).

Spot it#

Clue	What to do
Sorted array + pair or target sum	Opposite ends, move by comparison
"Is it a palindrome?"	Compare the ends, move inward
Triplets or quadruplets to a target	Fix the outer elements, two-pointer the rest
Largest value at either end (squares, parabola)	Fill the result from the back

Template#

sort items
lo = 0, hi = n - 1
while lo < hi:
    value = combine(items[lo], items[hi])
    if value is too small: lo += 1
    else if value is too big: hi -= 1
    else:
        record the pair
        lo += 1, hi -= 1         # skip repeats if tuples must be unique

For 3Sum, fix each i (skip repeats) and run this scan on the part to its right.

Pitfalls#

Duplicates. Skip a fixed element equal to the previous one, and skip repeats on the inner pointers.
i < j vs i <= j. Use < when an element cannot be used twice; <= when the middle still needs processing.
Forgetting to sort. Carry original indices with the values if you need them.
Palindrome skipping. Use inner while loops guarded by i < j.

Say it in an interview#

"Sorting puts the extremes at the ends, so each move rules out only pairs that cannot be the answer."
"kSum is recursion down to a two-pointer base case, with duplicate skips at each level."