DSA-014 · Sorted two-pointer elimination

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.

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.

Sorted array — current endpoints

0: -5
1: -2
2: 0
3: 7
4: 9

State after this step
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.

Sorted array — current endpoints

0: 4

State after this step
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.

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.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 95/20,000 characters

Self-review

I can prove both pointer moves.I use zero-based distinct indices.I verify any valid pair and preserve input.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Two pointers: eliminate with a proof

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-15 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.