Two Sum II
MediumSorted input · find indices that add up to target
The list is sorted, so put one finger at the smallest and one at the biggest; too small → move left up, too big → move right down.
The idea
The array is sorted, so put one pointer at the smallest value and one at the largest. Their sum tells you exactly which pointer to move: too small → raise the low end; too big → lower the high end.
The trick
- Sorting turns 'search for a partner' into a single directed sweep.
1
3
4
5
0
1
2
3
target9
Step 1 of 7. Brute force: test every pair and check if it adds to 9. Values: 1, 3, 4, 5. target 9.
1/7
Brute force
timeO(n²)spaceO(1)
Try every pair.
1// try every pair2for (let i = 0; i < n; i++)3 for (let j = i + 1; j < n; j++)4 if (nums[i] + nums[j] === target)5 return [i, j];6return [-1, -1];Input
- array
- [1, 3, 4, 5]
Memory
- i
- —
- j
- —
- target
- 9
- pairs tried
- —
- sum
- —
Output
- sum
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [2, 7, 11, 15], target = 9
- Output:
- [1, 2]
- Explanation:
- nums[1]+nums[2]=2+7=9 (1-indexed).
Example 2
- Input:
- nums = [2, 3, 4], target = 6
- Output:
- [1, 3]
- Explanation:
- 2+4=6 at positions 1 and 3.
Example 3
- Input:
- nums = [-1, 0], target = -1
- Output:
- [1, 2]
- Explanation:
- -1+0 = -1.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.