Pair with a given sum in a sorted array
Easy · Target 10 minutes · Two pointers · Type asked at
Jane StreetCitadelBloomberg
You are given an array nums sorted in non-decreasing order and an integer
target. Return the indices of the two numbers that add up to target, in
increasing order. Exactly one such pair exists, and you may not use the same element twice.
Examples
| Input | Output | Why |
|---|---|---|
nums = [2, 7, 11, 15], target = 9 | [0, 1] | 2 + 7 = 9. |
nums = [1, 3, 4, 5, 7, 11], target = 10 | [1, 4] | 3 + 7 = 10. The scan starts at 1 + 11 = 12, which is too big, so the right pointer moves in. |
Constraints
- 2 ≤ n ≤ 10⁵
- −10⁹ ≤ nums[i] ≤ 10⁹
- nums is sorted in non-decreasing order
- Exactly one valid pair exists
Hints
Hint 1
A hash map solves this in O(n) time and O(n) space without using the ordering. The ordering is there for a reason: you can do better on space.
Hint 2
Put one pointer at each end. What does it tell you when the two values sum to more than the target?
Hint 3
If the sum is too big, the only way to shrink it is to move the right pointer left, because the left value is already the smallest available.
Dry run on [1,3,4,5,7,11],10
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 4nums10lo31425374115hisum12target10
Pointers at both ends. Target 10.
-
Step 2 / 4nums10lo31425374115hisum12target10
1 + 11 = 12 > 10. nums[5] is too large, so move hi left.
-
Step 3 / 4nums10lo31425374hi115sum8target10
1 + 7 = 8 < 10. nums[0] is too small to pair with anything left, so move lo right.
-
Step 4 / 4nums1031lo425374hi115sum10target10
3 + 7 = 10. Answer [1, 4].
How to think about it
Because the array is sorted, a pointer at each end gives you a decision rule that never needs
to be revisited. Let lo and hi be the two ends and look at
nums[lo] + nums[hi]:
- Too small? Every pair using
lois at most this sum, becausehiis the largest remaining value. Solocan never be part of the answer: move it right. - Too large? By the same argument in reverse,
hiis out: move it left. - Equal? Done.
Each step removes exactly one index from consideration, so the loop runs at most n times. That "one side can be discarded for good" argument is the whole two-pointer pattern; the rest of the problems in this section are variations on which quantity you compare.
Complexity. Time O(n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def pair_sum(nums, target):
lo, hi = 0, len(nums) - 1
while lo < hi:
total = nums[lo] + nums[hi]
if total == target:
return [lo, hi]
if total < target:
lo += 1 # nums[lo] is too small to pair with anything left
else:
hi -= 1 # nums[hi] is too large to pair with anything left
return []#include <vector>
std::vector<int> solve(const std::vector<int>& nums, long long target) {
int lo = 0, hi = static_cast<int>(nums.size()) - 1;
while (lo < hi) {
long long total = static_cast<long long>(nums[lo]) + nums[hi]; // avoid 32-bit overflow
if (total == target) return {lo, hi};
if (total < target) ++lo;
else --hi;
}
return {};
}import java.util.*;
class Solution {
public int[] pairSum(int[] nums, long target) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
long total = (long) nums[lo] + nums[hi]; // avoid 32-bit overflow
if (total == target) return new int[]{lo, hi};
if (total < target) lo++;
else hi--;
}
return new int[0];
}
}function pairSum(nums, target) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const total = nums[lo] + nums[hi];
if (total === target) return [lo, hi];
if (total < target) lo++; // nums[lo] cannot be in the answer
else hi--; // nums[hi] cannot be in the answer
}
return [];
}fn solve(nums: &[i64], target: i64) -> Option<(usize, usize)> {
let (mut lo, mut hi) = (0usize, nums.len() - 1);
while lo < hi {
let total = nums[lo] + nums[hi];
match total.cmp(&target) {
std::cmp::Ordering::Equal => return Some((lo, hi)),
std::cmp::Ordering::Less => lo += 1,
std::cmp::Ordering::Greater => hi -= 1,
}
}
None
}import Data.Array
-- Indices from both ends; the array gives O(1) access by index.
solve :: [Int] -> Int -> Maybe (Int, Int)
solve xs target = go 0 (n - 1)
where
n = length xs
arr = listArray (0, n - 1) xs
go lo hi
| lo >= hi = Nothing
| total == target = Just (lo, hi)
| total < target = go (lo + 1) hi
| otherwise = go lo (hi - 1)
where total = arr ! lo + arr ! hiWhere people lose marks
- Using
<=in the loop condition lets the two pointers land on the same element, which would let you use one number twice. - On a sorted array a hash map is not wrong, but it spends O(n) memory to ignore information you were handed.
- Adding two values near 10⁹ overflows 32-bit integers in C++ and Java. Use a 64-bit type for the sum.
Variants to try
- What changes if the array is not sorted? (Sorting costs O(n log n); a hash map keeps O(n) time.)
- How would you return every distinct pair rather than one? (Move both pointers on a hit and skip duplicates.)
- Three numbers summing to the target: fix one and run this scan on the rest, giving O(n²).
Next problems
Two walls holding the most water
The input is not sorted, but one comparison still rules out an end for good: the shorter wall can never do better.
Open the problem → Medium20 minAll distinct triplets summing to zero
Sort, then fix one value and run the two-pointer scan on the rest. The whole difficulty is in the duplicates.
Open the problem →Write a solution and run it against the real test table.
Keep going
Two walls holding the most water
The input is not sorted, but one comparison still rules out an end for good: the shorter wall can never do better.
Open the problem → Medium20 minAll distinct triplets summing to zero
Sort, then fix one value and run the two-pointer scan on the rest. The whole difficulty is in the duplicates.
Open the problem → Two pointersThe pattern behind it
Two indices walking a sorted or paired structure, each step ruling out one candidate for good.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.