Two Sum in Java — HashMap O(n), Two-Pointer Sorted, Variants

Standard Two Sum (unsorted)

HashMap one-pass — O(n) time, O(n) space

• Iterate once
• For each element x, check if target - x is in the map
• If yes, return [map.get(complement), current index]
• Otherwise, put x in the map
• If no pair found, return default

Why one pass works

• As we iterate, the map contains all previous elements
• Current element checks backward against the map
• When complement is found, both indices are available

Duplicates

• target=6, nums=[3,3]: first 3 stored at index 0; second 3 finds it; return [0,1]
• Works correctly

Overflow

• target - nums[i] can overflow if target = Integer.MIN_VALUE
• Cast to long if large values are possible

Sorted input — Two-pointer O(n) time, O(1) space

• left = 0, right = n-1
• sum = nums[left] + nums[right]
• If sum < target: left++
• If sum > target: right--
• If equal: return pair

Why monotonicity works

• sum too small → need larger → moving right left shrinks sum (wrong direction) — move left right
• sum too large → mirror
• Each move commits to skipping pairs; the argument proves we never skip a valid one

When to use which

HashMap

• Unsorted input
• Need original indices
• O(n) space OK

Two-pointer

• Sorted input
• Memory-constrained
• Any valid pair (don't care about original indices)

Don't sort just to use two-pointer

• O(n log n) sorting cost
• Loses original indices
• HashMap's O(n) is usually better

Variants

Three Sum (O(n²))

• Sort, outer loop on first element
• Two-pointer for remaining two
• Skip duplicates at each level for distinct triplets

Four Sum (O(n³))

• Sort, two outer loops
• Two-pointer at base

K-Sum generalization

• Recursion + two-pointer at base
• O(n^(K-1))

Count pairs

• HashMap with frequencies
• pairs += count[target - n]
• O(n) time, O(n) space

Pairs with difference K

• Similar to two-sum
• For each n, check n - K and n + K in seen set

Two Sum III (data structure)

• add: O(1) — HashMap merge count
• find: O(n) — scan keys
• Handles duplicates: target=2a needs count[a] ≥ 2

Two Sum BST

• Two iterators (in-order forward, reverse in-order)
• Two-pointer logic on the iterators
• O(n) time, O(h) space
• Or: in-order flatten + two-pointer, O(n) space

Closest pair to target

• Sort + two-pointer
• Track smallest |sum - target|

Edge cases

Array < 2 elements

• No valid pair
• Return default / throw

No valid pair

• Return [-1, -1] or throw IllegalArgumentException

Negative numbers

• Works for both approaches
• No special handling

Duplicates

• HashMap handles naturally
• Two-pointer + duplicates: skip manually in K-Sum variants

Integer overflow

• target - x if target = Integer.MIN_VALUE and x > 0
• Cast to long
• Or: if (target - x == nums[j]) replaced by careful compare

Common pitfalls

1. O(n²) brute force

• Nested loops — wastes the technique

2. Sorting unsorted input

• Loses indices
• O(n log n) overhead
• Use HashMap instead

3. Forgetting duplicates

• target=6, [3,3] must return pair
• Some implementations fail here

4. Off-by-one in two-pointer

• while (left < right) — strict less, not ≤

5. Using the same element twice

• HashMap stores index; current index is never in map when checked
• Ensures distinct indices

Recommendation: For Two Sum on unsorted input, always start with the HashMap one-pass approach — O(n) time, O(n) space, handles duplicates naturally, preserves original indices. The key insight is: for each element, check if its complement is already in the map. If you're given sorted input, prefer two-pointer for O(1) space; never sort an unsorted array just to use two-pointer (O(n log n) cost and loses index mapping). Always handle duplicates correctly — target=6 with [3, 3] must return [0, 1]. Watch for integer overflow when target is near Integer.MIN_VALUE; cast to long if necessary. For extensions: Three Sum is sort + outer loop + two-pointer (O(n²)); Four Sum adds another outer loop (O(n³)); K-Sum generalizes via recursion + two-pointer at base. For counting all pairs, use a HashMap with frequencies. For Two Sum III (data structure design), maintain a counts HashMap with O(1) add and O(n) find. For Two Sum BST, use two iterators (in-order forward and reverse) to achieve O(n) time, O(h) space. The mental model: Two Sum = complement lookup; HashMap makes it O(n), sorted input makes two-pointer O(n) with O(1) space. Once you've internalized this, all K-Sum variants and related pair-finding problems become the same template with different bookkeeping.