Problem

This problem is similar to Two Sum, only difference is input array is now sorted.

Detailed problem

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. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Examples

Example 1:

1
2
3

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

1
2
3

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

1
2
3

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Naive

Here is the naive approach:

  1. Loop through the array with two nested loops:
    • The outer loop iterates through every element (i).
    • The inner loop iterates through the elements after i (j).
  2. Compute the sum of numbers[i] and numbers[j].
  3. If the sum equals the target, return [i + 1, j + 1] (1-based indexing).
  4. Since the guarantee is that there is exactly one solution, you can exit as soon as the result is found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (numbers[i] + numbers[j] == target) {
                    return new int[]{i + 1, j + 1};
                }
            }
        }

        // This will never be reached because a solution is guaranteed.
        throw new IllegalArgumentException("No solution found");
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n: int = len(numbers)
        
        for i in range(n):
            for j in range(i + 1, n):
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]

        # This line won't be reached as a solution is always guaranteed.
        raise ValueError("No solution exists")

Complexity

  • ⏰ Time complexity: O(n^2) duet o nested loop
  • 🧺 Space complexity: O(1)

Method 2 - Using Binary Search

As the array is sorted, we can use binary search to find complement of the number (complement = target - number).

  1. Loop through the array using a single pointer i starting at the beginning. This pointer selects the first number numbers[i].
  2. Compute the required value that needs to pair with numbers[i] to form the target sum: required = target - numbers[i]
  3. Use binary search to locate the required value in the portion of the array to the right of i, i.e., numbers[i + 1:].
    • Binary search efficiently finds the required value or determines that it doesn’t exist in O(log n) time.
  4. If the required value is found, return the indices [i + 1, index of required + 1] (1-based indexing).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;

        for (int i = 0; i < n; i++) {
            int required = target - numbers[i];
            
            // Perform binary search in the right portion of the array
            int low = i + 1;
            int high = n - 1;
            
            while (low <= high) {
                int mid = (low + high) / 2;
                
                if (numbers[mid] == required) {
                    return new int[]{i + 1, mid + 1};  // Return 1-based indices
                } else if (numbers[mid] < required) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }

        // Guaranteed solution, so this won't execute
        throw new IllegalArgumentException("No solution found");
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n: int = len(numbers)
        
        for i in range(n):
            required: int = target - numbers[i]
            
            # Binary search for the "required" value in the right portion of the array
            low: int = i + 1
            high: int = n - 1
            
            while low <= high:
                mid: int = (low + high) // 2
                if numbers[mid] == required:
                    return [i + 1, mid + 1]  # Return 1-based indices
                elif numbers[mid] < required:
                    low = mid + 1
                else:
                    high = mid - 1
        
        # Guaranteed solution, so this won't execute
        raise ValueError("No solution exists")

Complexity

  • ⏰ Time complexity: O(n * log n). The outer loop runs n times, and for each iteration, binary search (O(log n)) is performed on the remaining portion of the array.
  • 🧺 Space complexity: O(1). No extra data structures are used; everything is computed in-place.

Method 3 - Two Pointer technique

To solve this problem, we can use two points to scan the array from both sides. This is very similar to Two Sum#Method 3 - Using Sorting and 2 Pointer Approach.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
	public int[] twoSum(int[] numbers, int target) {	
		int left = 0;
		int right = numbers.length - 1;
	
		while (left<right) {
			int currSum = numbers[left] + numbers[right];
			if (currSum<target) {
				++left;
			} else if (currSum > target) {
				right--;
			} else {
				return new int[] {
					left + 1, right + 1
				};
			}
		}
	
		return new int[]{-1, -1};
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l: int = 0
        r: int = len(numbers) - 1
        
        while l < r:
            sum: int = numbers[l] + numbers[r]
            
            if sum == target:
                return [l + 1, r + 1]
            elif sum < target:
                l += 1
            else:
                r -= 1
        
        # This line won't be reached as a solution is always guaranteed.
        return [-1, -1]

Complexity

  • ⏰ Time complexity: O(n) because the two pointers traverse the array at most once.
  • 🧺 Space complexity: O(1) as no extra data structures are used.