Pair with Target Sum
Easy · Two Pointers · Array · Two Pointers
Problem
You are given an array arr of integers sorted in ascending order and an integer targetSum. Find two different positions whose values add up to targetSum and return their indices [i, j] with i < j (0-based).
If no such pair exists, return [-1, -1]. There is at most one valid pair.
Aim for O(n) time and O(1) extra space: start one pointer at each end and move them toward each other.
Examples
Input: arr = [1,3,5,8,11], targetSum = 13 Output: [2,3]
5 + 8 = 13, at indices 2 and 3.
Input: arr = [-4,0,6,10], targetSum = 2 Output: [0,2]
-4 + 6 = 2. No other pair works: 0 would need a 2.
Input: arr = [2,4,7], targetSum = 20 Output: [-1,-1]
The largest possible sum is 4 + 7 = 11, so no pair reaches 20.
Constraints
- 2 <= len(arr) <= 10^5
- -10^9 <= arr[i] <= 10^9
- arr is sorted in ascending order
- -2 · 10^9 <= targetSum <= 2 · 10^9
- At most one pair of positions sums to targetSum
Approaches
- Hash map of complements — time O(n), space O(n)
Follow-up
If the array were not sorted, the hash map method finds the pair in O(n) time with O(n) space, while sorting first costs O(n log n) and loses the original positions unless you sort (value, index) pairs. Sorted input is what makes the O(1)-space walk possible.
Related problems
Start free on Cariara · Coding problems · System design studio
