LeetCode · #167

Two Sum II Solution

Given a 1-indexed sorted array, find two numbers that add up to target. Return their indices.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #167

🏗️

Pattern

Two Pointers — converge on sorted

Given a 1-indexed array of integers numbers sorted in non-decreasing order, find two numbers that add up to a specific target. Return their indices as [index1, index2] where 1 ≤ index1 < index2. You must use only constant extra space.

Example

 Input: numbers = [2, 7, 11, 15],  target = 9 Output: [1, 2]
// numbers[1] + numbers[2] = 2 + 7 = 9  (1-indexed) 

Constraints

 • 2 ≤ numbers.length ≤ 3 × 10⁴ • -1000 ≤ numbers[i] ≤ 1000 • numbers is sorted in non-decreasing order • Exactly one solution exists • Must use O(1) extra space 

Section Two · Approach 1

Brute Force — HashMap O(n)

Use the same HashMap approach as LC 1 (Two Sum). This works but ignores the sorted property and uses O(n) space — violating the constant-space constraint.

Problem: A HashMap uses O(n) space. Since the array is sorted, two converging pointers can find the pair in O(n) time with O(1) space — no map needed.

Java — HashMap (violates O(1) space)

 import java.util.HashMap;
class Solution {
public int[] twoSum(int[] numbers, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < numbers.length; i++) {
int comp = target - numbers[i];
if (map.containsKey(comp))
return new int[] { map.get(comp) + 1, i + 1 };
            map.put(numbers[i], i);
        }
return new int[] {};
    }
}

Python — dict (violates O(1) space)

 class Solution:
def twoSum(self, numbers: list[int], target: int) -> list[int]:
        seen = {}
for i, num in enumerate(numbers):
if target - num in seen:
return [seen[target - num] + 1, i + 1]
            seen[num] = i

Metric	Value
Time	O(n)
Space	O(n) — violates constraint

Section Three · Approach 2

Two Pointers — O(n) time, O(1) space

Place left at the start and right at the end. Compute their sum. If it equals target, done. If too small, move left right (increase sum). If too large, move right left (decrease sum).

💡 Mental model: Imagine a thermostat dial with two knobs. The left knob only turns right (warmer), the right knob only turns left (cooler). You're trying to hit an exact temperature. Too cold? Move the left knob. Too hot? Move the right. Since the dial is sorted, you converge guaranteed.

Algorithm

Step 1: Set left = 0, right = n - 1.
Step 2: Compute sum = numbers[left] + numbers[right].
Step 3: If sum == target → return [left+1, right+1] (1-indexed).
Step 4: If sum < target → left++ (need a larger value).
Step 5: If sum > target → right-- (need a smaller value).

🎯 Why it's correct:

The sorted order guarantees monotonic behavior.
Moving left right can only increase the sum; moving right left can only decrease it.
Since exactly one solution exists, the pointers must meet it.
No valid pair is skipped because every decision eliminates only impossible candidates.

Section Four · Trace

Visual Walkthrough

Trace through numbers = [2, 7, 11, 15], target = 9:

Converging Two Pointers on sorted array

Section Five · Implementation

Code — Java & Python

Java — Two Pointers

 class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target)
return new int[] { left + 1, right + 1 }; // 1-indexed else if (sum < target)
                left++; // need larger value else
right--; // need smaller value
}
return new int[] {}; // unreachable
}
}

Python — Two Pointers

 class Solution:
def twoSum(self, numbers: list[int], target: int) -> list[int]:
        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 

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
HashMap	O(n)	O(n)	Ignores sorted property; violates O(1) space
Binary Search per element	O(n log n)	O(1)	Slower; binary search for each complement
Two Pointers ← optimal	O(n)	O(1)	Exploits sorted order. One pass, no extra memory.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Answer at extremes	`[1, 5], t=6`	First check finds it. L=0, R=1 → 1+5=6.
Negative numbers	`[-3, 0, 3], t=0`	Negatives work fine — sorted order still holds.
Duplicates	`[1, 1, 3], t=2`	Two 1s sum to 2. L=0, R=2→4>2→R--, R=1→1+1=2 ✓
Large array	`n = 3×10⁴`	O(n) handles it easily. At most n iterations.

⚠ Common Mistake: Returning 0-indexed instead of 1-indexed results. The problem specifies 1-indexed — remember to add 1 to both indices before returning.

← Back to Two Pointers problems

LearningTree

LC 167 · Two Sum II — Input Array Is Sorted — Solution & Explanation | DSA Guide