Two Pointers: Pair with Given Sum in Sorted Array
Fast recall
Quick revision
Core answer
left at index 0 and right at n-1. Move left right when the sum is too small, move right left when too large, and return the pair when it equals the target. This is O(n) versus O(n^2) brute force, in O(1) space.Whether you can exploit sorted order to eliminate candidates directionally and explain why each pointer move is safe
Using nested loops for O(n^2) instead of recognizing the two-pointer opportunity, or not explaining why a move eliminates a range
Explain that sorted order lets each move eliminate an entire range of pairs, not just one
Interview-ready guide
Interview answer
To find a pair with a given sum in a sorted array using two pointers, you start with left at index zero and right at the last index, then move them inward based on the current sum.
If nums at left plus nums at right equals the target, you found the pair. If the sum is less than target, move left forward to increase the sum. If the sum is greater than target, move right backward to decrease it.
You keep doing this until the pointers meet or you find the pair. This runs in O of n time because each pointer moves at most n steps total, and it uses O of one space because you only need two integers. The key insight is that the sorted property lets you make confident decisions.
When the sum is too small, you know that keeping right fixed and trying any left value further left would also be too small, so moving left right eliminates that entire range of pairs in one step. Similarly, when the sum is too large, moving right left eliminates all pairs with current left.
This is why you can scan the whole space in one pass instead of checking every pair with nested loops. Nested loops would take O(n²), while each pointer move here discards a whole range of impossible pairs. If the input is not sorted, a HashMap of seen values is the usual O(n)-time alternative, with O(n) extra space.
Two Pointers: Pair with Given Sum in Sorted Array
Direct Answer
Place left at index 0 and right at n-1. Move left right when the sum is too small, move right left when too large, and return the pair when it equals the target. This is O(n) versus O(n^2) brute force, in O(1) space.
Deep Dive & Architecture
Put one pointer on the smallest value and one on the largest. Compare their sum with the target. If it is too small, only a larger left value can help; if it is too large, only a smaller right value can help.
Worked example: [1, 2, 4, 6, 10], target 8
1 + 10 = 11, so move right leftward. 1 + 6 = 7, so move left rightward. 2 + 6 = 8, so the pair is found.
The moves discard complete sets of candidates. When 1 + 10 is too large, pairing 10 with any remaining value greater than 1 cannot improve it. When 1 + 6 is too small, pairing 1 with any value no larger than 6 cannot reach 8. This proof depends on the array being sorted.
The scan is O(n) time and O(1) extra space. A nested-loop solution is O(n²). For unsorted input, use a hash set in O(n) expected time and O(n) space, or sort a copy in O(n log n) when original indexes are not required.
Use long for the sum if two int values could overflow. Also clarify whether the answer should return values, indexes, one pair, or every distinct pair.
Code Example
public class PairSumFinder {
public int[] findPairWithSum(int[] nums, int target) {
if (nums == null || nums.length < 2) return new int[]{-1, -1};
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) return new int[]{nums[left], nums[right]};
else if (sum < target) left++; // need larger sum
else right--; // need smaller sum
}
return new int[]{-1, -1};
}
public static void main(String[] args) {
int[] nums = {1, 3, 5, 7, 9, 11};
int[] r = new PairSumFinder().findPairWithSum(nums, 14);
System.out.println("Pair: [" + r[0] + ", " + r[1] + "]"); // [3, 11]
}
}
Common Mistakes & Pitfalls
- Using nested loops: O(n^2) brute force shows you missed the two-pointer opportunity.
- Not explaining the invariant: saying 'move left if too small' without explaining that it eliminates all pairs with the current right misses the deeper point.
- Forgetting to check sorted: clarify the input is sorted, or whether sorting first is acceptable.
- Returning indices instead of values (or vice versa): read the problem carefully.
Check your understanding
Answer these without looking back at the article.
- What is the two-pointer technique and when do you use it?
- How do you check if a string is a palindrome using two pointers?
- How do you remove duplicates from a sorted array in-place?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.