Two Sum Sorted

Problem Link

Two Sum II – Input Array Is Sorted – LeetCode

Problem: Find Two Numbers That Sum to Target in a Sorted Array

Problem Statement

Given a 1-indexed array of integers numbers that is 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 added by one, i.e., return [index1, index2].

• Each input has exactly one solution

• You may not use the same element twice

• Must use constant extra space

Examples

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

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

Example 3
Input: numbers = [-1,0], target = -1
Output: [1,2]

Constraints

• 2 <= numbers.length <= 3 * 10⁴

• -1000 <= numbers[i] <= 1000

• -1000 <= target <= 1000

• The input is sorted in non-decreasing order

• Exactly one solution exists

Intuition

Since the array is sorted, we can use the two-pointer approach starting from both ends:

• Increase the left pointer if the sum is less than target

• Decrease the right pointer if the sum is more than target

• Stop when the sum equals the target

This is more efficient than the brute force approach, which would take O(n²) time.

Approach

1. Initialize two pointers:

   • l = 0 (start of array)

   • r = n - 1 (end of array)

2. While l < r:

   • Compute currSum = numbers[l] + numbers[r]

   • If currSum == target, return [l + 1, r + 1] (1-based indexing)

   • If currSum > target, decrement r

   • If currSum < target, increment l

Code (Java)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;

        while (l < r) {
            int currAns = nums[l] + nums[r];
            if (currAns == target) {
                return new int[]{l + 1, r + 1};
            } else if (currAns > target) {
                r--;
            } else {
                l++;
            }
        }

        return new int[]{-1, -1}; // shouldn't reach here as per constraints
    }
}

Time and Space Complexity

• Time Complexity: O(n)
  Each pointer moves at most once through the array.

• Space Complexity: O(1)
  Only two pointers used, no extra memory required.

Dry Run

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

Initial:

• l = 0, r = 3

• numbers[l] + numbers[r] = 2 + 15 = 17 > 9 → r--

Now:

• l = 0, r = 2

• 2 + 11 = 13 > 9 → r--

Now:

• l = 0, r = 1

• 2 + 7 = 9 → Found → return [1, 2]

Brute Force (For Comparison)

Idea

Check all possible pairs (i, j) and return if numbers[i] + numbers[j] == target.

Code (Java)

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};
    }
}

• Time Complexity: O(n²)

• Space Complexity: O(1)

Conclusion

The two-pointer method efficiently utilizes the sorted property of the input array to achieve O(n) time and O(1) space. It's a clean and optimal solution for problems involving sorted arrays and pair sums.