Beyond HashMaps: Solving "Two Sum II" with the Two-Pointer Technique (Java)

Welcome back to "Mastering DSA with LeetCode"! We previously tackled the classic "Two Sum" problem using a HashMap for an efficient O(N) solution. Today, we're taking on its close relative: "Two Sum II - Input Array Is Sorted" (LeetCode #167).

This problem introduces a crucial twist: the input array is sorted. This seemingly small detail unlocks a powerful new technique – the Two-Pointer pattern – allowing us to solve it with O(1) additional space! Let's explore how this works.

Understanding the Problem:

Given a 1-indexed array of integers numbers that is sorted in non-decreasing order, and an integer target, we need to find two indices index1 and index2 such that numbers[index1] + numbers[index2] == target and index1 < index2. We cannot use the same element twice.

The problem guarantees exactly one valid solution and specifically requires an O(1) additional space solution.

Example:

• Input: numbers = [1, 2, 3, 4], target = 3

• Expected Output: [1, 2]

• Explanation: numbers[0] (1) + numbers[1] (2) == 3. Since the output must be 1-indexed, we return [1, 2].

My Thought Process & Approach (The Two-Pointer Magic):

My first instinct from the original "Two Sum" might be to use a HashMap again. While that would work (O(N) time, O(N) space), the problem's strict O(1) additional space constraint, combined with the sorted array, immediately points to the Two-Pointer pattern.

Here's how it works:

1. Initialize Pointers:

   • Set a left pointer (i in my code) at the beginning of the array (index 0).

   • Set a right pointer (j in my code) at the very end of the array (index n-1).

2. Iterate and Adjust:

   • While left is less than right (meaning our pointers haven't crossed):

     • Calculate the currentSum = numbers[left] + numbers[right].

     • If currentSum == target: We found our pair! Since the problem guarantees a unique solution, we can return the 1-indexed pointers (left + 1, right + 1) immediately.

     • If currentSum > target: The sum is too large. Since the array is sorted, to decrease the sum, we must move the right pointer one step to the left (j--). Moving left would only increase the sum further.

     • If currentSum < target: The sum is too small. To increase the sum, we must move the left pointer one step to the right (i++). Moving right would only decrease the sum further.

3. Return: The loop continues until the pointers cross or the sum equals the target. Due to the problem guarantee, we will always find the solution inside the loop.

This elegantly leverages the sorted nature of the array to find the target sum in a single pass without extra space.

Java Code Implementation:

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        int i =0;
        int j = n-1;
        int[] ans = new int[2];
        while(i<j){
            if(numbers[i] + numbers[j] == target){
                ans[0] = i+1;
                ans[1] = j+1;
                return ans;
            }
            else if(numbers[i] + numbers[j]>target){
                j--;
            }
            else{
                i++;
            }
        }
        return ans;
    }
}

Time and Space Complexity Analysis:

• Time Complexity: O(N)

  • We use a single while loop, where in each iteration either i increases or j decreases. In the worst case, the pointers traverse the entire array once (effectively N steps).

  • Each operation inside the loop (addition, comparison, pointer movement) is constant time.

  • Therefore, the time complexity is linear, O(N). This is optimal as we must look at elements to find the sum.

• Space Complexity: O(1)

  • We only use a few variables (n, i, j, ans) whose space does not depend on the size of the input array numbers.

  • This meets the problem's strict requirement for O(1) additional space, making it a highly optimized solution.