How to Explain Two Sum II (Input Array Is Sorted) in a Coding Interview (Step-by-Step)
Two Sum II is where the two-pointer pattern is born. The sorted array is the hint — and if you miss it, you’ll reach for a HashMap and waste O(n) space for no reason. Spot it, and the solution is O(n) time, O(1) space, and five lines of code.
In this post, you’ll learn exactly how to walk an interviewer through this problem: why the sorted property changes everything, how the two pointers move, and what edge cases to call out proactively.
Problem Statement
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers that add up to a specific target.
Return the indices of the two numbers as an integer array [index1, index2] where 1 <= index1 < index2 <= numbers.length.
Your solution must use only constant extra space.
Examples
Output: [1, 2] → numbers[0] + numbers[1] = 2 + 7 = 9
Output: [1, 3] → numbers[0] + numbers[2] = 2 + 4 = 6
Output: [1, 2] → numbers[0] + numbers[1] = -1 + 0 = -1
Constraints
2 <= numbers.length <= 3 * 10⁴-1000 <= numbers[i] <= 1000numbersis sorted in non-decreasing order- Exactly one solution exists
- Must use only O(1) extra space
What Is the Problem?
“I need to find two numbers in a sorted array that sum to a target and return their 1-based indices. The array is already sorted, and I must solve it in constant space — so no HashMap.”
The moment you say “no HashMap because constant space is required”, the interviewer knows you read the constraints carefully. That’s a strong signal.
Step 1: Start With the Brute Force (Then Dismiss It)
Check every pair with nested loops
Time: O(n²)
Space: O(1)
Store complements in a map
Time: O(n)
Space: O(n) ✗ violates constraint
Exploit sorted order, squeeze inward
Time: O(n)
Space: O(1) ✓
“The HashMap approach from Two Sum I would work but uses O(n) space — which violates the constraint. The sorted array gives us a better option: two pointers.”
The Key Insight — Sorted Array = Two Pointers
Because the array is sorted, we know: if the sum of two pointers is too large, moving the right pointer left makes it smaller. If it’s too small, moving the left pointer right makes it larger.
This gives us a guaranteed path to the answer without revisiting any element — O(n) time, O(1) space.
Step 2: Explain the Algorithm in Plain English
“I place one pointer at the start of the array and one at the end. I compute their sum. If it equals the target, I return their 1-based indices. If the sum is too large, I move the right pointer left to decrease it. If the sum is too small, I move the left pointer right to increase it. Since exactly one solution is guaranteed, the pointers will always converge on it.”
Step 3: Talk Through the Code
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left = 0 # Start pointer at the beginning
right = len(numbers) - 1 # End pointer at the last element
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left + 1, right + 1] # Convert to 1-based index
elif total < target:
left += 1 # Sum too small — move left pointer right
else:
right -= 1 # Sum too large — move right pointer leftPoint out the left + 1 and right + 1 — the problem is 1-indexed, easy to forget under pressure.
Visual Walkthrough
Tracing through numbers = [2, 3, 4, 7, 11, 15], target = 9:
| L index | R index | numbers[L] | numbers[R] | sum | Action |
|---|---|---|---|---|---|
| 0 | 5 | 2 | 15 | 17 | 17 > 9 → move R left |
| 0 | 4 | 2 | 11 | 13 | 13 > 9 → move R left |
| 0 | 3 | 2 | 7 | 9 | 9 = 9 → move R left |
| 0 | 3 | 2 | 7 | 9 ✓ | Return [1, 4] |
Final state: L at index 0 (value 2), R at index 3 (value 7) → return [1, 4] (1-based)
Step 4: Highlight Edge Cases
"The problem returns 1-based indices — so the answer is[left + 1, right + 1], not[left, right]. This is the most common off-by-one mistake on this problem."
"The constraints allow negative numbers. Two pointer logic still works — we're comparing sums to target, not assuming positivity. Example:[-1, 0]with target-1correctly returns[1, 2]."
"The solution can be two adjacent elements, e.g.[2, 7, 11]with target 9. The two pointers will converge toleft=0, right=1—left < rightis still true, so they're found correctly."
"The problem guarantees exactly one solution, so we don't need to handle no-solution or multiple-solution cases. The while loop will always find the answer beforeleftandrightcross."
Step 5: State Time and Space Complexity
| Approach | Time | Space |
|---|---|---|
| Brute Force | O(n²) | O(1) |
| HashMap | O(n) | O(n) |
| Two Pointers ✓ | O(n) | O(1) |
"Two pointers gives us the best of both worlds — O(n) time like the HashMap approach, but O(1) space because we only use two index variables. Each element is visited at most once as the pointers never move backward."
Interview Checklist for Two Sum II
- Restate — "find two numbers in a sorted array that sum to target, return 1-based indices"
- Call out O(1) space constraint immediately — rules out HashMap
- State the key insight — sorted array means two pointers can squeeze inward
- Explain the movement logic — sum too big → move right left, sum too small → move left right
- Mention the 1-based index gotcha — return
left+1, right+1 - Handle negative numbers edge case
- Note that exactly one solution is guaranteed — no edge case needed for no-solution
- Compare to Two Sum I — same problem, sorted input unlocks O(1) space
- State O(n) time and O(1) space
- Ask before coding, don't just dive in
Related Problems to Practice
If you can solve Two Sum II cleanly, try these next: