Problem: Two Sum (Sorted Array)

Problem Statement

Given a sorted array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.

• Constraint: You must use $O(1)$ extra space.
• Note: The array is already sorted.

Approach: Two Pointers (Opposite Direction)

Since the array is sorted, we can use two pointers starting at both ends.

1. Initialize: left = 0, right = nums.length - 1.
2. Calculate Sum: currentSum = nums[left] + nums[right].
3. Compare:
   • If currentSum == target: Found the pair.
   • If currentSum < target: The sum is too small. To increase it, move the left pointer to the right.
   • If currentSum > target: The sum is too large. To decrease it, move the right pointer to the left.

Java Implementation

public int[] twoSum(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[]{left, right};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[]{-1, -1};
}

Dry Run

Input: nums = [1, 2, 4, 6, 10, 14], target = 12

Complexity Discussion

• Time Complexity: $O(n)$. Each element is visited at most once as the pointers converge.
• Space Complexity: $O(1)$. No extra data structures are used.

Interview Tips

• Always mention why you move the pointers. "Because the array is sorted, moving the left pointer right guarantees a larger or equal sum."
• Clarify if the indices are 0-based or 1-based.