DSA-001 · Hash lookup with index ownership
Two Sum
Foundation · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 42980 deterministic checks. Learner drafts are not executed.
Understand the problem
Return two distinct indices i<j whose array values sum to target. Return an empty array if no pair exists. Any valid pair is acceptable when several exist.
- nums is non-null with 0–100,000 signed int values; target is a signed int. Null is outside the contract.
- Return exactly two in-range indices in increasing order, or an empty array. An element cannot be used twice.
- Do not mutate nums. Evaluate sums and complements mathematically using long intermediates so overflow cannot invent a pair. The reference chooses the earliest finishing j, then the earliest stored i.
Examples
Input:
[2,7,11,15], target=9
Output:[0,1]The values at two different positions sum to nine.
Input:
[3,3], target=6
Output:[0,1]Equal values are allowed because the positions are distinct.
Input:
[2147483647,1], target=-2147483648
Output:[]The mathematical sum is 2147483648, not the wrapped int value.
Before you start
- Map keys, values, and duplicate insertion behavior
- Index identity and safe integer arithmetic
Recognize the structure
For a fixed right index j, the missing value is target-nums[j]. Repeatedly finding that value is a membership-and-location query. Unlike a sorted two-pointer problem, the input has arbitrary order and we must return original indices.
Try before revealing
Hint 1
Fix the larger index. What value must appear earlier?
Hint 2
Store a location for each processed value.
Hint 3
Check the complement before insertion; return the earlier index and current index.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Enumerate pairs
Try every i and every later j, checking their sum in long arithmetic. For [3,2,4] and target 6, (0,1) gives 5, (0,2) gives 7, and (1,2) succeeds. This is O(n²) time and O(1) auxiliary space; it is correct without sorting or modifying input. Repeated searches through earlier elements are the bottleneck.
Improve the baseline
Remember processed positions
Store value→earliest index for the already processed prefix. This turns a repeated linear search into an expected constant-time lookup.
Look up before inserting
At j, ask for the complement before storing nums[j]. Then an answer always uses an earlier index; [3] cannot match itself.
Preserve the arithmetic contract
Compute complement as long. If it lies outside int range, no array value can equal it. Keep the earliest duplicate index with putIfAbsent for a reproducible reference trace.
Why it is correct
Initialize
The empty map describes exactly the empty processed prefix, and no pair has been skipped.
Preserve
Before processing j, the map holds the earliest index of every value at indices below j. A matching complement gives a valid distinct pair. If none exists, no pair ending at j exists; insertion then establishes the invariant for j+1.
Finish
Every possible pair has a larger index j, so a complete scan without success proves none exists. A returned pair is valid even if another valid pair would also satisfy the contract.
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.
import java.util.HashMap;
import java.util.Map;
public final class Solution {
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> firstIndex = new HashMap<>();
for (int j = 0; j < nums.length; j++) {
long complement = (long) target - nums[j];
if (complement >= Integer.MIN_VALUE && complement <= Integer.MAX_VALUE) {
Integer i = firstIndex.get((int) complement);
if (i != null) return new int[]{i, j};
}
firstIndex.putIfAbsent(nums[j], j);
}
return new int[0];
}
public static int[] baseline(int[] nums, int 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
Map value to index
The map stores positions, not counts, because the requested output is indices.
Range-check the complement
Cast only after the long complement is known to fit; casting first can wrap.
Insert after querying
putIfAbsent preserves the first duplicate position and lookup-first prevents self-use.
Complexity
Expected O(n) time with hashing and O(u) auxiliary entries for u distinct processed values. This is an expected hash-table model, not a guaranteed worst-case promise.
The output has at most two integers. Pair enumeration costs O(n²) time and O(1) extra space. Both preserve the array.
Exact-state walkthroughs
Reveal normal and boundary traces
Lookup before insertion
Input: {"nums":[3,2,4],"target":6} · Result: [1,2]
Step 1 of 7: Start with no earlier positions.
The map describes exactly the processed prefix.
- 0: 3
- 1: 2
- 2: 4
| Variable | Value |
|---|---|
| seen | [] |
See the affected Java block
1 import java.util.HashMap; 2 import java.util.Map; 3 4 public final class Solution { 5 public static int[] twoSum(int[] nums, int target) { 6 Map<Integer, Integer> firstIndex = new HashMap<>(); 7 for (int j = 0; j < nums.length; j++) { 8 long complement = (long) target - nums[j]; 9 if (complement >= Integer.MIN_VALUE && complement <= Integer.MAX_VALUE) { 10 Integer i = firstIndex.get((int) complement); 11 if (i != null) return new int[]{i, j}; 12 } 13 firstIndex.putIfAbsent(nums[j], j); 14 } 15 return new int[0]; 16 } 17 18 public static int[] baseline(int[] nums, int target) { 19 for (int i = 0; i < nums.length; i++) 20 for (int j = i + 1; j < nums.length; j++) 21 if ((long) nums[i] + nums[j] == target) return new int[]{i, j}; 22 return new int[0]; 23 } 24 } 25
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Start with no earlier positions.
The map describes exactly the processed prefix.
- seen
[]
- Query an earlier complement for index 0.
Only indices below j can be returned.
- j
0- value
3- complement
3- seen
[]
- No earlier match; retain the earliest position.
Every processed value maps to its first index.
- j
0- seen
[[3,0]]
- Query an earlier complement for index 1.
Only indices below j can be returned.
- j
1- value
2- complement
4- seen
[[3,0]]
- No earlier match; retain the earliest position.
Every processed value maps to its first index.
- j
1- seen
[[3,0],[2,1]]
- Query an earlier complement for index 2.
Only indices below j can be returned.
- j
2- value
4- complement
2- seen
[[3,0],[2,1]]
- Return the contract result.
The final state satisfies the requested output contract.
- result
[1,2]
No self-pair
Input: {"nums":[3],"target":6} · Result: []
Step 1 of 4: Start with no earlier positions.
The map describes exactly the processed prefix.
- 0: 3
| Variable | Value |
|---|---|
| seen | [] |
See the affected Java block
1 import java.util.HashMap; 2 import java.util.Map; 3 4 public final class Solution { 5 public static int[] twoSum(int[] nums, int target) { 6 Map<Integer, Integer> firstIndex = new HashMap<>(); 7 for (int j = 0; j < nums.length; j++) { 8 long complement = (long) target - nums[j]; 9 if (complement >= Integer.MIN_VALUE && complement <= Integer.MAX_VALUE) { 10 Integer i = firstIndex.get((int) complement); 11 if (i != null) return new int[]{i, j}; 12 } 13 firstIndex.putIfAbsent(nums[j], j); 14 } 15 return new int[0]; 16 } 17 18 public static int[] baseline(int[] nums, int target) { 19 for (int i = 0; i < nums.length; i++) 20 for (int j = i + 1; j < nums.length; j++) 21 if ((long) nums[i] + nums[j] == target) return new int[]{i, j}; 22 return new int[0]; 23 } 24 } 25
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Start with no earlier positions.
The map describes exactly the processed prefix.
- seen
[]
- Query an earlier complement for index 0.
Only indices below j can be returned.
- j
0- value
3- complement
3- seen
[]
- No earlier match; retain the earliest position.
Every processed value maps to its first index.
- j
0- seen
[[3,0]]
- Return the contract result.
The final state satisfies the requested output contract.
- result
[]
Test the contract
Input:
[], target=0
Output:[]No positions.
Input:
[3], target=6
Output:[]Cannot reuse one position.
Input:
[0,0], target=0
Output:[0,1]Duplicate zero.
Input:
[-3,4,3,90], target=0
Output:[0,2]Mixed signs.
Common mistakes and counterexamples
Insert before checking
Counterexample: [3], target=6 can return [0,0].
Query only earlier positions.
Ignore overflow
Counterexample: [MAX_VALUE,1], target=MIN_VALUE is not a pair.
Use long for sums/complements.
Return values instead of positions
Counterexample: [7,2], target=9 requires [0,1], not [7,2].
Retain original indices in the map.
Follow-ups
Return every index pair.
A value may have many earlier positions, so store index lists and emit all matches. Account for potentially quadratic output; one stored index is no longer sufficient.
The array is sorted and memory is tight.
Use inward pointers and an elimination argument, giving O(n) time and O(1) extra space. Preserve original-index requirements if sorting a copy of arbitrary input.
Only existence is required in a stream.
A set of earlier values suffices. Explain unbounded distinct-value memory, duplicate values, and when a sliding retention window changes the problem.
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 · 102/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.