DSA-014 · FOCUSED PRACTICE
Two Sum in a Sorted Array
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 5011 deterministic checks. Learner drafts are not executed.
Understand the problem
Find two distinct positions in a nondecreasing integer array whose values add to a target.
- nums is non-null, nondecreasing, and has 0–100,000 signed int values. target is any signed long. Sortedness is a precondition; no sorting or validation is performed.
- Return any int[]{i,j} with zero-based indices 0≤i<j<n and exact sum target; return an empty int[] if no pair exists. There may be multiple valid pairs, and no lexicographic tie rule is promised.
- Preserve nums. Compute sums in long before addition; targets outside the sum range of two ints simply have no solution. A single occurrence cannot be reused.
Examples
Input:
nums=[1,3,5,8], target=9
Output:[0,3]1+8 is nine using distinct zero-based positions.
Input:
nums=[2,2], target=4
Output:[0,1]Equal values are valid when they occupy different positions.
Before you start
- Array indexing and inclusive pointer bounds
- Loop invariants and Java value versus reference semantics
Recognize the structure
Sorted order lets one failed endpoint sum eliminate a whole row or column of candidate pairs. The comparison must tell you which boundary can no longer participate in any solution.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 95/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
What is the largest partner available for the current left value?
Hint 2
If even that sum is too small, can left occur in a solution?
Hint 3
Move left on small sums and right on large sums.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Enumerate index pairs
Try all i<j with a long sum. For [1,3,5,8], target 9, pairs (0,1) and (0,2) miss, while (0,3) succeeds. For a missing target, all n(n-1)/2 pairs are inspected. This is O(n²) time and O(1) workspace, and serves as the existence oracle.
Improve the baseline
Start with widest bounds
All possible pairs initially use indices between left=0 and right=n-1.
Eliminate a small left endpoint
If nums[left]+nums[right]<target, replacing right by any smaller allowed index can only lower the sum. No pair using this left endpoint can work; increment left.
Eliminate a large right endpoint
If the sum is too large, replacing left by a larger allowed index can only raise it. Decrement right. Return immediately on equality; stop when the endpoints meet.
Why it is correct
Candidate invariant
If a solution exists and none has been returned, there is a solution with both indices in the remaining interval. Initially this includes every legal pair.
Safe elimination
A too-small sum rules out every remaining pair using left. A too-large sum rules out every remaining pair using right. Each chosen move removes only impossible candidates.
Termination and absence
The interval shrinks by one per failed comparison. At left>=right it contains fewer than two positions, so no pair remains; returning [] is justified, not merely a scan timeout.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
public final class Solution {
public static int[] twoSum(int[] nums, long target) {
int left = 0, right = nums.length - 1;
while (left < right) {
long sum = (long) nums[left] + nums[right];
if (sum == target) return new int[]{left, right};
if (sum < target) left++;
else right--;
}
return new int[0];
}
public static int[] baseline(int[] nums, long target) {
for (int i = 0; i < nums.length; i++) for (int j = i + 1; j < nums.length; j++)
if ((long) nums[i] + nums[j] == target) return new int[]{i, j};
return new int[0];
}
}
Read the meaningful blocks
Widen before adding
(long) nums[left]+nums[right] computes the mathematical sum. Casting an already overflowed int result would be too late.
left<right
This is both a bounds guard and the distinct-position requirement.
Any pair
Tests must verify index bounds and the sum, rather than demanding a particular pair when alternatives exist.
Complexity
O(n) time and O(1) auxiliary space, excluding the constant-sized returned pair. Each failed comparison discards one endpoint.
The brute-force baseline uses O(n²) time and O(1) space. Sorting an unsorted input would lose direct original indices unless those indices were stored with values.
Exact-state walkthroughs
Reveal normal and boundary traces
Eliminate small and large endpoint sums
Input: {"nums":[-5,-2,0,7,9],"target":5} · Result: [1,3]
Step 1 of 5: Begin with every index pair available.
Any solution not yet returned has both indices inside the remaining interval.
- 0: -5
- 1: -2
- 2: 0
- 3: 7
- 4: 9
| Variable | Value |
|---|---|
| values | [-5,-2,0,7,9] |
| left | 0 |
| right | 4 |
| target | 5 |
See the affected Java block
1 public final class Solution { 2 public static int[] twoSum(int[] nums, long target) { 3 int left = 0, right = nums.length - 1; 4 while (left < right) { 5 long sum = (long) nums[left] + nums[right]; 6 if (sum == target) return new int[]{left, right}; 7 if (sum < target) left++; 8 else right--; 9 } 10 return new int[0]; 11 } 12 public static int[] baseline(int[] nums, long target) { 13 for (int i = 0; i < nums.length; i++) for (int j = i + 1; j < nums.length; j++) 14 if ((long) nums[i] + nums[j] == target) return new int[]{i, j}; 15 return new int[0]; 16 } 17 } 18
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin with every index pair available.
Any solution not yet returned has both indices inside the remaining interval.
- values
[-5,-2,0,7,9]- left
0- right
4- target
5
- Discard an endpoint that cannot belong to a remaining solution.
Even its largest partner is too small, so oldLeft is impossible.
- values
[-5,-2,0,7,9]- oldLeft
0- oldRight
4- sum
4- left
1- right
4
- Discard an endpoint that cannot belong to a remaining solution.
Even its smallest partner is too large, so oldRight is impossible.
- values
[-5,-2,0,7,9]- oldLeft
1- oldRight
4- sum
7- left
1- right
3
- The two distinct endpoints meet the target.
Both indices are legal and their exact sum equals the target.
- values
[-5,-2,0,7,9]- left
1- right
3- sum
5
- Return the contract result.
All required values have been finalized under the declared contract.
- result
[1,3]
No pair with one position
Input: {"nums":[4],"target":8} · Result: []
Step 1 of 2: Begin with every index pair available.
Any solution not yet returned has both indices inside the remaining interval.
- 0: 4
| Variable | Value |
|---|---|
| values | [4] |
| left | 0 |
| right | 0 |
| target | 8 |
See the affected Java block
1 public final class Solution { 2 public static int[] twoSum(int[] nums, long target) { 3 int left = 0, right = nums.length - 1; 4 while (left < right) { 5 long sum = (long) nums[left] + nums[right]; 6 if (sum == target) return new int[]{left, right}; 7 if (sum < target) left++; 8 else right--; 9 } 10 return new int[0]; 11 } 12 public static int[] baseline(int[] nums, long target) { 13 for (int i = 0; i < nums.length; i++) for (int j = i + 1; j < nums.length; j++) 14 if ((long) nums[i] + nums[j] == target) return new int[]{i, j}; 15 return new int[0]; 16 } 17 } 18
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin with every index pair available.
Any solution not yet returned has both indices inside the remaining interval.
- values
[4]- left
0- right
0- target
8
- Return the contract result.
All required values have been finalized under the declared contract.
- result
[]
Test the contract
Input:
nums=[], target=0
Output:[]No pair.
Input:
nums=[4], target=8
Output:[]An index cannot pair with itself.
Input:
nums=[-5,-2,0,7], target=5
Output:[1,3]Negative values preserve sorted elimination.
Input:
nums=[2147483647,2147483647], target=4294967294
Output:[0,1]Long sum.
Common mistakes and counterexamples
Move right after a small sum
Counterexample: [1,3,5,8], target 9 already has the largest partner for left.
Discard left, not the only larger partner that could help.
Reuse one index
Counterexample: [4], target 8 must return [].
Require left<right.
Add as int
Counterexample: [2147483647,2147483647] targets 4294967294, not -2.
Cast an operand to long before addition.
Follow-ups
Return all value pairs.
After finding a match, skip duplicates at both ends and record the value pair once. If the output is index pairs instead, duplicate runs can produce quadratically many answers.
Handle unsorted original indices.
Use a hash map or sort value/index records. State memory cost and keep original positions; a sorted clone of values alone is insufficient.
Choose a deterministic tie rule.
Any-pair correctness does not imply the lexicographically first result. Define the desired index ordering and adapt duplicate handling or use per-index binary search with a suitable proof.