Two Pointers from Both Ends: Pair Sum, Palindrome and Container

24 min · Intermediate

Many problems ask about pairs. Checking every pair is slow. When the data is sorted, or the rule is symmetric, two pointers that start at the two ends and close in solve it in one pass.

Two pointers from both ends

Two pointers is a technique that keeps two positions in a sequence and moves them by a rule, so one pass can replace nested loops. Opposite-end pointers start at the two ends and close in.

A shop has prices sorted low to high and a budget. Is there a pair of prices that adds up to it? Put one pointer at each end and move them toward each other.

A sorted list 3, 8, 12, 19, 25, 40 with target 31. Pointer L starts at 3 and R at 40. Each step compares the sum with 31 and moves one pointer inward, fading the discarded cell, until 12 plus 19 equals 31.

Example 1 · Brute force: try every pair

Python

1def pair_sum_slow(nums, target):2    for i in range(len(nums)):3        for j in range(i + 1, len(nums)):4            if nums[i] + nums[j] == target:5                return i, j6    return None7
8
9print(pair_sum_slow([3, 8, 12, 19, 25, 40], 31))

Output

(2, 3)

What this code does

Two nested loops check every pair, so the time is O(n squared) and the space is O(1).
It is correct but slow for long lists. Sorted order lets two pointers do the same job in O(n).

Example 2 · Two pointers from both ends

Python

1def pair_sum(nums, target):2    left, right = 0, len(nums) - 13    while left < right:4        total = nums[left] + nums[right]5        if total == target:6            return left, right7        if total < target:8            left += 19        else:10            right -= 111    return None12
13
14prices = [3, 8, 12, 19, 25, 40]15print(pair_sum(prices, 31))16print(pair_sum(prices, 5))

Output

(2, 3)
None

What this code does

Each step looks at one pair and moves one pointer, so the loop runs at most n times.
Python lists are zero-based, so len(nums) - 1 is the last index.

Why moving a pointer is safe

If the sum is too big, the right value is too big for every partner still available, because the left value is already the smallest one left. So the right value can go. The same logic works when the sum is too small.

Python

1def count_pairs_below(nums, target):2    left, right = 0, len(nums) - 13    count = 04    while left < right:5        if nums[left] + nums[right] < target:6            count += right - left7            left += 18        else:9            right -= 110    return count11
12
13print(count_pairs_below([1, 3, 5, 7, 9], 10))

Example 3 · Trace the pointers

Python

1prices = [3, 8, 12, 19, 25, 40]2target = 313left, right = 0, len(prices) - 14while left < right:5    total = prices[left] + prices[right]6    print(left, right, total)7    if total == target:8        break9    if total < target:10        left += 111    else:12        right -= 1

Output

What this code does

Printing the pointers each round shows the search closing in.
Five rounds are enough here, while brute force may need up to 15 pair checks.

When a pair is below the target, every pair from left to right - 1 is below it too, so right - left pairs are counted at once.

Valid palindrome

A palindrome reads the same from both ends. Compare the first and last letters, skip anything that is not a letter or digit, and move inward.

Example 4 · Palindrome with a built-in view

Python

1def is_palindrome_short(text):2    clean = [ch.lower() for ch in text if ch.isalnum()]3    return clean == clean[::-1]4
5
6print(is_palindrome_short("A man, a plan, a canal: Panama"))7print(is_palindrome_short("Order 66 #"))

Output

True
False

What this code does

This is the shortest Python version: filter, then compare with the reversed copy.
It builds two extra lists, so space is O(n). Interviews often ask for the two-pointer version with O(1) space.

Example 5 · Palindrome, two pointers

Python

1def is_palindrome(text):2    left, right = 0, len(text) - 13    while left < right:4        if not text[left].isalnum():5            left += 16        elif not text[right].isalnum():7            right -= 18        elif text[left].lower() != text[right].lower():9            return False10        else:11            left += 112            right -= 113    return True14
15
16for message in ["Was it a car or a cat I saw?", "Python"]:17    print(message, is_palindrome(message))

Output

Was it a car or a cat I saw? True
Python False

What this code does

Spaces and punctuation are skipped by moving only one pointer.
The loop stops early on the first mismatch.

Example 6 · Valid palindrome

Python

1def is_palindrome(text):2    left, right = 0, len(text) - 13    while left < right:4        if not text[left].isalnum():5            left += 16        elif not text[right].isalnum():7            right -= 18        elif text[left].lower() != text[right].lower():9            return False10        else:11            left += 112            right -= 113    return True14
15
16print(is_palindrome("A man, a plan, a canal: Panama"))17print(is_palindrome("Order 66 #"))

