Course4all
Join us on telegram
Home/dsa/Two Pointers/Two Sum II - Input Array Is Sorted

Two Sum II - Input Array Is Sorted

Master this topic with zero to advance depth.

Two Sum II - Input Array Is Sorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Return the indices of the two numbers, [index1, index2], added by one.

Visual Representation

numbers = [2, 7, 11, 15], target = 9 L: index 0 (val 2) R: index 3 (val 15) Sum = 2 + 15 = 17 (> 9) -> Move R left (R=2) L: index 0 (val 2) R: index 2 (val 11) Sum = 2 + 11 = 13 (> 9) -> Move R left (R=1) L: index 0 (val 2) R: index 1 (val 7) Sum = 2 + 7 = 9 (== 9) -> FOUND! [1, 2] (1-indexed)
Easy

Examples

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

The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Approach 1

Level I: Brute Force (Check All Pairs)

Intuition

Try every possible pair of numbers to see if they sum up to the target. While correct, it doesn't leverage the fact that the array is sorted.

⏱ O(N^2)💾 O(1)

Detailed Dry Run

ijnums[i]nums[j]SumTargetMatch?
012799YES! Return [1, 2]
java
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) {
                    return new int[]{i + 1, j + 1};
                }
            }
        }
        return new int[]{-1, -1};
    }

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

⚠️ Common Pitfalls & Tips

O(N^2) complexity is inefficient for large arrays.

Approach 2

Level II: Binary Search

Intuition

For each element at index i, we know the required second element is target - numbers[i]. Since the array is sorted, we can use binary search to find this complement in the sub-array to the right of i (numbers[i+1...n-1]).

⏱ O(N log N)💾 O(1)

Detailed Dry Run

Input: [2, 7, 11, 15], Target: 9

  1. i = 0 (2): Search for 9 - 2 = 7 in [7, 11, 15].
  2. Binary Search found 7 at index 1.
  3. Return [1, 2].
java
public int[] twoSum(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; i++) {
        int low = i + 1, high = numbers.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (numbers[mid] == target - numbers[i]) return new int[]{i + 1, mid + 1};
            if (numbers[mid] < target - numbers[i]) low = mid + 1;
            else high = mid - 1;
        }
    }
    return new int[]{-1, -1};
}

⚠️ Common Pitfalls & Tips

While better than O(N^2), it is still worse than the O(N) Two Pointer approach.

Approach 3

Level III: Optimal (Two Pointer Collision)

Intuition

Since the array is sorted, we can start with two pointers at the extreme ends. If the sum is too small, we move the left pointer right (to increase values). If the sum is too large, we move the right pointer left (to decrease values). This is guaranteed to find the solution in one pass.

⏱ O(N)💾 O(1)

Detailed Dry Run

Input: [2, 7, 11, 15], Target: 9

LRSumAction
0 (2)3 (15)17Sum > 9, move R left (R--)
0 (2)2 (11)13Sum > 9, move R left (R--)
0 (2)1 (7)9Sum == 9, RETURN [1, 2]
java
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int l = 0, r = numbers.length - 1;
        while (l < r) {
            int sum = numbers[l] + numbers[r];
            if (sum == target) return new int[]{l + 1, r + 1};
            if (sum < target) l++;
            else r--;
        }
        return new int[]{-1, -1};
    }

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

⚠️ Common Pitfalls & Tips

Ensure 1-based indexing. This approach only works on sorted arrays.

← Previous QuestionContainer With Most Water
Next Question →3Sum