Two Sum II (LeetCode
Learn how to solve Two Sum II using brute force, binary search, HashMap, and the optimal two-pointer approach. Includes intuition, dry runs, Java code, correctness proof, complexity analysis, edge cases, interview tips, and production applications.
Introduction
Two Sum II — Input Array Is Sorted is one of the best introductory problems for learning the Two Pointer pattern.
It is frequently discussed in coding interviews because it tests whether you can use the sorted property of an array to improve a brute-force solution.
This problem evaluates your understanding of:
- Sorted arrays
- Opposite-direction pointers
- Search-space elimination
- Index handling
- One-based indexing
- Time and space optimization
- Algorithm correctness
- Integer overflow
The key insight is:
Because the array is sorted, the sum tells us exactly which pointer must move.
If the current sum is too small:
Move the left pointer right
If the current sum is too large:
Move the right pointer left
This reduces the solution from quadratic time to linear time.
Problem Statement
Given a 1-indexed sorted integer array numbers, find two distinct elements whose sum equals target.
Return their indexes as:
[index1, index2]
where:
1 <= index1 < index2 <= numbers.length
The problem guarantees exactly one valid answer.
You must use constant additional space.
Example 1
Input
numbers = [2,7,11,15]
target = 9
Output
[1,2]
Explanation:
numbers[0] + numbers[1]
=
2 + 7
=
9
The array uses zero-based indexing internally, but the required result uses one-based indexing.
Therefore:
0 + 1 = 1
1 + 1 = 2
Result:
[1,2]
Example 2
Input
numbers = [2,3,4]
target = 6
Output
[1,3]
Explanation:
2 + 4 = 6
Example 3
Input
numbers = [-1,0]
target = -1
Output
[1,2]
Explanation:
-1 + 0 = -1
Important Problem Guarantees
The classic problem guarantees:
- The array is sorted in non-decreasing order.
- Exactly one solution exists.
- The same element cannot be used twice.
- The answer uses one-based indexing.
- Constant extra space is expected.
These guarantees influence the implementation.
What Is the Two Pointer Technique?
The Two Pointer technique maintains two indexes and moves them according to the relationship between the current state and the target.
For this problem:
Left Pointer → Starts at the beginning
Right Pointer → Starts at the end
Visual:
L R
↓ ↓
2 3 4 7 11 15
At every step:
sum = numbers[left] + numbers[right]
Then:
sum == target → Return answer
sum < target → Move left right
sum > target → Move right left
Why Does the Sorted Array Matter?
Suppose:
numbers[left] + numbers[right] < target
The sum is too small.
Moving the right pointer left would select an equal or smaller value and make the sum even smaller.
Therefore, the only useful move is:
left++
Similarly, if:
numbers[left] + numbers[right] > target
the sum is too large.
Moving the left pointer right would select an equal or larger value and make the sum even larger.
Therefore, the useful move is:
right--
The sorted property makes pointer movement logically valid.
Approach 1 — Brute Force
Core Idea
Check every possible pair.
For each index i, compare it with every later index j.
If:
numbers[i] + numbers[j] == target
return the one-based indexes.
Java Code — Brute Force
public class TwoSumTwoBruteForce {
public int[] twoSum(
int[] numbers,
int target) {
for (int first = 0;
first < numbers.length;
first++) {
for (int second = first + 1;
second < numbers.length;
second++) {
if (numbers[first]
+ numbers[second]
== target) {
return new int[]{
first + 1,
second + 1
};
}
}
}
throw new IllegalArgumentException(
"No valid pair exists");
}
}
Brute Force Complexity
| Complexity | Value |
|---|---|
| Time | O(n²) |
| Space | O(1) |
The solution uses constant memory but checks too many unnecessary pairs.
Why Brute Force Is Inefficient
For an array of length n, the number of possible pairs is:
n × (n - 1) / 2
For:
n = 100,000
this is approximately:
5 billion pairs
The sorted property should be used to eliminate large portions of the search space.
Approach 2 — Binary Search
Core Idea
For every element:
current = numbers[i]
calculate the required complement:
complement = target - current
Because the array is sorted, search for the complement using binary search in the portion after index i.
Example
numbers = [2,7,11,15]
target = 9
At index 0:
current = 2
complement = 9 - 2 = 7
Binary search for 7 from index 1 onward.
Found at index 1.
Return:
[1,2]
Java Code — Binary Search
public class TwoSumTwoBinarySearch {
public int[] twoSum(
int[] numbers,
int target) {
for (int first = 0;
first < numbers.length - 1;
first++) {
long complement =
(long) target
- numbers[first];
int second =
binarySearch(
numbers,
first + 1,
numbers.length - 1,
complement);
if (second != -1) {
return new int[]{
first + 1,
second + 1
};
}
}
throw new IllegalArgumentException(
"No valid pair exists");
}
private int binarySearch(
int[] numbers,
int left,
int right,
long target) {
while (left <= right) {
int middle =
left
+ (right - left) / 2;
if (numbers[middle]
== target) {
return middle;
}
if (numbers[middle]
< target) {
left =
middle + 1;
} else {
right =
middle - 1;
}
}
return -1;
}
}
Binary Search Complexity
| Complexity | Value |
|---|---|
| Time | O(n log n) |
| Space | O(1) |
This is better than brute force but not optimal.
The Two Pointer solution completes the search in linear time.
Approach 3 — HashMap
Core Idea
Use a map to store previously visited values and their indexes.
For every value:
complement = target - current value
Check whether the complement has already been seen.
Java Code — HashMap
import java.util.HashMap;
import java.util.Map;
public class TwoSumTwoHashMap {
public int[] twoSum(
int[] numbers,
int target) {
Map<Integer, Integer> indexes =
new HashMap<>();
for (int index = 0;
index < numbers.length;
index++) {
int complement =
target - numbers[index];
if (indexes.containsKey(
complement)) {
return new int[]{
indexes.get(complement)
+ 1,
index + 1
};
}
indexes.put(
numbers[index],
index);
}
throw new IllegalArgumentException(
"No valid pair exists");
}
}
HashMap Complexity
| Complexity | Value |
|---|---|
| Time | O(n) average |
| Space | O(n) |
Although the time is linear, the approach ignores the sorted property and uses additional memory.
The problem explicitly encourages constant extra space.
Approach 4 — Optimal Two Pointer Solution
Core Idea
Initialize:
int left = 0;
int right = numbers.length - 1;
At every step:
sum = numbers[left] + numbers[right]
Then:
- Return when the sum matches.
- Increase
leftwhen the sum is too small. - Decrease
rightwhen the sum is too large.
Java Code — Optimal Solution
public class TwoSumTwo {
public int[] twoSum(
int[] numbers,
int target) {
int left = 0;
int right =
numbers.length - 1;
while (left < right) {
long sum =
(long) numbers[left]
+ numbers[right];
if (sum == target) {
return new int[]{
left + 1,
right + 1
};
}
if (sum < target) {
left++;
} else {
right--;
}
}
throw new IllegalArgumentException(
"No valid pair exists");
}
}
LeetCode-Style Implementation
Because LeetCode guarantees a solution, the method may return an empty array if no result is found.
public class Solution {
public int[] twoSum(
int[] numbers,
int target) {
int left = 0;
int right =
numbers.length - 1;
while (left < right) {
int sum =
numbers[left]
+ numbers[right];
if (sum == target) {
return new int[]{
left + 1,
right + 1
};
}
if (sum < target) {
left++;
} else {
right--;
}
}
return new int[0];
}
}
For production code, using long for the sum is safer.
Two Pointer Flow
graph TD
Initialize_Left_and_Right["Initialize Left and Right"] --> Calculate_Sum["Calculate Sum"]
Calculate_Sum["Calculate Sum"] --> Sum_Equals_Target["Sum Equals Target?"]
Sum_Equals_Target["Sum Equals Target?"] --> No["No"]
No["No"] --> Sum_Too_Small["Sum Too Small?"]
Sum_Too_Small["Sum Too Small?"] --> Repeat_Until_Left_Meets_Righ["Repeat Until Left Meets Right"]
Detailed Dry Run
Input:
numbers = [2,3,4,7,11,15]
target = 9
Initial state:
left = 0
right = 5
Values:
numbers[left] = 2
numbers[right] = 15
Sum:
2 + 15 = 17
Since:
17 > 9
move the right pointer left.
Iteration 2
left = 0
right = 4
Values:
2 and 11
Sum:
13
Since:
13 > 9
move right again.
Iteration 3
left = 0
right = 3
Values:
2 and 7
Sum:
9
Match found.
Return one-based indexes:
[1,4]
Dry Run Table
| Left Index | Left Value | Right Index | Right Value | Sum | Action |
|---|---|---|---|---|---|
| 0 | 2 | 5 | 15 | 17 | Move right |
| 0 | 2 | 4 | 11 | 13 | Move right |
| 0 | 2 | 3 | 7 | 9 | Return [1,4] |
Dry Run with a Sum That Is Too Small
Input:
numbers = [1,2,3,4,6,8]
target = 10
Initial:
left = 0 → 1
right = 5 → 8
Sum:
1 + 8 = 9
Too small.
Move left:
left = 1 → 2
New sum:
2 + 8 = 10
Return:
[2,6]
Visual Pointer Movement
Target = 10
L R
↓ ↓
1 2 3 4 6 8
1 + 8 = 9
Sum too small
Move L right
L R
↓ ↓
1 2 3 4 6 8
2 + 8 = 10
Match found
Why Moving the Left Pointer Is Correct
Assume:
numbers[left] + numbers[right] < target
Because the array is sorted:
numbers[left + 1] >= numbers[left]
To increase the sum, move left right.
What about pairing numbers[left] with a smaller right-side value?
Any index j < right satisfies:
numbers[j] <= numbers[right]
Therefore:
numbers[left] + numbers[j]
<=
numbers[left] + numbers[right]
<
target
So numbers[left] cannot form the target with any remaining value.
It is safe to discard it.
Why Moving the Right Pointer Is Correct
Assume:
numbers[left] + numbers[right] > target
Because the array is sorted:
numbers[right - 1] <= numbers[right]
To reduce the sum, move right left.
What about pairing numbers[right] with a larger left-side value?
Any index i > left satisfies:
numbers[i] >= numbers[left]
Therefore:
numbers[i] + numbers[right]
>=
numbers[left] + numbers[right]
>
target
So numbers[right] cannot form the target with any remaining value.
It is safe to discard it.
Correctness Proof
We prove that the algorithm returns the valid pair without eliminating it incorrectly.
Assume the current pointers are:
left
right
Case 1 — Current Sum Is Too Small
numbers[left] + numbers[right] < target
Since numbers[right] is the largest value in the current search range, pairing numbers[left] with any other available value cannot produce a larger sum.
Therefore, numbers[left] cannot belong to the valid answer.
Moving left right does not remove the correct pair.
Case 2 — Current Sum Is Too Large
numbers[left] + numbers[right] > target
Since numbers[left] is the smallest value in the current search range, pairing numbers[right] with any other available value cannot produce a smaller sum.
Therefore, numbers[right] cannot belong to the valid answer.
Moving right left does not remove the correct pair.
Case 3 — Current Sum Equals the Target
The two distinct indexes form the required solution.
Therefore, returning them is correct.
Because every pointer move safely removes an impossible value, the valid answer remains inside the search interval until it is found.
Loop Invariant
A useful loop invariant is:
At the beginning of every iteration, if a valid pair exists, at least one valid pair lies inside the current interval from
lefttoright.
Each pointer movement preserves this invariant by eliminating only an index that cannot participate in a valid pair.
When the current sum equals the target, the solution is returned.
Complexity Analysis
The left pointer moves only to the right.
The right pointer moves only to the left.
Each pointer moves at most n - 1 times.
Therefore:
| Complexity | Value |
|---|---|
| Time | O(n) |
| Space | O(1) |
Why the Complexity Is Not O(n²)
Although two pointers are used, they are not nested loops.
Both pointers move monotonically toward each other.
The total number of pointer movements is at most proportional to n.
Therefore:
O(n)
not:
O(n²)
One-Based Indexing
Java arrays are zero-indexed.
The problem output is one-indexed.
Therefore:
return new int[]{
left + 1,
right + 1
};
A common interview mistake is returning:
return new int[]{
left,
right
};
Why Use left < right?
The same array element cannot be used twice.
When:
left == right
both pointers refer to the same element.
Therefore, the loop condition must be:
while (left < right)
not:
while (left <= right)
Integer Overflow Risk
Suppose:
numbers[left] = 2,000,000,000
numbers[right] = 2,000,000,000
Their mathematical sum is:
4,000,000,000
which exceeds the Java int maximum.
Incorrect:
int sum =
numbers[left]
+ numbers[right];
Safer:
long sum =
(long) numbers[left]
+ numbers[right];
The cast must happen before the addition.
Incorrect Overflow Cast
This is too late:
long sum =
(long) (
numbers[left]
+ numbers[right]);
The addition occurs as int first and may already overflow.
Correct:
long sum =
(long) numbers[left]
+ numbers[right];
Production-Ready Implementation
public final class TwoSumSorted {
public int[] findPair(
int[] numbers,
int target) {
if (numbers == null) {
throw new IllegalArgumentException(
"Numbers must not be null");
}
if (numbers.length < 2) {
throw new IllegalArgumentException(
"At least two numbers are required");
}
int left = 0;
int right =
numbers.length - 1;
while (left < right) {
long sum =
(long) numbers[left]
+ numbers[right];
if (sum == target) {
return new int[]{
left + 1,
right + 1
};
}
if (sum < target) {
left++;
} else {
right--;
}
}
throw new IllegalArgumentException(
"No pair adds up to the target");
}
}
Should Production Code Validate Sorting?
The Two Pointer algorithm assumes the array is sorted.
Production code has several options.
Option 1 — Document the Precondition
The caller must provide a sorted array.
This avoids an additional scan.
Option 2 — Validate Sorting
private boolean isSorted(
int[] numbers) {
for (int index = 1;
index < numbers.length;
index++) {
if (numbers[index]
< numbers[index - 1]) {
return false;
}
}
return true;
}
Validation costs:
O(n)
The overall complexity remains:
O(n)
Option 3 — Sort a Copy
Sorting requires:
O(n log n)
and changes index semantics.
If original indexes must be returned, sorting raw values is not sufficient.
For this problem, sorted input should normally be treated as a precondition.
Edge Cases
Two Elements
numbers = [1,4]
target = 5
Result:
[1,2]
Negative Numbers
numbers = [-5,-2,0,3,8]
target = 1
Valid pair:
-2 + 3 = 1
Result:
[2,4]
Zero Values
numbers = [0,0,3,4]
target = 0
Result:
[1,2]
The two zeroes occupy distinct indexes.
Duplicate Values
numbers = [1,2,2,3]
target = 4
Possible pair:
1 + 3 = 4
or:
2 + 2 = 4
The original problem guarantees one expected answer, but the algorithm returns whichever matching pair its pointer movement reaches.
Large Target
numbers = [1,2,3]
target = 100
No pair exists.
Production code should define whether to:
- Throw an exception
- Return an empty array
- Return
Optional - Return a result object
Negative Target
numbers = [-10,-5,-2,1]
target = -7
Valid pair:
-5 + -2 = -7
The pointer logic works correctly with negative targets.
Minimum Array Length
An array with fewer than two elements cannot contain a valid pair.
Common Interview Mistakes
Mistake 1 — Ignoring the Sorted Property
Using a HashMap works but misses the intended constant-space optimization.
Mistake 2 — Moving the Wrong Pointer
Incorrect:
Sum too small → Move right left
This makes the sum smaller.
Correct:
Sum too small → Move left right
Mistake 3 — Returning Zero-Based Indexes
The required answer is one-indexed.
Mistake 4 — Using left <= right
This may allow the same element to be selected twice.
Mistake 5 — Forgetting Integer Overflow
Use long for the sum when input values may be large.
Mistake 6 — Sorting the Input Again
The array is already sorted.
Sorting adds unnecessary work.
Mistake 7 — Using Binary Search and Claiming It Is Optimal
Binary search gives:
O(n log n)
The Two Pointer solution is:
O(n)
Mistake 8 — Claiming O(n²) Because There Are Two Pointers
Pointer count does not determine complexity.
Analyze pointer movement.
Mistake 9 — Moving Both Pointers After a Mismatch
Only one pointer should move based on whether the sum is too small or too large.
Mistake 10 — Not Explaining Correctness
A strong answer explains why the discarded index can never participate in a valid pair.
Two Sum I vs Two Sum II
| Two Sum I | Two Sum II |
|---|---|
| Input may be unsorted | Input is sorted |
| HashMap is preferred | Two Pointers are preferred |
| O(n) time, O(n) space | O(n) time, O(1) space |
| Return original zero-based indexes | Return one-based indexes |
| Sorting may lose indexes | Sorting already provided |
Why Not Always Use Two Pointers for Two Sum?
Two Pointers require order information.
For an unsorted array:
[3,2,4]
the current sum does not reliably tell us which pointer to move.
Sorting could enable Two Pointers, but original indexes would need to be preserved.
For unsorted Two Sum, a HashMap is usually simpler.
Follow-Up 1 — Return the Values Instead of Indexes
public int[] findValues(
int[] numbers,
int target) {
int left = 0;
int right =
numbers.length - 1;
while (left < right) {
long sum =
(long) numbers[left]
+ numbers[right];
if (sum == target) {
return new int[]{
numbers[left],
numbers[right]
};
}
if (sum < target) {
left++;
} else {
right--;
}
}
return new int[0];
}
Follow-Up 2 — Return All Unique Pairs
The input may contain multiple valid pairs.
Example:
numbers = [1,1,2,2,3,3,4,4]
target = 5
Unique pairs:
[1,4]
[2,3]
Java Code — All Unique Pairs
import java.util.ArrayList;
import java.util.List;
public class AllTwoSumPairs {
public List<int[]> findPairs(
int[] numbers,
int target) {
List<int[]> result =
new ArrayList<>();
int left = 0;
int right =
numbers.length - 1;
while (left < right) {
long sum =
(long) numbers[left]
+ numbers[right];
if (sum == target) {
result.add(
new int[]{
numbers[left],
numbers[right]
});
int leftValue =
numbers[left];
int rightValue =
numbers[right];
while (left < right
&& numbers[left]
== leftValue) {
left++;
}
while (left < right
&& numbers[right]
== rightValue) {
right--;
}
} else if (sum < target) {
left++;
} else {
right--;
}
}
return result;
}
}
Why Skip Duplicates?
Without skipping duplicate values, the result could include:
[1,4]
[1,4]
[2,3]
[2,3]
Moving past repeated left and right values ensures unique value pairs.
Follow-Up 3 — Count Pairs
The meaning of “count pairs” must be clarified.
Possible requirements:
- Count unique value pairs.
- Count all index pairs.
- Count pairs whose sum is less than a target.
- Count pairs whose sum is greater than a target.
Each variation requires different duplicate handling.
Count Pairs with Sum Less Than Target
For sorted input:
public long countPairsLessThan(
int[] numbers,
int target) {
int left = 0;
int right =
numbers.length - 1;
long count = 0L;
while (left < right) {
long sum =
(long) numbers[left]
+ numbers[right];
if (sum < target) {
count +=
right - left;
left++;
} else {
right--;
}
}
return count;
}
Why Add right - left?
If:
numbers[left] + numbers[right] < target
then every value between:
left + 1 and right
paired with numbers[left] also produces a sum smaller than the target.
The number of valid pairs beginning at left is:
right - left
This allows multiple pairs to be counted at once.
Follow-Up 4 — Closest Pair Sum
Find the pair whose sum is closest to the target.
Java Code — Closest Pair
public class ClosestPairSum {
public int[] findClosestPair(
int[] numbers,
int target) {
if (numbers == null
|| numbers.length < 2) {
throw new IllegalArgumentException(
"At least two numbers are required");
}
int left = 0;
int right =
numbers.length - 1;
int bestLeft = left;
int bestRight = right;
long bestDifference =
Long.MAX_VALUE;
while (left < right) {
long sum =
(long) numbers[left]
+ numbers[right];
long difference =
Math.abs(
sum - target);
if (difference
< bestDifference) {
bestDifference =
difference;
bestLeft = left;
bestRight = right;
}
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
break;
}
}
return new int[]{
bestLeft + 1,
bestRight + 1
};
}
}
Follow-Up 5 — Pair Difference
Find two values whose difference equals a target.
For sorted non-decreasing arrays, use two pointers moving in the same direction.
left = 0
right = 1
Compare:
numbers[right] - numbers[left]
This is a different Two Pointer variation.
Java Code — Target Difference
public class PairWithDifference {
public int[] findPair(
int[] numbers,
int difference) {
int left = 0;
int right = 1;
while (right < numbers.length) {
if (left == right) {
right++;
continue;
}
long currentDifference =
(long) numbers[right]
- numbers[left];
if (currentDifference
== difference) {
return new int[]{
left + 1,
right + 1
};
}
if (currentDifference
< difference) {
right++;
} else {
left++;
}
}
return new int[0];
}
}
Follow-Up 6 — Input Is Unsorted
Options include:
HashMap
Time: O(n)
Space: O(n)
Best when original indexes are required.
Sort Value-Index Pairs
Time: O(n log n)
Space: O(n)
Then apply Two Pointers while preserving original indexes.
Value-Index Record
public record IndexedValue(
int value,
int originalIndex) {
}
Sort records by value, then run Two Pointers.
Follow-Up 7 — Streaming Input
Two Pointers require random access to both ends of sorted data.
For a one-way stream:
- The right boundary may not be available.
- The complete size may be unknown.
- Random backward movement may be impossible.
Alternatives include:
- HashSet of seen values
- External sorting
- Bounded buffers
- Database index lookup
- Windowed pair detection
Follow-Up 8 — Very Large Sorted File
If the data is stored on disk and supports random access:
- One pointer can read from the beginning.
- Another can read from the end.
- Block buffering can reduce I/O.
For sequential-only files, consider:
- External indexes
- Sorting into chunked storage
- Database queries
- One-pass hashing when memory allows
The in-memory algorithm remains logically valid, but storage access patterns matter.
Production Applications
The exact Two Sum II problem is mostly educational, but the pattern appears in real systems.
Examples include:
- Matching debit and credit transactions
- Reconciling payment amounts
- Pairing resource capacities
- Matching order quantities
- Finding complementary price points
- Detecting balanced inventory movements
- Searching sorted time-series values
- Pairing service thresholds
- Financial transaction analysis
- Resource utilization planning
Real-World Example — Transaction Reconciliation
Suppose a sorted list contains transaction amounts:
[25,50,75,100,150,200]
A reconciliation process needs two transactions totaling:
225
Two Pointers can find:
25 + 200
in linear time and constant memory.
In production, transaction IDs would also need to be tracked.
Real-World Example — Resource Capacity Matching
Suppose server capacities are sorted:
[2,4,6,8,10,12]
A workload requires two servers totaling capacity:
16
Possible match:
4 + 12
or:
6 + 10
If multiple matches are allowed, the system must define selection criteria such as:
- Lowest cost
- Lowest energy use
- Maximum geographical separation
- First valid match
Real-World Example — Budget Pairing
Suppose a customer has a fixed budget and wants two products whose prices exactly equal it.
Sorted prices:
[20,30,45,55,70,90]
Budget:
100
The algorithm finds:
30 + 70
Senior-Level Discussion — Why Is This Greedy Pointer Movement Safe?
The pointer movement is greedy because it removes one boundary value without trying all of its pairs.
It is safe due to monotonic ordering.
When the largest possible pair involving the left value is too small, that left value cannot work.
When the smallest possible pair involving the right value is too large, that right value cannot work.
The algorithm relies on this monotonic elimination property.
Without sorted input, the property does not hold.
Senior-Level Discussion — Is This Binary Search?
No.
Both Binary Search and Two Pointers use sorted order, but their search strategies differ.
| Binary Search | Two Pointers |
|---|---|
| Repeatedly halves one search interval | Moves two boundaries |
| Usually searches for one value | Usually searches for a relationship |
| O(log n) per search | O(n) total traversal |
| Random midpoint access | Sequential boundary movement |
Senior-Level Discussion — Can It Return a Deterministic Pair with Duplicates?
Yes, but the exact deterministic rule must be defined.
The standard algorithm returns the first pair encountered by inward pointer movement.
Possible business rules include:
- Smallest first index
- Smallest second index
- Lexicographically smallest pair
- Largest value pair
- First pair by input order
Different rules may require modifying the algorithm.
Interview Explanation
A strong interview explanation could be:
Since the input array is sorted, I place one pointer at the beginning and one at the end. If their sum equals the target, I return their one-based indexes. If the sum is too small, I move the left pointer right because pairing the current left value with any smaller right-side value cannot reach the target. If the sum is too large, I move the right pointer left because pairing the current right value with any larger left-side value would remain too large. Each pointer moves at most
ntimes, so the solution runs in O(n) time with O(1) extra space.
Interview Tips
Interviewers commonly ask:
- Why does the sorted property matter?
- Why move the left pointer when the sum is small?
- Why move the right pointer when the sum is large?
- How do you prove that a valid pair is not skipped?
- Why is the time complexity O(n)?
- Why is the loop condition
left < right? - Why are the returned indexes incremented by one?
- How do you handle integer overflow?
- How is this different from Two Sum I?
- Can Binary Search solve it?
- How would you return all unique pairs?
- How would you count pairs below a target?
- How would the solution change for unsorted input?
- Can the algorithm work on a stream?
- How do duplicates affect the result?
Unit Tests
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import org.junit.jupiter.api.Test;
class TwoSumTwoTest {
private final TwoSumTwo solution =
new TwoSumTwo();
@Test
void shouldFindPairInTypicalArray() {
int[] result =
solution.twoSum(
new int[]{
2,
7,
11,
15
},
9);
assertArrayEquals(
new int[]{1, 2},
result);
}
@Test
void shouldFindFirstAndLastValues() {
int[] result =
solution.twoSum(
new int[]{
2,
3,
4
},
6);
assertArrayEquals(
new int[]{1, 3},
result);
}
@Test
void shouldHandleNegativeValues() {
int[] result =
solution.twoSum(
new int[]{
-1,
0
},
-1);
assertArrayEquals(
new int[]{1, 2},
result);
}
@Test
void shouldHandleDuplicateValues() {
int[] result =
solution.twoSum(
new int[]{
1,
2,
2,
3
},
4);
int firstValue =
new int[]{
1,
2,
2,
3
}[result[0] - 1];
int secondValue =
new int[]{
1,
2,
2,
3
}[result[1] - 1];
assertArrayEquals(
new int[]{4},
new int[]{
firstValue
+ secondValue
});
}
}
Cleaner Duplicate Test
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;
import org.junit.jupiter.api.Test;
class TwoSumTwoDuplicateTest {
private final TwoSumTwo solution =
new TwoSumTwo();
@Test
void returnedIndexesShouldBeDistinctAndValid() {
int[] numbers =
{1, 2, 2, 3};
int[] result =
solution.twoSum(
numbers,
4);
int firstIndex =
result[0] - 1;
int secondIndex =
result[1] - 1;
assertTrue(
firstIndex < secondIndex);
assertEquals(
4,
numbers[firstIndex]
+ numbers[secondIndex]);
}
}
Unit Test — Production Validation
import static org.junit.jupiter.api.Assertions.assertThrows;
import org.junit.jupiter.api.Test;
class TwoSumSortedTest {
private final TwoSumSorted solution =
new TwoSumSorted();
@Test
void shouldRejectNullInput() {
assertThrows(
IllegalArgumentException.class,
() -> solution.findPair(
null,
10));
}
@Test
void shouldRejectArrayWithOneElement() {
assertThrows(
IllegalArgumentException.class,
() -> solution.findPair(
new int[]{5},
10));
}
@Test
void shouldRejectMissingPair() {
assertThrows(
IllegalArgumentException.class,
() -> solution.findPair(
new int[]{1, 2, 3},
100));
}
}
Unit Test — Overflow Safety
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import org.junit.jupiter.api.Test;
class TwoSumOverflowTest {
private final TwoSumTwo solution =
new TwoSumTwo();
@Test
void shouldAvoidIntegerOverflow() {
int[] numbers = {
Integer.MIN_VALUE,
-1,
0,
Integer.MAX_VALUE
};
int[] result =
solution.twoSum(
numbers,
-1);
assertArrayEquals(
new int[]{1, 4},
result);
}
}
The valid pair is:
Integer.MIN_VALUE
+
Integer.MAX_VALUE
=
-1
Approach Comparison
| Approach | Time | Space | Uses Sorted Property | Recommended |
|---|---|---|---|---|
| Brute Force | O(n²) | O(1) | No | No |
| Binary Search | O(n log n) | O(1) | Yes | Better |
| HashMap | O(n) average | O(n) | No | Good for unsorted input |
| Two Pointers | O(n) | O(1) | Yes | Best |
Similar Problems
Once you understand Two Sum II, continue with:
- Three Sum
- Four Sum
- Three Sum Closest
- Container With Most Water
- Trapping Rain Water
- Pair with Target Difference
- Valid Palindrome
- Squares of a Sorted Array
- Remove Duplicates from Sorted Array
- Merge Sorted Arrays
- Count Pairs Less Than Target
Summary
Two Sum II demonstrates how sorted order can guide pointer movement.
The optimal strategy places:
left
at the beginning and:
right
at the end.
At every step:
sum == target → Return
sum < target → left++
sum > target → right--
The sorted property guarantees that each discarded boundary value cannot participate in a valid pair.
Complexity:
Time: O(n)
Space: O(1)
Key Takeaways
- Two Sum II uses a sorted array.
- Start pointers at opposite ends.
- Calculate the sum of boundary values.
- Move the left pointer when the sum is too small.
- Move the right pointer when the sum is too large.
- Return one-based indexes.
- Use
left < rightto avoid reusing one element. - Each pointer moves monotonically.
- Total runtime is O(n).
- Extra space is O(1).
- Use
longto avoid integer overflow. - Brute force takes O(n²).
- Binary Search takes O(n log n).
- HashMap uses O(n) additional space.
- The Two Pointer solution fully uses the sorted property.
- Pointer movement is safe because of monotonic ordering.
- Duplicate values are allowed when they occupy different indexes.
- Skip repeated values when returning all unique pairs.
- Clarify whether follow-ups count index pairs or unique value pairs.
- The same pattern appears in Three Sum and many sorted-array problems.