Pair Sum in a Sorted List

Medium ⏱ 12 min 47% acceptance ★★★★★ 4.8

Given a list items sorted in ascending order and a target sum, write find_pair_sum(items, target) that returns a tuple of the values (a, b) (with a <= b) whose sum equals target, using the two-pointer technique (one pointer from the start, one from the end). If no such pair exists, return None.

Examples

Example 1

Input

items = [1, 2, 4, 7, 11], target = 15

Output

(4, 11)

Explanation

4 + 11 == 15; pointers converge from both ends until the sum matches.

Example 2

Input

items = [1, 2, 3], target = 100

Output

None

Explanation

No pair in the list sums to 100.

Constraints

items is sorted ascending.
0 <= len(items) <= 10^5

Topics

ListsTwo Pointers

Companies

AmazonAdobe

Hints

Hint 1

Start left at index 0 and right at the last index.

Hint 2

If the sum is too small, move left forward; if too large, move right backward.

← Move All Zeros to the End Shallow Copy vs Reference Assignment →

Loading the Python runtime… Run executes your code and shows printed output; Submit checks your function against this problem's examples.