Two Sum II - Input Array Is Sorted

Easytwo-pointersarray
Category: Two Pointers
Companies that ask this question:
AmazonGoogleFacebookMicrosoft
LeetCode →NeetCode →

Approach

Two Sum II - Input Array Is Sorted

Problem Statement

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

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.

Example 2

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

Example 3

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

Intuition

Since the array is already sorted, we can use two pointers to efficiently find the pair. Unlike the original Two Sum problem which requires a hash map, the sorted property allows us to use O(1) space.

The key insight is:

  • If the current sum is too small, we need to increase it → move left pointer right
  • If the current sum is too large, we need to decrease it → move right pointer left
  • If we find the exact sum → return the indices

Pattern Recognition

This is a classic Two Pointers pattern problem with these characteristics:

  • Sorted input
  • Need to find a pair satisfying a condition
  • Can eliminate half the search space in each decision
  • O(n) time, O(1) space solution exists

Approach

  1. Initialize Pointers: Start with left = 0 and right = length - 1
  2. Calculate Sum: Get currentSum = numbers[left] + numbers[right]
  3. Decision Logic:
    • If currentSum == target: Return [left + 1, right + 1] (1-indexed)
    • If currentSum < target: Move left++ (need larger number)
    • If currentSum > target: Move right-- (need smaller number)
  4. Repeat: Continue until we find the answer (guaranteed to exist)

Edge Cases

  • Array with exactly 2 elements (minimum size)
  • Negative numbers in the array
  • Target is negative
  • Answer uses first and last indices

Complexity Analysis

  • Time Complexity: O(n) where n is the length of the array
    • Each pointer moves at most n times
    • Single pass through the array
  • Space Complexity: O(1)
    • Only using two pointer variables
    • No additional data structures needed

Solution

java
1class Solution {
2    public int[] twoSum(int[] numbers, int target) {
3        // Initialize two pointers at both ends
4        int left = 0;
5        int right = numbers.length - 1;
6
7        // Continue until we find the answer
8        while (left < right) {
9            int currentSum = numbers[left] + numbers[right];
10
11            if (currentSum == target) {
12                // Found the pair! Return 1-indexed positions
13                return new int[]{left + 1, right + 1};
14            } else if (currentSum < target) {
15                // Sum too small, need larger number
16                left++;
17            } else {
18                // Sum too large, need smaller number
19                right--;
20            }
21        }
22
23        // Should never reach here per problem constraints
24        return new int[]{-1, -1};
25    }
26}
27
Loading visualizer...