Two-pointer pair search in Python
Start pointers at both ends and move the one that makes the sum too small or too large; runs in O(n).
- File
two_pointer_pair_search.py, 53 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/two-pointer-pair-search/. The authors are listed in prov/XYYCS4.jsonl.
from typing import Optional
def two_pointer_pair_search(a: list[int], t: int) -> Optional[tuple[int, int]]:
"""Return (i, j) with i < j and a[i] + a[j] == t, or None if no such pair exists.
Precondition: a is sorted in non-decreasing order.
Cost: at most len(a) - 1 iterations, O(n) time and O(1) extra space.
"""
lo, hi = 0, len(a) - 1 # @line L1
while lo < hi: # @line L2
s = a[lo] + a[hi] # @line L3
if s == t: # @line L4
return (lo, hi)
if s < t: # @line L5
lo += 1
else: # @line L6
hi -= 1
return None # @line L7
def count_pairs_with_sum(a: list[int], t: int) -> int:
"""Return the number of index pairs i < j with a[i] + a[j] == t.
Precondition: a is sorted in non-decreasing order. Cost: O(n) time.
"""
lo, hi = 0, len(a) - 1
count = 0
while lo < hi:
s = a[lo] + a[hi]
if s < t:
lo += 1
elif s > t:
hi -= 1
elif a[lo] == a[hi]:
m = hi - lo + 1
count += m * (m - 1) // 2
break
else:
x, y = a[lo], a[hi]
left = 0
while a[lo] == x:
lo += 1
left += 1
right = 0
while a[hi] == y:
hi -= 1
right += 1
count += left * right
return count
test_two_pointer_pair_search.py 41 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/two-pointer-pair-search/. The authors are listed in prov/XYYCS4.jsonl.
import random
from two_pointer_pair_search import count_pairs_with_sum, two_pointer_pair_search
def test_example() -> None:
a = [1, 3, 4, 6, 8, 11, 14, 17]
assert two_pointer_pair_search(a, 22) == (4, 6)
assert two_pointer_pair_search(a, 24) is None
def test_edges() -> None:
assert two_pointer_pair_search([], 0) is None
assert two_pointer_pair_search([5], 10) is None
assert two_pointer_pair_search([5, 5], 10) == (0, 1)
assert two_pointer_pair_search([1, 3, 5], 10) is None
assert two_pointer_pair_search([1, 4, 6, 9], 5) == (0, 1)
assert two_pointer_pair_search([1, 2, 3, 4], 5) == (0, 3)
assert two_pointer_pair_search([-5, -1, 0, 2, 7], -6) == (0, 1)
big = 2**62
assert two_pointer_pair_search([-big, 0, big], 0) == (0, 2)
def test_against_brute_force() -> None:
rng = random.Random(20261104)
for _ in range(2000):
n = rng.randrange(0, 12)
a = sorted(rng.randrange(-10, 11) for _ in range(n))
t = rng.randrange(-22, 23)
sols = {(i, j) for i in range(n) for j in range(i + 1, n) if a[i] + a[j] == t}
got = two_pointer_pair_search(a, t)
if sols:
assert got is not None
i, j = got
assert 0 <= i < j < n and a[i] + a[j] == t
else:
assert got is None
assert count_pairs_with_sum(a, t) == len(sols)
What the next level needs
- the tests did not run in this build