easyTwo PointersPure DSA~15 min
Transfer Pair Equals Target
A treasury service receives a sorted list of pending transfer amounts. Compliance needs to flag any pair whose total exactly equals a watched amount. Find one such pair using only O(1) extra memory.
Problem
Given an array of integers amounts sorted in ascending order and an integer target, return a pair of indices (i, j) with i < j such that amounts[i] + amounts[j] == target. If no such pair exists, return (−1, −1). If multiple pairs exist, return any one.
Input
An integer n (2 ≤ n ≤ 10^5), the sorted array amounts (each in [-10^9, 10^9]), and an integer target.
Output
A pair of indices (i, j) or (-1, -1).
Constraints
- 2 ≤ n ≤ 100,000
- Array is sorted ascending
- O(1) extra space — no hash maps for this one
Examples
Example 1
Input
amounts = [1, 3, 4, 6, 9], target = 7
Output
(0, 3) or (1, 2)
1+6=7 and 3+4=7. Either pair is acceptable.
Example 2
Input
amounts = [1, 2, 3], target = 100
Output
(-1, -1)
No pair sums to 100.