Two Sum II - Input Array Is Sorted
Asked at Google, Amazon, Oracle
Problem
Given a sorted array of integers and a target, find two numbers that add up to the target. Return their 1-indexed positions. This problem demonstrates the two-pointer technique on sorted data, achieving O(n) time without a hash map.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Amazon | Medium | View all Amazon questions → |
| Oracle | Medium | View all Oracle questions → |
How to Think About It
Brute force: check every pair. O(n²). The sorted property allows a much better approach.
Two pointers: start with left at index 0 and right at index n-1. The sum of these two is the maximum possible. If sum > target, move right left. If sum < target, move left right.
Why it works: in a sorted array, moving the left pointer right increases the sum, and moving the right pointer left decreases the sum. Each step eliminates one element from consideration.
Why no hash map is needed: unlike Two Sum I, the array is sorted. Two pointers gives O(n) time and O(1) space, which is better than hash map's O(n) space.
Visual walkthrough for nums=[2,7,11,15], target=9:
left=0, right=3. sum=2+15=17 > 9. Move right.
left=0, right=2. sum=2+11=13 > 9. Move right.
left=0, right=1. sum=2+7=9 == 9. Return [1,2].
Visual walkthrough for nums=[2,3,4], target=6:
left=0, right=2. sum=2+4=6 == 6. Return [1,3].
Edge cases: exactly one solution guaranteed, no duplicates in valid pairs, 1-indexed output.
Optimal Approach
Step 1: Set left = 0, right = n-1.
Step 2: While left < right:
current_sum = nums[left] + nums[right]
- If current_sum == target: return [left+1, right+1] (1-indexed)
- If current_sum < target: move left right (need larger sum)
- If current_sum > target: move right left (need smaller sum)
The 1-indexed return is important. The problem uses 1-based indexing.
Time: O(n) — each pointer moves at most n times. Space: O(1).
What Trips People Up in Real Interviews
Returning 0-indexed positions. The problem asks for 1-indexed positions. Return [left+1, right+1], not [left, right].
Using a hash map. While it works (O(n) time), the two-pointer approach is O(1) space and is the expected solution for a sorted array.
Not handling the case where the sum equals the target. When total == target, return immediately. Don't continue searching.
Moving both pointers at once. Only move one pointer per iteration. Moving both might skip the valid pair.
Confusing this with Two Sum I. That problem uses an unsorted array and requires a hash map. This problem uses a sorted array and two pointers.
Solution Code
def twoSum(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left + 1, right + 1]
elif total < target:
left += 1
else:
right -= 1
return []Frequently Asked Questions
What is the Two Sum II - Input Array Is Sorted problem?
Given a sorted array of integers and a target, find two numbers that add up to the target. Return their 1-indexed positions. This problem demonstrates the two-pointer technique on sorted data, achieving `O(n)` time without a `hash map`.
How do you solve Two Sum II - Input Array Is Sorted?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Two Sum II - Input Array Is Sorted?
Two Sum II - Input Array Is Sorted is asked at Google, Amazon, Oracle. It is a medium difficulty problem.
What are common mistakes on Two Sum II - Input Array Is Sorted?
- Returning 0-indexed positions. The problem asks for 1-indexed positions. Return [left+1, right+1], not [left, right].
- Using a `hash map`. While it works (`O(n)` time), the two-pointer approach is `O(1)` space and is the expected solution for a sorted array.
- Not handling the case where the sum equals the target. When `total == target`, return immediately. Don't continue searching.
- Moving both pointers at once. Only move one pointer per iteration. Moving both might skip the valid pair.
- Confusing this with Two Sum I. That problem uses an unsorted array and requires a `hash map`. This problem uses a sorted array and two pointers.