Find a Pair That Sums to a Target in a Sorted Array
Solve this Problemnums sorted in non-decreasing order and an integer target, find the one pair of elements whose values add up to target, and return their positions as a 1-indexed pair [index1, index2] with index1 < index2. Exactly one valid pair exists.
Since the array is already sorted, you don't need extra space or a second pass — a two-pointer sweep from both ends finds the pair in a single O(n) pass.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
2 ≤ nums.length ≤ 10⁵ - ◆
-10⁶ ≤ nums[i] ≤ 10⁶ - ◆
nums is sorted in non-decreasing order - ◆
Exactly one valid pair exists
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public int[] pairWithTargetSum(int[] nums, int target) { |
| 3 | int left = 0, right = nums.length - 1; |
| 4 | while (left < right) { |
| 5 | int sum = nums[left] + nums[right]; |
| 6 | if (sum == target) { |
| 7 | return new int[]{left + 1, right + 1}; |
| 8 | } else if (sum < target) { |
| 9 | left++; |
| 10 | } else { |
| 11 | right--; |
| 12 | } |
| 13 | } |
| 14 | return new int[]{}; |
| 15 | } |
| 16 | } |
| 17 |
04Set left to index 0 and right to index 4 — the two ends of the sorted array.
Approach & Solutions
Brute Force
BruteCheck every pair of positions with two nested loops. For each i, scan every j after it and test whether nums[i] + nums[j] equals target. Correct, but it never uses the fact that the array is sorted.
O(n²)O(1)1class Solution {
2 public int[] pairWithTargetSum(int[] nums, int target) {
3 for (int i = 0; i < nums.length; i++) {
4 for (int j = i + 1; j < nums.length; j++) {
5 if (nums[i] + nums[j] == target) {
6 return new int[]{i + 1, j + 1};
7 }
8 }
9 }
10 return new int[]{};
11 }
12}Better — Binary Search
BetterFor each index i, binary-search the remainder of the sorted array (from i + 1 to the end) for the exact complement target - nums[i]. This uses the array's sortedness the same way two pointers does, but from a different angle — it re-searches from scratch for every i instead of sliding both ends inward together, so it costs O(n log n) instead of O(n).
O(n log n)O(1)1class Solution {
2 public int[] pairWithTargetSum(int[] nums, int target) {
3 int n = nums.length;
4 for (int i = 0; i < n - 1; i++) {
5 int complement = target - nums[i];
6 int lo = i + 1, hi = n - 1;
7 while (lo <= hi) {
8 int mid = lo + (hi - lo) / 2;
9 if (nums[mid] == complement) {
10 return new int[]{i + 1, mid + 1};
11 } else if (nums[mid] < complement) {
12 lo = mid + 1;
13 } else {
14 hi = mid - 1;
15 }
16 }
17 }
18 return new int[]{};
19 }
20}Optimal — Two Pointers
OptimalSince nums is sorted, put one pointer at the start (left) and one at the end (right). If nums[left] + nums[right] is too small, the only way to grow it is to move left forward to a bigger value. If it's too big, pull right backward to a smaller value. When the sum matches target, return both 1-indexed positions.
O(n)O(1)1class Solution {
2 public int[] pairWithTargetSum(int[] nums, int target) {
3 int left = 0, right = nums.length - 1;
4 while (left < right) {
5 int sum = nums[left] + nums[right];
6 if (sum == target) {
7 return new int[]{left + 1, right + 1};
8 } else if (sum < target) {
9 left++;
10 } else {
11 right--;
12 }
13 }
14 return new int[]{};
15 }
16}