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 27We want two different positions whose values add up to 34. Here they are positions 3 and 4, because .
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:
At about 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.
Compare the two ends and move one of them
Put one index, left, on the smallest value and another, right, on the largest, and add the two values: . That is less than 34, and it tells us something about every pair that contains 3. Since 27 is the largest value in the list, any other partner gives 3 a sum of 30 or less. No pair that sums to 34 contains 3, and we can leave 3 behind by moving left one step to the right, onto 8.
Now the two ends are 8 and 27, and , which is more than 34. This time the sum tells us about 27. We have already left 3 behind, so the smallest partner 27 could have is 8, and any other partner makes the sum 35 or more. No pair that sums to 34 contains 27, and right moves one step to the left, onto 20.
The scan keeps going the same way until a sum is 34:
[3, 8, 11, 14, 20, 27] with target 34. Grey values have been left behind; each sum that is not 34 removes exactly one.Each step adds the values at left and right and does one of three things:
- If the sum equals the target, the two positions are the answer.
- If the sum is less than the target, the left value is too small, and
leftmoves one step right. - If the sum is greater than the target, the right value is too large, and
rightmoves one step left.
On our list the fifth sum is the match, where the pair loop has 15 to try. If no two values have the target sum, the indices end up on the same position. One position cannot be a pair, so the scan stops there and reports that there is no answer.
The two indices are called pointers because each one points at a position of the list, and the method is called two pointers. It comes in two forms. In this lesson the pointers start at opposite ends and move toward each other. In the other form, the sliding window, both pointers start at the left end and move to the right.
Choose each move and see the pairs it rules out
In this widget you choose the moves. The grid under the list has one square for each of the 15 pairs: the square in row and column , with less than , stands for positions and . Moving left off position shades the open squares of row , and moving right off position shades the open squares of column . Those are the pairs the move rules out, though the scan added up only one of them.
The pair scan in code
Here is the same task as a judge problem:
You get a list numbers sorted in nondecreasing order and an integer target. Return the positions of two different elements that add up to target as [index1, index2] with index1 < index2, counting positions from 1.
Exactly one answer exists. The solution may use only a constant amount of extra memory.
Constraints
Sample 1 ยท Input
numbers = [2,7,11,15], target = 9
Output
[1,2]
Sample 2 ยท Input
numbers = [2,3,4], target = 6
Output
[1,3]
Sample 3 ยท Input
numbers = [-1,0], target = -1
Output
[1,2]
Three details of the statement show up in the code. The judge counts positions from 1, so the function adds 1 to each index before returning it. The two elements must be at different positions: in the second sample , but the list holds only one 3, so the answer is positions 1 and 3, the values 2 and 4. And the limit on extra memory rules out the hash map. The scan meets it, because left and right are all it stores.
The loop is the three cases above, with the match checked first:
def two_sum(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left + 1, right + 1]
if total < target:
left += 1
else:
right -= 1
return []
print(two_sum([2, 7, 11, 15], 9))
print(two_sum([2, 3, 4], 6))
print(two_sum([-1, 0], -1))Prints [1, 2], [1, 3] and [1, 2], the three samples' answers.
The loop runs while left < right, and that condition is what keeps the two positions different: once the pointers meet, only one position remains and the loop ends. The statement guarantees an answer, so on the judge the function returns from inside the loop. The final return covers a list with no pair.
Worked example
Trace the pair scan
The trace runs the scan on our list one sum at a time, with positions counted from 0. With Predict the next step switched on, it asks you for the next move before showing it. It also runs on three other lists: the first sample above, whose pair sits at the left end; a list with no pair; and a list whose answer is two equal values at different positions.
Optional practice. Try an answer or keep stepping; predictions do not award XP or solve credit.
Keep both ends of the sorted list. Every surviving candidate pair lies between these pointers.
Change the example input
Current result: [3,4]
Cost of the pair search
- Trying every pair
time - There are pairs: 19,999,900,000 for 200,000 values.
- Two pointers on a sorted list
time, extra memory - Each sum that is not a match moves one pointer one step toward the other, so there are at most sums: 199,999 for 200,000 values.
Sorted order and the invariant
Both moves used one fact about a sorted list: every value between left and right is at least the left value and at most the right value. So when the sum of the two ends is too small, pairing the left value with anything else between the pointers cannot make the sum larger, and the left value has no partner. When the sum is too large, pairing the right value with anything else between the pointers cannot make the sum smaller, and the right value has no partner. Either way, the value we leave behind belongs to no pair with the target sum.
That gives the scan an invariant, a statement that is true before every step and still true after it:
Invariant
Every pair that sums to the target has both of its positions between left and right, the ends included.
It is true at the start, when the pointers enclose the whole list, and each move keeps it true, because the value left behind is in no such pair. The pointers get one step closer with every move, so the scan either reaches a pair with the target sum or ends with both pointers on one position. One position cannot be a pair, so by the invariant the list has none.
The scan on an unsorted list
On an unsorted list that fact is false, and the scan can miss the pair. Take [1, 9, 2, 6] with target 8, where . The first sum, , is too small, and left moves onto 9. The second, , is too large, so the scan leaves 6 behind while its partner 2 is still between the pointers. Dropping 6 would be safe only if every value between the pointers were at least the left value, 9. Only sorted order guarantees that. After one more sum, , the pointers meet and the scan reports no pair.
So an unsorted list has to be sorted first. The sort takes time, more than the scan itself, and it moves the values to new positions. When the problem asks for the original positions, as CSES Sum of Two Values does, you can sort pairs of (value, original position) and scan those. Or you can use a hash map, which needs no sorting but stores an entry for every value.
Fix one value and scan for the other two
The pair scan is also a building block. When a problem asks for three values, a loop can choose the first one and the scan can find the other two.
You get a list of integers nums. Return every triple of values at three different positions that sums to 0. Two triples with the same three values count once, whatever positions they came from; the triples may come in any order.
Constraints
Sample 1 ยท Input
nums = [-1,0,1,2,-1,-4]
Output
[[-1,-1,2],[-1,0,1]]
Sample 2 ยท Input
nums = [0,1,1]
Output
[]
Sample 3 ยท Input
nums = [0,0,0]
Output
[[0,0,0]]
In the first sample, and . The list holds two copies of , so the values , 0 and 1 can be picked from two different sets of positions, but the answer lists them once.
Trying every set of three positions is too slow for 3,000 values:
That is about 45 seconds of work. To do better, sort the list, so that the first sample becomes [-4, -1, -1, 0, 1, 2], and let each position i in turn hold the smallest value of the triple. The other two values are to the right of i and must sum to -nums[i]. That is the pair problem on the sorted positions after i, so we run the scan there, with left at i + 1 and right at the end of the list.
One thing changes inside the scan. A match no longer ends it, because the same first value can belong to several triples. We record the triple and move both pointers inward. Once the first and second values are chosen, the third has to be whatever brings the sum to 0, so a different triple needs a different second value, and with it a different third.
Equal values would make the same triple appear more than once, and two checks prevent that. When nums[i] equals the value before it, we skip i, because the scan for the earlier copy already found every triple that starts with this value. And after a match, left keeps moving while it sits on another copy of the second value it just used. The right pointer needs no check of its own: if it lands on a copy of the old third value, the new second value is larger than the old one, so the sum is too large and the scan moves right again.
def three_sum(nums):
nums = sorted(nums)
out = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
out.append([nums[i], nums[left], nums[right]])
left += 1
while left < right and nums[left] == nums[left - 1]:
left += 1
right -= 1
return out
print(three_sum([-1, 0, 1, 2, -1, -4]))
print(three_sum([0, 1, 1]))
print(three_sum([0, 0, 0]))Prints the three samples' answers.
On the sorted first sample, the loop over i does this:
i = 0fixes and needs a pair that sums to 4. The two largest values give only , so the scan finds nothing.i = 1fixes and needs a pair that sums to 1. The first sum, , matches. Both pointers move, and matches as well.i = 2holds again and is skipped. Without that check it would record[-1, 0, 1]a second time.i = 3fixes 0 and finds nothing, because is too large.
The scan for position i makes fewer than sums, so all the scans together make fewer than , and the search takes time after an sort. For 3,000 values that is under sums, about a thousand times fewer than the number of triples.
Count many pairs with one comparison
So far, each comparison has ruled out one value. When a problem asks how many pairs pass a test, one comparison can also count a whole run of pairs that pass.
You get a list of side lengths nums. Return how many triples of positions hold three lengths that could form a triangle. Three sides form a triangle when each one is shorter than the sum of the other two.
Constraints
Sample 1 ยท Input
nums = [2,2,3,4]
Output
3
Sample 2 ยท Input
nums = [4,2,3,4]
Output
4
In the first sample the three triangles are 2, 3, 4 using the first 2, the same sides using the second 2, and 2, 2, 3. The sides 2, 2 and 4 make no triangle, because is not greater than 4.
The statement has three inequalities, but with the sides named so that , only one needs checking:
The other two are and . Take the first: alone is already at least , so adding a positive makes the left side larger than . The same goes for . Only a side of length 0 could break them, and such a side fails anyway, because then is just , which is at most . So three sides form a triangle exactly when the two shorter ones sum to more than the longest.
As in 3Sum, we sort the list and fix one value, this time the longest side nums[k], so that the test compares a sum of two values with one number. The other two sides come from positions 0 to , and we count the pairs there whose sum is greater than nums[k]. The pointers start at left = 0 and right = k - 1, and each step compares one sum:
- If
nums[left] + nums[right]is greater thannums[k], so is the sum ofnums[right]with every value between the pointers, because those values are at leastnums[left]. That makesright - leftpairs, one for each position fromlefttoright - 1. We add that number to the count. Every passing pair that usesrightis now counted, sorightmoves one step left. - Otherwise
nums[left]is too small even withnums[right], the largest partner it still has. It passes with none of them, soleftmoves one step right.
def triangle_number(nums):
nums = sorted(nums)
count = 0
for k in range(len(nums) - 1, 1, -1):
left, right = 0, k - 1
while left < right:
if nums[left] + nums[right] > nums[k]:
count += right - left
right -= 1
else:
left += 1
return count
print(triangle_number([2, 2, 3, 4]))
print(triangle_number([4, 2, 3, 4]))Prints 3 and then 4, the two samples' answers.
On the first sample, sorted as [2, 2, 3, 4], start with , the side 4. With left = 0 and right = 2 the sum is , which is greater than 4, so the step counts pairs: each 2 with the 3. Then right moves onto the second 2, where is not greater than 4, so left moves and meets right. For , the side 3, the sum counts one more pair, and the total is 3.
The scan for the longest side nums[k] makes fewer than comparisons, because each one moves a pointer and the pointers start positions apart. All the scans together make fewer than , so the count takes time. For 1,000 sides that is under 500,000 comparisons, where trying every triple would take .
Two ends without sorted order
In all three problems so far, a pointer moved once its value was finished: it had no partner left, or all of its pairs had been counted. In each case, sorted order is what showed the value was finished. Two pointers at opposite ends can also work on a list that is not sorted, when the problem gives another way to tell that one end is finished.
You get a list height where height[i] is the height of a vertical wall at position . Choose two walls; together with the floor they hold water up to the shorter wall's height. Return the largest amount of water any two walls can hold.
Constraints
Sample 1 ยท Input
height = [1,8,6,2,5,4,8,3,7]
Output
49
Sample 2 ยท Input
height = [1,1]
Output
1
With walls at positions left and right, the water is as high as the shorter wall and as wide as the distance between the two, so the container holds min(height[left], height[right]) * (right - left) units. In the first sample the best pair is the wall of height 8 at position 1 and the wall of height 7 at position 8:
Move the shorter wall inward
At this problem's limit of 100,000 walls there are 4,999,950,000 pairs, about 50 seconds of work. To avoid trying them all, we start from the widest pair, which in the first sample is positions 0 and 8 and holds , and ask which wall to give up.
Look at the left wall, of height 1. Any other container that uses it has a right wall closer than position 8, so it is narrower, and its water still cannot rise above 1. It holds less than 8. So the left wall is finished, and left moves inward. The taller wall is different: with another partner it may hold much more, and here it goes on to hold 49.
The same holds at every step. Pairing the shorter wall with any other wall between the pointers gives a container that is narrower and no higher, so the current container is the best one left for the shorter wall. We record its amount if it is the largest so far, and then moving the shorter wall inward gives up nothing better. When the two walls are equally tall, this is true of both, and either one may move.
def max_area(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
best = max(best, min(height[left], height[right]) * (right - left))
if height[left] <= height[right]:
left += 1
else:
right -= 1
return best
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))
print(max_area([1, 1]))Prints 49 and then 1, the two samples' answers.
On the first sample the scan measures 8, then 49 at positions 1 and 8, then 18, 40, 24, 6, 10 and 4 as the pointers close in, and it returns 49. Each step moves one pointer, so walls take steps: 99,999 at the limit, where the pair loop needs about five billion.
Common two-pointer mistakes
Looping while
left <= rightin the pair search.- Where it breaks
- For
[4, 5]with target 8, the first sum is 9, sorightmoves onto 4. With both pointers on position 0 the loop runs once more, adds and returns[1, 1]: one element used twice. - The fix
- Loop while
left < right, so that the two positions always differ.
Moving
leftonly one step after a 3Sum match.- Where it breaks
- On
[-2, 0, 0, 2, 2], the first match is . One step laterleftis on the second 0 andrighton the first 2, which match again, and the answer lists[-2, 0, 2]twice. - The fix
- After a match, keep moving
leftwhile its value equals the one before it.
Moving the taller wall in Container With Most Water.
- Where it breaks
- On
[1, 8, 6, 2, 5, 4, 8, 3, 7], the wall of height 1 then stays in every container the scan measures. Each one is capped at height 1, and the scan returns 8 where the answer is 49. - The fix
- Move the shorter wall. It is the one that cannot be part of a larger container.
Recall In the triangle count, a sum that is large enough moves `right`. In the pair search, the pointer that moved was the one whose value had failed. Why the difference?
In both, a pointer moves when its value is finished. In the pair search that is the value with no partner left. In the triangle count, a large enough sum has just counted every passing pair that uses nums[right], all right - left of them, so right is the finished one. nums[left] may still pass with a smaller partner, and it stays.
Two more problems and the next lesson
Two problems in this lesson's list have no worked solution above. Both use two pointers to build a sorted answer from its largest value down, the way the merge step of merge sort builds one from its smallest value up.
Judge problems
- Squares of a Sorted Array(opens the judge in a new tab) โ
The list is sorted, so the value furthest from zero is at one of the two ends, and its square is the largest. Compare the two ends, write the larger square into the last free slot of the answer, and move that pointer inward.
- Merge Sorted Array(opens the judge in a new tab) โ
nums1has empty slots at its end, enough to holdnums2. The pointers sit on the last unplaced value of each list. The larger of the two is the largest value not yet placed, so it goes into the last free slot ofnums1. Filling from the back keeps each write away from the values ofnums1that have not been read yet.
Related chapters
- Sliding window โ
Both pointers start at the left end and move right, and the values between them form a window.
Further reading
- USACO Guide, SilverTwo Pointers(opens in a new tab)
Both forms side by side: Sum of Two Values with pointers from opposite ends, then Books with a window, followed by a graded problem list.
- Antti Laaksonen (PDF)Competitive Programmerโs Handbook, Section 8.1: Two pointers method(opens in a new tab)
Pages 77 to 79 explain why the pointers make moves in total, using a subarray sum and the 2SUM problem, and mention the 3SUM method.
- OI Wiki, in Chineseๅๆ้ (Two pointers)(opens in a new tab)
Maintaining a range with two pointers, matching a subsequence, pairs in a sorted array and Floydโs cycle detection on a linked list, each with code.
- Wikipedia3SUM(opens in a new tab)
The sort-then-scan method used above, and the faster algorithms found since 2014, which beat quadratic time by small margins.