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:
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 (indexn-1
).
Iterate and Adjust:
While
left
is less thanright
(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 theright
pointer one step to the left (j--
). Movingleft
would only increase the sum further.If
currentSum < target
: The sum is too small. To increase the sum, we must move theleft
pointer one step to the right (i++
). Movingright
would only decrease the sum further.
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 eitheri
increases orj
decreases. In the worst case, the pointers traverse the entire array once (effectivelyN
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 arraynumbers
.This meets the problem's strict requirement for O(1) additional space, making it a highly optimized solution.
Subscribe to my newsletter
Read articles from Kaushal Maurya directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
