Two Sum II - Input Array Is Sorted

Medium#167towards each other

You get numbers sorted from smallest to largest and a target sum. Find two numbers that add up to it and return their positions, counting from 1, not from 0. A pair always exists, and one number cannot be taken twice. Our example: [1, 4, 6, 7, 10, 13], sum 16 — the answer is [3, 5]: 6 + 10.

167 Two Sum II - Input Array Is SortedWalkthrough · 1×

Example: [1, 4, 6, 7, 10, 13], sum 16. The pointers start at both ends: too small — left moves right, too big — right moves left.

01142637410513left
still possiblethe pair being checkedruled outthe pair found

left starts at the smallest number, 1

01/21
restart · back · play · step
Speed
1function twoSumSorted(numbers, target):
2 left = 0
3 right = len(numbers) - 1
4 while left < right:
5 sum = numbers[left] + numbers[right]
6 if sum < target:
7 left = left + 1
8 else if sum > target:
9 right = right - 1
10 else:
11 return [left + 1, right + 1]
state
left
0
right
–
sum
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The numbers are sorted, so moving left to the right can only make the sum bigger, and moving right to the left can only make it smaller.
  2. A move rules a number out for good. If the sum is too small, the left number with any other number still in play is no bigger, so it has no partner. Too big: the same for the right number.
  3. Unlike the card, the answer is positions counted from 1, not indices: add 1 to each pointer.

Complexity

Time O(n): each step moves one pointer inwards, so there are at most n − 1 steps. Memory O(1): only two pointers and a sum.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.