2
5
8
11
15
19
[0][1][2][3][4][5]
Brute force
▸1given sorted arr, target2for i ← 0 to n − 2:3 fix arr[i]4 for j ← i + 1 to n − 1:5 if arr[i] + arr[j] == target → return (i, j)6return none
state
- target19
warming up the animation
Given a 1-indexed array of integers sorted in non-decreasing order, return the indices of the two numbers that add up to a given target. Exactly one solution exists, and you may not use the same element twice.
▸1given sorted arr, target2for i ← 0 to n − 2:3 fix arr[i]4 for j ← i + 1 to n − 1:5 if arr[i] + arr[j] == target → return (i, j)6return none
We want two indices (i, j) such that arr[i] + arr[j] = 19.