Two Sum II - Input Array Is Sorted

Two Sum II looks just like the famous Two Sum. But there is one big difference. The array is already sorted. That one fact changes everything. It lets you solve the problem with no extra memory at all. The interviewer wants to see if you notice the sorted hint and use it.

🎯 The Problem

You get a sorted array and one target. Find the two numbers that add up to the target. The rules:

• The array is already sorted from small to large.
• Find the two numbers whose sum is the target.
• Return their positions, counted from 1, not 0.
• There is exactly one pair that works.
• You cannot use the same position twice.

For the array [2, 7, 11, 15] and target 9, the pair 2 + 7 gives 9. The 2 sits at position 1 and the 7 at position 2. So the answer is [1, 2]. The partner of a number is its complement. For 2, the complement is 7.

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

Explanation: numbers[0] + numbers[1] = 2 + 7 = 9
             Their 1-based positions are 1 and 2.

Here is the array laid out so you can see it. Notice it grows from left to right.

🐢 Approach 1: Nested Loops (Brute Force)

Same as plain Two Sum. Check every pair.

The idea:

• Pick one number.
• Check it against every other number after it.
• If a pair adds to the target, you found it.

Why it is weak:

• For every number you scan the rest of the array again.
• Time grows as O(n²).
• It ignores the sorted hint completely. Same speed as an unsorted array.

Here is the brute-force code for that idea:

def two_sum(numbers, target):
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1]
    return [-1, -1]

⚡ Approach 2: Binary Search Per Number (Better)

The idea in one line: for each number, search the sorted array for its complement.

The idea:

• For each number, the complement is target - current.
• The array is sorted, so binary search finds that complement fast.
• Binary search finds a value by cutting the sorted list in half each time.

How it works:

• Loop through each number once.
• Binary search for its complement.

Why it is faster:

• Each binary search is O(log n). Total time is O(n log n). Better than brute force.

Why it is weak:

• It searches from one number at a time. It does not use both ends at once.
• The best idea does.

Here is the binary-search-per-number code:

def two_sum(numbers, target):
    for i, value in enumerate(numbers):
        need = target - value
        left, right = i + 1, len(numbers) - 1
        while left <= right:
            mid = (left + right) // 2
            if numbers[mid] == need:
                return [i + 1, mid + 1]
            if numbers[mid] < need:
                left = mid + 1
            else:
                right = mid - 1
    return [-1, -1]

⚡ Approach 3: Two Pointers (Best)

The idea in one line: walk one pointer from each end and let the sorted order tell you which way to move.

The idea:

• Put one pointer at the start and one at the end.
• The left pointer starts small. The right pointer starts large.

How it works:

• Add the two numbers the pointers point to.
• Sum equals the target: you are done. Return both positions.
• Sum too small: move the left pointer right for a bigger number.
• Sum too big: move the right pointer left for a smaller number.

Why it is fast:

• Each step throws away a number that can never be part of the answer.
• The pointers meet after one pass. Time is O(n) and space is O(1).

Here is a dry-run of the two pointers walking on our example.

Steps to Solve

1. Put a left pointer at the first index and a right pointer at the last index.
2. While left is before right, add the two numbers they point to.
3. If the sum equals the target, return the two positions as 1-based.
4. If the sum is too small, move the left pointer one step right.
5. If the sum is too big, move the right pointer one step left.
6. Keep going until the pointers meet.

#include <stdio.h>

void twoSum(int numbers[], int n, int target, int result[]) {
    int left = 0;
    int right = n - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {        // found the pair
            result[0] = left + 1;   // 1-based position
            result[1] = right + 1;
            return;
        } else if (sum < target) {
            left++;                 // need a bigger number
        } else {
            right--;                // need a smaller number
        }
    }
    result[0] = -1;
    result[1] = -1;
}

int main(void) {
    int numbers[] = {2, 7, 11, 15};
    int target = 9;
    int result[2];
    twoSum(numbers, 4, target, result);
    printf("[%d, %d]\n", result[0], result[1]);
    return 0;
}

[1, 2]

#include <iostream>
#include <vector>
using namespace std;

vector<int> twoSum(vector<int>& numbers, int target) {
    int left = 0;
    int right = (int)numbers.size() - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {                 // found the pair
            return {left + 1, right + 1};    // 1-based positions
        } else if (sum < target) {
            left++;                          // need a bigger number
        } else {
            right--;                         // need a smaller number
        }
    }
    return {-1, -1};
}

int main() {
    vector<int> numbers = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = twoSum(numbers, target);
    cout << "[" << result[0] << ", " << result[1] << "]" << endl;
    return 0;
}

[1, 2]

public class TwoSumII {
    public static int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {                       // found the pair
                return new int[] { left + 1, right + 1 };  // 1-based
            } else if (sum < target) {
                left++;                                // need a bigger number
            } else {
                right--;                               // need a smaller number
            }
        }
        return new int[] { -1, -1 };
    }

    public static void main(String[] args) {
        int[] numbers = { 2, 7, 11, 15 };
        int target = 9;
        int[] result = twoSum(numbers, target);
        System.out.println("[" + result[0] + ", " + result[1] + "]");
    }
}

[1, 2]

def two_sum(numbers, target):
    left = 0                       # pointer at the start
    right = len(numbers) - 1       # pointer at the end
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:        # found the pair
            return [left + 1, right + 1]   # 1-based positions
        elif total < target:
            left += 1              # need a bigger number
        else:
            right -= 1             # need a smaller number
    return [-1, -1]


numbers = [2, 7, 11, 15]
target = 9
print(two_sum(numbers, target))

[1, 2]

function twoSum(numbers, target) {
  let left = 0;
  let right = numbers.length - 1;
  while (left < right) {
    const total = numbers[left] + numbers[right];
    if (total === target) {              // found the pair
      return [left + 1, right + 1];      // 1-based positions
    } else if (total < target) {
      left++;                            // need a bigger number
    } else {
      right--;                           // need a smaller number
    }
  }
  return [-1, -1];
}

const numbers = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(numbers, target));

[ 1, 2 ]

Let us walk through the Python version line by line. The two pointer lines are the heart of it.

left = 0 puts the first pointer at the smallest number. right = len(numbers) - 1 puts the second pointer at the largest number. We start at the two ends on purpose. That way we can reach in from both sides.

while left < right: keeps going as long as the pointers have not met. Once they meet, every pair has been checked.

total = numbers[left] + numbers[right] adds the two numbers under the pointers. This single sum tells us which way to move.

if total == target: checks for a match. If it matches, we return [left + 1, right + 1]. We add 1 to each index because the problem wants 1-based positions.

elif total < target: means the sum is too small. So left += 1 moves the left pointer right. Because the array is sorted, the next number is larger. So the sum goes up. That is exactly what we want.

else: means the sum is too big. So right -= 1 moves the right pointer left. The next number is smaller. So the sum goes down. Each move deletes a number that can never work, so we never waste a step.

⏱️ Time and Space Complexity

The brute force uses two loops, so it is O(n²) time. Binary search per number gives O(n log n) time. The two-pointer walk visits each number at most once, so it is O(n) time and O(1) space. No extra memory at all. That is why two pointers wins on a sorted array.

🧩 Key Takeaways

• ✅ A sorted array lets you skip the hash map and use two pointers instead.
• ✅ Start one pointer at each end and add the two values.
• ✅ Too small means move left up. Too big means move right down.
• ✅ Each move deletes a number that cannot be part of the answer, so it runs in O(n).
• ✅ Two pointers use O(1) extra memory, which beats the hash map on space.

🚀 What’s Next?

• 3Sum
• Container With Most Water