Output

True
False

What this code does

isalnum() is true for letters and digits.
This uses no copy of the text, so extra space is O(1).

Container with most water

Vertical lines have heights. Two lines and the floor hold water of width times the shorter height. Start with the widest pair and move the shorter line inward, because only a taller line can help.

Python

1def max_water(heights):2    left, right = 0, len(heights) - 13    best = 04    while left < right:5        width = right - left6        best = max(best, width * min(heights[left], heights[right]))7        if heights[left] < heights[right]:8            left += 19        else:10            right -= 111    return best12
13
14print(max_water([1, 8, 6, 2, 5, 4, 8, 3, 7]))

Example 7 · Best container

Python

1def max_water(heights):2    left, right = 0, len(heights) - 13    best = 04    while left < right:5        width = right - left6        best = max(best, width * min(heights[left], heights[right]))7        if heights[left] < heights[right]:8            left += 19        else:10            right -= 111    return best12
13
14print(max_water([4, 3, 2, 1, 4]))

Output

What this code does

The widest pair, the two 4s, is 4 apart: 4 * 4 = 16.
The heights are equal at the start, so the right pointer moves, and no later pair beats 16.

The width always shrinks, so keeping the shorter line can never improve the answer. One pass gives O(n) time and O(1) space.

Next step

Check your understanding

11 quick questions

Two pointers from both ends

Two pointers is a technique that keeps two positions in a sequence and moves them by a rule, so one pass can replace nested loops. Opposite-end pointers start at the two ends and close in.

A shop has prices sorted low to high and a budget. Is there a pair of prices that adds up to it? Put one pointer at each end and move them toward each other.

1def pair_sum_slow(nums, target):2 for i in range(len(nums)):3 for j in range(i + 1, len(nums)):4 if nums[i] + nums[j] == target:5 return i, j6 return None7 8 9print(pair_sum_slow([3, 8, 12, 19, 25, 40], 31))

1def pair_sum(nums, target):2 left, right = 0, len(nums) - 13 while left < right:4 total = nums[left] + nums[right]5 if total == target:6 return left, right7 if total < target:8 left += 19 else:10 right -= 111 return None12 13 14prices = [3, 8, 12, 19, 25, 40]15print(pair_sum(prices, 31))16print(pair_sum(prices, 5))

1def count_pairs_below(nums, target):2 left, right = 0, len(nums) - 13 count = 04 while left < right:5 if nums[left] + nums[right] < target:6 count += right - left7 left += 18 else:9 right -= 110 return count11 12 13print(count_pairs_below([1, 3, 5, 7, 9], 10))

1prices = [3, 8, 12, 19, 25, 40]2target = 313left, right = 0, len(prices) - 14while left < right:5 total = prices[left] + prices[right]6 print(left, right, total)7 if total == target:8 break9 if total < target:10 left += 111 else:12 right -= 1

1def is_palindrome_short(text):2 clean = [ch.lower() for ch in text if ch.isalnum()]3 return clean == clean[::-1]4 5 6print(is_palindrome_short("A man, a plan, a canal: Panama"))7print(is_palindrome_short("Order 66 #"))

1def is_palindrome(text):2 left, right = 0, len(text) - 13 while left < right:4 if not text[left].isalnum():5 left += 16 elif not text[right].isalnum():7 right -= 18 elif text[left].lower() != text[right].lower():9 return False10 else:11 left += 112 right -= 113 return True14 15 16for message in ["Was it a car or a cat I saw?", "Python"]:17 print(message, is_palindrome(message))

1def is_palindrome(text):2 left, right = 0, len(text) - 13 while left < right:4 if not text[left].isalnum():5 left += 16 elif not text[right].isalnum():7 right -= 18 elif text[left].lower() != text[right].lower():9 return False10 else:11 left += 112 right -= 113 return True14 15 16print(is_palindrome("A man, a plan, a canal: Panama"))17print(is_palindrome("Order 66 #"))

1def max_water(heights):2 left, right = 0, len(heights) - 13 best = 04 while left < right:5 width = right - left6 best = max(best, width * min(heights[left], heights[right]))7 if heights[left] < heights[right]:8 left += 19 else:10 right -= 111 return best12 13 14print(max_water([1, 8, 6, 2, 5, 4, 8, 3, 7]))