Two Sum II - Input Array Is Sorted
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
The list is sorted. Find two numbers adding to the target and return their 1-based positions, using only constant extra space.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Put one pointer at the smallest value and one at the largest. What is their sum compared with the target?
- Hint 2If the sum is too big, which of the two can never be part of the answer?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Items on a shelf are arranged from cheapest to costliest. You have exactly ₹900 to spend on two items. Hold the cheapest in your left hand and the costliest in your right. Total too high? The costliest can never fit with anything, put it back and take the next costliest. Total too low? The cheapest is too cheap, swap it for the next cheapest. You keep shrinking until the total is exactly ₹900.
- The obvious way
Check all pairs O(n²), or use a hash map O(n) time but extra memory (the problem wants constant extra space).
- The key insight
Because the list is sorted you can throw candidates away. If smallest + largest is too big, the largest pairs with nothing (even the smallest was too small a partner), so drop it. If it is too small, the smallest cannot work with anything, drop it. Each step removes one number, so you finish in one walk.
- The algorithm
- Left pointer on the first number, right pointer on the last.
- Add the two numbers. Equal to the target? Answer is their positions (starting from 1).
- Total too small? Move the left pointer one step right.
- Total too big? Move the right pointer one step left. Repeat.
Watch it run
Exampleprices = [2, 7, 11, 15], target = 9
Left holds 2, right holds 15: total 17, too big. Put 15 back.
total 17 > 9
Where people slip
- The answer uses 1-based positions.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
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] # the answer is 1-based
if total < target:
left += 1 # the small one is too small
else:
right -= 1 # the big one is too big
return []Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.