Mastering LeetCode Problem 0167 | Mohammad.H Mohammadi

Problem 0167: Two Sum II - Input Array Is Sorted

LeetCode 167 is one of those problems that looks simple on the surface but is extremely important for pattern-building.

If Two Sum (LeetCode 1) is your entry point to hash maps, then:

Two Sum II (LeetCode 167) is your entry point to the two-pointer pattern on sorted arrays.

This problem forces you to exploit the sorted property and solve the task in O(n) time with O(1) extra space — a very common real-interview requirement.

In this post, we’ll:

Understand the problem precisely
Look at the naive approach (and why it’s not ideal)
Derive the optimal two-pointer solution
Walk through it with examples
Analyze complexity
Connect it to other two-pointer problems you’re likely to see

1. Problem Statement

You are given:

A 1-indexed array numbers of integers, sorted in non-decreasing order.
An integer target.

Your task:

Find two numbers such that they add up to target, and return the indices (1-based) as [index1, index2], where 1 <= index1 < index2 <= numbers.length.

Constraints:

There is exactly one solution, and you may not use the same element twice.
You must use only constant extra space.

1.1. Example 1

Input:  numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation:
  numbers[1] + numbers[2] = 2 + 7 = 9

1.2. Example 2

Input:  numbers = [2,3,4], target = 6
Output: [1,3]
Explanation:
  numbers[1] + numbers[3] = 2 + 4 = 6

1.3. Example 3

Input:  numbers = [-1,0], target = -1
Output: [1,2]
Explanation:
  -1 + 0 = -1

2. First Thought: Hash Map (But Not Ideal Here)

If you’ve solved LeetCode 1 – Two Sum, your brain immediately goes to:

Use a hash map: value → index
For each element x, check if target - x exists in the map.

This works in general:

Time: O(n)
Space: O(n)

But here the problem explicitly wants:

“Use constant extra space.”

And there’s a very important extra piece of information:

The array is sorted.

Whenever you see “sorted” and “find pair with sum …”, your brain should light up with:

Two pointers.

3. Key Insight: Sorted Array ⇒ Two Pointers

Because the array is sorted in non-decreasing order, we can maintain two indices:

left at the beginning, pointing to the smallest element
right at the end, pointing to the largest element

We then inspect the sum:

sum_target = numbers[left] + numbers[right]

Based on the comparison to target:

If sum_target == target → we’re done.
If sum_target < target → the sum is too small:
- We need a larger sum, so we should increase the smaller side → move left to the right.
If sum_target > target → the sum is too large:
- We need a smaller sum, so we should decrease the larger side → move right to the left.

This strategy works efficiently because of the sorted order — every move is logically justified and we never need to “go back”.

4. Two-Pointer Algorithm

Let’s formalize the approach.

4.1 Algorithm Steps

Initialize:
- left = 0
- right = len(numbers) - 1
While left < right:
- Compute sum_target = numbers[left] + numbers[right]
- If sum_target == target:
  - Return [left + 1, right + 1]
    (because the problem uses 1-based indices)
- Else if sum_target < target:
  - Move left right: left += 1
- Else (sum_target > target):
  - Move right left: right -= 1
Because the problem guarantees exactly one solution, we will always return inside the loop.

5. Python Implementation

Here is a clean Python implementation using the two-pointer technique.
This version is LeetCode-compatible and uses constant extra space:

from typing import List

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        right = len(numbers) - 1
        left = 0

        while left < right:
            sum_target = numbers[left] + numbers[right]

            if sum_target == target:
                # Convert to 1-based indices as required.
                return [left + 1, right + 1]
            elif sum_target < target:
                # Need a larger sum -> move left pointer right.
                left += 1
            else:
                # sum_target > target: need a smaller sum -> move right pointer left.
                right -= 1

Your original algorithmic logic (before adding self) is exactly this — optimal and idiomatic.

6. Detailed Walkthrough

Let’s walk through the core logic on a couple of examples.

6.1. Example 1: `[2, 7, 11, 15], target = 9`

