Arrays and searching 0/120

Lesson 2 of 9

Two pointers

Find pairs in sorted arrays with two pointers that move inward, and prove that each move discards only pairs that cannot be the answer.

3,620 words ยท 17 min read

Part 1 of 10 Two pointers

Find two values with a given sum

A hash map can find two values that add up to a target: for each new value, look up the partner it needs among the values already read, and then store the new value. That works on a list in any order, but it stores an extra entry for every value it reads. When the list is sorted, two indices are enough, one starting at each end of the list and moving toward the other. Let's take a small sorted list and a target of 34:

position   0  1   2   3   4   5numbers    3  8  11  14  20  27

We want two different positions whose values add up to 34. Here they are positions 3 and 4, because 14+20=3414 + 20 = 34.

The direct way to find them is to try every pair of positions. Six values make only 15 pairs, but the number of pairs grows with the square of the length. CSES Sum of Two Values allows 200,000 values, which make this many pairs:

200,000ร—199,9992=19,999,900,000ย pairs\frac{200{,}000 \times 199{,}999}{2} = 19{,}999{,}900{,}000 \text{ pairs}

At about 10810^8 simple operations a second, that is 200 seconds of work against a one-second limit. The pair loop does the same work whatever order the list is in, so sorted order does not help it. The scan with two indices does use the order: in a sorted list, one sum can rule out many pairs at once.