All problems

Closest Pair Sum

Medium · two pointers

You are given two lists of integers, a and b, each sorted from smallest to largest (equal values may sit next to each other), and an integer target.

Pick exactly one value from a and exactly one value from b, and add them. Return the sum that is closest to target, meaning the one with the smallest value of |sum - target|.

If two different sums are equally close (one below the target and one above it), return the smaller sum. If a sum equals target exactly, return it.

Both lists have at least one value, so a valid pair always exists.

Examples

Example 1

Input: a = [-3, 0, 5], b = [1, 6], target = 7

Output: 6

The possible sums are -2, 3, 1, 6, 6 and 11. The sum 6 is only 1 away from 7, which is the closest.

Example 2

Input: a = [1, 4, 8], b = [2, 3, 9], target = 12

Output: 11

Both 11 (= 8 + 3) and 13 (= 4 + 9) are 1 away from 12, so the smaller one is returned.

Example 3

Input: a = [2, 5], b = [3, 4], target = 9

Output: 9

5 + 4 hits the target exactly.

Constraints