Initial:

numbers = [2, 7, 11, 15]
left = 0  -> 2
right = 3 -> 15

Step 1:
- sum_target = 2 + 15 = 17
- 17 > 9 → sum too large → move right left
- right = 2 (value 11)
Step 2:
- sum_target = 2 + 11 = 13
- 13 > 9 → still too large → move right left
- right = 1 (value 7)
Step 3:
- sum_target = 2 + 7 = 9
- 9 == 9 → found the pair
- Return [left + 1, right + 1] = [1, 2]

We never needed to revisit any index, and we used just two pointers.

6.2. Example 2: `numbers = [1, 2, 3, 4, 4], target = 8`

Initial:

left = 0 (1)
right = 4 (4)

Step 1:
- sum_target = 1 + 4 = 5 < 8
  → Need bigger sum → move left
- left = 1 (2)
Step 2:
- sum_target = 2 + 4 = 6 < 8
  → Need bigger sum → move left
- left = 2 (3)
Step 3:
- sum_target = 3 + 4 = 7 < 8
  → Need bigger sum → move left
- left = 3 (4)

Now:

left = 3 (4)
right = 4 (4)
sum_target = 4 + 4 = 8

We found the pair. Return [4, 5].

7. Why the Two-Pointer Strategy Is Correct

The crux of the correctness lies in the sorted nature of numbers.

At any step:

numbers[left] ≤ numbers[left + 1]
numbers[right - 1] ≤ numbers[right]

So:

If numbers[left] + numbers[right] < target:
- Even if we decrease right, the sum would not increase (in fact, it would likely decrease or stay similar).
- The only way to increase the sum is to increase the smaller term, i.e., move left to the right.
- Therefore, discarding the current left is safe — no pair containing this left and any element to its left/right can produce the target if the current sum is already too small.
If numbers[left] + numbers[right] > target:
- The sum is too large.
- Increasing left would only increase (or maintain) the sum, which we don’t want.
- We must reduce the larger term, so we move right left.
- Again, discarding the current right is safe.

Each step discards at least one index that can never be part of any valid solution under the constraints — thus ensuring we don’t miss the unique solution guaranteed by the problem.

8. Complexity Analysis

8.1. Time Complexity

Each of left and right moves monotonically:
- left can move from 0 to at most n - 1
- right can move from n - 1 to at most 0
Each pointer moves at most n times.
Overall: O(n) time.

8.2. Space Complexity

We use only a couple of integer variables (left, right, sum_target).
No extra arrays, no hash maps.
Extra space: O(1).

This matches the problem’s requirement: constant extra space.

9. Common Mistakes and Pitfalls

Returning 0-based indices
The problem is explicitly 1-indexed.
Common bug:
```
return [left, right]  # Wrong
```
Correct:
```
return [left + 1, right + 1]
```
Using a hash map anyway
It works, but:
- Uses O(n) extra space
- Ignores the sorted property In real interviews, this can cost you points if the interviewer expects you to leverage the sorted order.
Trying to brute-force with nested loops (O(n²))
Fine for learning, but not acceptable for large inputs or interviews.
Not handling negative numbers
The algorithm naturally supports them — the sorted + two-pointer logic remains valid regardless of sign.

10. elationship to Other Problems (Pattern Building)

LeetCode 167 is a canonical example of the two-pointer pattern on sorted arrays.

Once you master this, you’ll see a similar structure in:

LeetCode 125 – Valid Palindrome
Two pointers from both ends, move inward, compare characters.
LeetCode 680 – Valid Palindrome II
Two pointers with one allowed deletion (branch on first mismatch).
LeetCode 344 – Reverse String
Two pointers swapping characters in-place.
Other array problems:
- Count pairs with certain sum/difference
- Find closest sum to target in a sorted array
- Sliding windows combined with two pointers

The common pattern:

Use left and right indices.
Decide which pointer to move based on a comparison (sum, difference, etc.).
Leverage the sorted property for correctness and efficiency.