Two Sum Problem — A Complete Guide

---

What is the Problem?

Given an integer array, find two numbers that add up to a target sum.

• V1 → Return "YES" or "NO"
• V2 → Return the indices of those two numbers (target always valid in V2)

arr[] = {2, 6, 5, 8, 11}, target = 14
V1 → "YES"
V2 → [1, 3]  (arr[1]=6, arr[3]=8 → 6+8=14)

---

Edge Cases to Always Keep in Mind

• All elements are 0 → {0,0,0,0}, target 0 → YES, [0,1]
• Array has only 1 element → no pair possible, always NO
• Duplicate elements → {3,3,5}, target 6 → YES, [0,1]
• Negative numbers → {-1, 5, 3}, target 4 → YES (-1+5)
• Large numbers → potential integer overflow in some languages
• Target is smaller than the two smallest elements → NO
• Same element used twice — not allowed, i ≠ j always

---

Approach 1 — Brute Force

Time: O(n²) | Space: O(1)

The Idea: Check every possible pair in the array.

How it works:

• Run an outer loop i from 0 → n
• Run an inner loop j from i+1 → n (starting from i+1 avoids duplicate pairs and self-pairing)
• If arr[i] + arr[j] == target → return YES / [i, j]
• If no pair found after all iterations → return NO

arr = {2, 6, 5, 8, 11}, target = 14
i=0 (2): j=1→2+6=8, j=2→2+5=7, j=3→2+8=10, j=4→2+11=13
i=1 (6): j=2→6+5=11, j=3→6+8=14 ✅ → return [1,3]

⚠️ Why j = i+1? If j starts from 0 every time, you re-check the same pairs twice AND risk using the same index twice.

---

Approach 2 — HashMap (Best for Unsorted Arrays)

Time: O(n) | Space: O(n)

The Core Equation:

arr[i] + x = target
x = target - arr[i]   ← this is what we're hunting for

How it works:

• Maintain a HashMap { value → index }
• Loop through the array with index i
• Calculate x = target - arr[i]
• If x exists in the map → found the pair → return [map[x], i]
• If x not in map → store arr[i] → i in the map and move on

arr = {2, 6, 5, 8, 11}, target = 14
i=0, val=2, need=12 → not in map → store {2:0}
i=1, val=6, need=8  → not in map → store {2:0, 6:1}
i=2, val=5, need=9  → not in map → store {2:0, 6:1, 5:2}
i=3, val=8, need=6  → 6 IS in map at index 1 ✅ → return [1, 3]

✅ One-pass solution. You're building and checking the map simultaneously.

---

Approach 3 — Two Pointers (Only if Array is Sorted)

Time: O(n) after sorting | Space: O(1) Sorting cost: O(n log n) — so overall O(n log n)

The Idea: Use two ends of the sorted array and squeeze inward.

How it works:

• Place pointer i = 0 (left end), j = arr.length - 1 (right end)
• Loop while i < j:
  • If arr[i] + arr[j] == target → ✅ return [i, j]
  • If sum > target → move j-- (need smaller number)
  • If sum < target → move i++ (need bigger number)

arr = {2, 5, 6, 8, 11}, target = 14  (sorted)
i=0(2), j=4(11) → 13 < 14 → i++
i=1(5), j=4(11) → 16 > 14 → j--
i=1(5), j=3(8)  → 13 < 14 → i++
i=2(6), j=3(8)  → 14 == 14 ✅ → return [2, 3]

⚠️ If array is unsorted, you must sort first — but then original indices are lost. Store {value, originalIndex} pairs before sorting if you need original indices back.

---

Quick Comparison Cheatsheet

Approach	Time	Space	Best Used When
Brute Force	O(n²)	O(1)	Small arrays, quick prototype
HashMap	O(n)	O(n)	Unsorted, need original indices
Two Pointer	O(n log n)	O(1)	Array already sorted, save memory

---

Rule of thumb: Default to HashMap for most interviews. Use Two Pointer only when the array is already sorted or space is a hard constraint.