The problem
Given a list of numbers sorted from small to large and a target, find the two numbers that add up to the target and return their positions (LeetCode counts from 1).
Input: [1, 3, 4, 6, 8, 11, 13, 15], target = 10 Output: [3, 4] (positions of 4 and 6, counting from 1)
Picture it
Picture a row of lockers numbered in increasing order, with one friend at each end. They add their two locker numbers. Too big? The friend on the right steps left to a smaller locker. Too small? The friend on the left steps right to a bigger one. Because the row is sorted, each step safely rules out a locker, and they meet the answer without trying every pair.
How to recognise it
- You need a pair that adds up to a target, and the list is already sorted.
- Sorted order means a sum tells you which way to move: too small, use a bigger number; too big, use a smaller one.
- The problem asks for O(1) extra space, which rules out the dictionary from Two Sum.
- Up to 3 × 10^4 numbers, and exactly one answer is guaranteed.
Start with brute force
Try every pair (i, j) with i < j and return the first one that hits the target, counting positions from 1.
def two_sum_brute(nums, target):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i + 1, j + 1]
return []
There are n(n − 1)/2 pairs, so time is O(n²) and space O(1). With n = 3 × 10^4 that is about 4.5 × 10^8 pair checks, too slow. A binary search for target − nums[i] from each i is O(n log n), and the Two Sum dictionary is O(n) but uses O(n) space. Neither uses the sorting fully.
From brute force to the idea
- Start at the extremes. Put
lon the smallest number andron the largest, and look at their sum. - Too small? Move
lright. If the sum is below the target,nums[l]is too small even with the largest partner left. Every other partner is smaller still, sonums[l]can never be part of the answer. Drop it. - Too big? Move
rleft. By the same argument,nums[r]is too big even with the smallest partner, so drop it. - Each step discards one number for good. The answer pair is never discarded, because a pointer only moves past a number that cannot be in it. So the pointers must reach the pair.
- Return positions from 1. LeetCode counts from 1, hence
[l + 1, r + 1].
This is the key idea: on sorted data, the sum's direction tells you which end to drop, one number per step.
The key idea
Sorted input lets two pointers squeeze inward: sum too big → move right pointer left, too small → move left pointer right. O(n).
Python solution
def two_sum(nums, target):
l, r = 0, len(nums) - 1
while l < r:
s = nums[l] + nums[r]
if s == target:
return [l + 1, r + 1] # 1-based
if s < target:
l += 1
else:
r -= 1
return []In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): every pair is checked | O(1): two indices |
| Two pointers (shown code) | O(n): each step moves one pointer inwards, at most n − 1 steps | O(1): two indices and a sum |
Edge cases
- Duplicate values in the answer (
[2, 2], target 4): returns[1, 2]; the two pointers are different positions. - Negatives (
[-1, 0], target −1): returns[1, 2]; sorted order is all that matters. - No pair exists (
[1, 2], target 10): returns[]. LeetCode promises an answer, so this only matters if you reuse the function. - Fewer than two numbers:
[5]and[]both return[]becausel < ris false at once. - Several valid pairs: the problem rules this out. If it happened, the code would return the first pair the pointers meet.
Common mistakes
- Writing
while l <= r. Whenl == r, one number is added to itself:[2, 3, 7]with target 6 wrongly returns[2, 2]. - Returning
[l, r], forgetting the 1-based positions. - Moving both pointers after a miss, which can skip the answer.
- Using a dictionary out of habit. It works, but it ignores the sorted order and breaks the O(1) space requirement.
Given a sorted list and a target, count the pairs of positions i < j with nums[i] + nums[j] less than the target. For [-1, 1, 1, 2, 3] and target 2 the answer is 3. Describe your approach, then write it if you like.
Compare with our answer
Use the same two pointers, but count whole blocks at once. If nums[l] + nums[r] is below the target, then nums[l] plus any number between l + 1 and r is also below it, because those are no bigger than nums[r]. That is r - l pairs, all with l; count them and move l. Otherwise nums[r] is too big for the current l and for every l still to come, so move r.
def count_pairs_below(nums, target):
l, r, count = 0, len(nums) - 1, 0
while l < r:
if nums[l] + nums[r] < target:
count += r - l # nums[l] pairs with l+1..r
l += 1
else:
r -= 1
return count
Time O(n), space O(1). Counting pairs one by one would be O(n²) when most pairs qualify.
A strong answer mentions: why one comparison settles r - l pairs at once, why moving r loses nothing, and the O(n) time.
1. You have a sorted list of item prices and must find whether two different items cost exactly your budget, using O(1) extra memory. Which approach fits best?
The list is sorted and memory must be O(1), so two pointers give O(n) time and O(1) space. A dictionary needs O(n) space, and binary search is O(n log n).
2. When nums[l] + nums[r] is less than the target, why is it safe to discard nums[l] for good?
nums[r] is the largest number still in play. If nums[l] plus it is still short, so is nums[l] plus anything else that remains. The smallest number can be in the answer; it just is not here.
3. A learner changes the loop to while l <= r. Which call now returns a wrong answer?
The pointers meet on the 3 and 3 + 3 = 6, so it returns [2, 2], using one number twice. In [1, 2, 4] the meeting number is 4 and 8 is not 7, and the other calls find their pair before the pointers meet.
Score 60% or more and the lesson is marked complete.