Two pointers for a pair sum in a sorted array
Trace a sorted two-sum search in C#, prove which pairs each move rules out, and catch the duplicate-index and overflow cases that break the proof.
Six ledger adjustments, sorted by amount, read [-7, -2, 1, 5, 9, 14]. You need two distinct entries that add up to 10. A double loop can try all 15 pairs. A search from the two ends finds the answer in four additions. The interesting part is the first addition, -7 + 14 = 7. In one comparison it finishes everything you ever need to know about the entry at index 0.
The same question on 200,000 entries has 19,999,900,000 possible pairs. Reducing the cost of an individual comparison will do little for a loop that visits all of them. The sorted order gives each comparison a much bigger job.
Put a finger on the smallest remaining value and another on the largest. Their sum is the largest sum you can make with the left value and the smallest sum you can make with the right value. Which of those statements you need depends on where the sum falls relative to the target.
In the ledger, -7 plus the most generous partner available, 14, still comes up short. Trying -7 with 9 or 5 can only make things worse. Move the left index up by one. The next sum, -2 plus 14, overshoots. Now 14 fails even with the smallest partner still available. Move the right index down by one.
-
Start
- -7
- -2
- 1
- 5
- 9
- 14
Sum 7. Drop -7 and all five pairs it could make.
-
Advance left index
- -7
- -2
- 1
- 5
- 9
- 14
Sum 12. Drop 14 and its four remaining pairs.
-
Lower right index
- -7
- -2
- 1
- 5
- 9
- 14
Sum 7. Drop -2 and its three remaining pairs.
-
Advance left index
- -7
- -2
- 1
- 5
- 9
- 14
Sum 10. Return zero-based indices 2 and 4.
Notice what survived the second comparison. The pair (-7, 14) was already gone. Each move discards only pairs that are still candidates, so the next search interval sits entirely inside the last one. The values can cross zero without changing any of this. Sorting makes the sums move predictably when you hold one endpoint and vary the other.
Before each comparison, every possible answer that has survived so far has both indices between the two pointers. A pointer moves only after every remaining pair using that endpoint has failed.
Here is a version for callers that may supply an array with no match. A nullable pair represents that outcome. The input is in nondecreasing order, equal values may repeat, and indices start at zero. If several pairs qualify, any one is acceptable.
static (int Left, int Right)? FindPair(int[] sorted, int target)
{
int left = 0;
int right = sorted.Length - 1;
while (left < right)
{
long sum = (long)sorted[left] + sorted[right];
if (sum == target)
return (left, right);
if (sum < target)
left++;
else
right--;
}
return null;
}The strict loop condition encodes the word "distinct." With [2, 5, 12] and target 10, the pointers can meet on the 5. At that point there is one entry left, so the search is over. Two different entries can share the same value. For [2, 5, 5, 12] the result is (1, 2). Skipping duplicate values before checking the sum would risk discarding the answer.
The cast in the addition belongs before the plus sign. On [1, 2, 2147483647] with target 3, the first sum should be 2,147,483,648. That is too large, so the right pointer should move. Adding two int operands in an unchecked context wraps that sum to a negative number and sends the left pointer the wrong way. Assigning that wrapped value to a long afterward preserves the mistake. In a checked context the narrow addition throws instead. C# arithmetic operators
The initial distance between the pointers is n - 1. After every failed comparison the distance shrinks by exactly one. Even if the input has no solution, an array of 200,000 entries requires at most 199,999 comparisons of endpoint sums. This bound counts work and says nothing about how many milliseconds a particular machine takes. The scan therefore takes O(n) time. Two indices and one running sum take O(1) auxiliary space.
A binary search for each element's complement would also use the sort order. Take a candidate at index 17 and search the suffix after 17 for its partner. That never reuses an element and keeps the indices intact. It does start a fresh search for each candidate, though. The two-pointer version remembers a piece of information across searches. Once 14 proved too large for -2, it will still be too large when the next left value rises to 1. There is no reason to include that part of the suffix again.
The precondition earns that saving. Suppose the ledger arrives as [1, 8, 2, 3] and the target is 10. The same loop sees 1 + 3, discards 1, then sees 8 + 3 and discards 3. That happens to leave the answer. Change the input to [2, 8, 1, 3] and the first step discards the 2 you need. Sorting a copy repairs the ordering and costs O(n log n) time. If a caller needs the indices in the original ledger, carry each original index through the sort or look up complements in a dictionary during one pass. Sorting only the amounts silently changes what the result indices mean.
Change the question to "How many pairs sum to at most 10?" The same reasoning lets you count many successful pairs at once. If the two endpoints fit, the left endpoint also fits with every other remaining value. There are exactly right - left such partners. Count them, then retire the left endpoint. If the sum is too large, retire only the right endpoint. Every counted pair belongs to a unique left index.
static long CountPairsAtMost(int[] sorted, int limit)
{
long count = 0;
int left = 0;
int right = sorted.Length - 1;
while (left < right)
{
if ((long)sorted[left] + sorted[right] <= limit)
{
count += right - left;
left++;
}
else
{
right--;
}
}
return count;
}On the six ledger entries, -7 contributes five pairs. The sum with -2 and 14 is too high, so drop 14. Then -2 contributes three pairs, and 1 contributes two, for ten in all. The pair (1, 9) belongs in that total because equality is allowed. Using a strict comparison would lose it. For 100,000 zero entries and a limit of zero, all 4,999,950,000 pairs qualify, which explains the wide result type even when every amount fits comfortably in an int.
There is a useful small-scale check for both versions. Enumerate every i < j on a short sorted array, adding in long. For an exact match, verify the returned indices are distinct and their values sum to the target. For the limit variant, compare the actual counts. Mix repeated amounts with a target just below the smallest possible sum. Those inputs exercise a different exit from the easy case where the endpoints match on the first comparison. The same idea of running a straightforward answer beside a faster one works for other data structures. Property-based testing in C#
Katabench's Two Sum II exercise guarantees a solution and asks for its zero-based indices in ascending order. The plain Two Sum exercise removes the ordering promise. Try the same tests against both and inspect what happens to the time and allocation measurements when the input grows. C# coding challenges · Reading the performance results
Practice what you just read
- Open in the editor: Two Sum II (Sorted Input)
Algorithm Easy Free, no account needed
Two Sum II (Sorted Input)
Two Sum again - but the array is sorted, and that changes everything.
- Open in the editor: Two Sum
Algorithm Easy Free, no account needed
Two Sum
Find the indices of the two numbers that add up to a target.
More like this: C# coding challenges →