1. Two Sum
Problem Details
- 🔗 Link: https://leetcode.com/problems/two-sum/
- 📊 Difficulty: Easy
- 🏢 Asked By: Amazon, Google, Meta, Apple
- 🏷️ Category: Arrays & Hashing
- 🔗 Similar Problems: LC 167 (Two Sum II), LC 15 (3Sum), LC 18 (4Sum), LC 560 (Subarray Sum Equals K)
📋 Problem Statement
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
Examples
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Explanation: nums[1] + nums[2] == 6, so return [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Explanation: Two different indices with same value sum to target
Constraints
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9- Only one valid answer exists
💡 Implication of constraints:
- ✅ Array always has ≥ 2 elements (guaranteed pair exists)
- ✅ Can return immediately upon finding solution (exactly one answer)
- ✅ Large value range (-10⁹ to 10⁹) → Cannot use array indexing, must use HashMap
- ✅ Values can be negative, zero, or positive → Handle all cases
🚫 Approach 1 – Brute Force
Thought Process
💭 The Most Obvious Way:
- Try all possible pairs of numbers in the array
- For each element, check it against every other element
- Start with first element → check against all others
- Move to second element → check against all remaining
- Continue until pair found that sums to target
- Direct translation of problem into code (no clever optimization)
Algorithm / Pseudocode
Step 1: Outer loop with index i from 0 to length-2
(Stop at length-2 because need at least one element after current)
Step 2: For each i, inner loop with index j from i+1 to length-1
(Start from i+1 to avoid using same element twice)
Step 3: For each pair (i, j):
- Calculate sum: nums[i] + nums[j]
- If sum equals target → return [i, j] immediately
Step 4: If all pairs checked with no match:
- Return empty array (never happens due to constraints)
Code
class Solution {
public int[] twoSum(int[] nums, int target) {
// Outer loop: consider each element as first number in pair
// Stop at length-1 because we need at least one more element
for (int i = 0; i < nums.length - 1; i++) {
// Inner loop: check all elements after position i
// Starting from i+1 prevents using same element twice
for (int j = i + 1; j < nums.length; j++) {
// Check if current pair sums to target
if (nums[i] + nums[j] == target) {
// Found our answer! Return indices immediately
return new int[] {i, j};
}
}
}
// Never executes (problem guarantees exactly one solution)
// Required by Java to ensure all paths return a value
return new int[] {};
}
}
Dry Run
🔍 Walking Through Example: nums = [3, 2, 4], target = 6
Initial Setup:
═══════════════════════════════════════════════
Array: [3, 2, 4]
Index: 0 1 2
Target: 6
═══════════════════════════════════════════════
Execution Trace Table:
┌──────┬───┬───┬─────────┬─────────┬─────┬────────┬──────────────────┐
│ Step │ i │ j │ nums[i] │ nums[j] │ Sum │ Match? │ Action │
├──────┼───┼───┼─────────┼─────────┼─────┼────────┼──────────────────┤
│ 1 │ 0 │ 1 │ 3 │ 2 │ 5 │ ❌ │ Continue │
│ 2 │ 0 │ 2 │ 3 │ 4 │ 7 │ ❌ │ Continue │
│ 3 │ 1 │ 2 │ 2 │ 4 │ 6 │ ✅ │ Return [1,2] │
└──────┴───┴───┴─────────┴─────────┴─────┴────────┴──────────────────┘
Detailed Step-by-Step:
═══════════════════════════════════════════════
Step 1: i=0, j=1
Checking pair at indices [0, 1]
Values: nums[0]=3, nums[1]=2
Sum: 3 + 2 = 5
Does 5 == 6? ❌ No
→ Continue to next pair
Step 2: i=0, j=2
Checking pair at indices [0, 2]
Values: nums[0]=3, nums[2]=4
Sum: 3 + 4 = 7
Does 7 == 6? ❌ No
→ Outer loop increments i to 1
Step 3: i=1, j=2
Checking pair at indices [1, 2]
Values: nums[1]=2, nums[2]=4
Sum: 2 + 4 = 6
Does 6 == 6? ✅ Yes!
→ Return [1, 2] immediately
═══════════════════════════════════════════════
Result: [1, 2] after checking 3 pairs
═══════════════════════════════════════════════
Time & Space Complexity
⏰ Time Complexity: O(n²)
- Outer loop runs n-1 iterations
- Inner loop runs progressively fewer times: (n-1) + (n-2) + ... + 1
- Total comparisons: (n-1) × n / 2 ≈ n²/2
- Simplifies to O(n²) in Big-O notation
💾 Space Complexity: O(1)
- Only constant extra space used
- Two loop variables i, j (fixed size)
- Result array not counted (required output)
- No data structures that grow with input
✅ Approach 3 – Optimal (Final)
Thought Process (How did you arrive here)
🎯 The Breakthrough Insight:
Brute Force Problem: Checking every pair repeatedly is wasteful
↓
Key Question: For each number, what are we looking for?
→ We know EXACTLY what we need: the complement!
↓
Insight: Instead of searching forward from each position,
REMEMBER what we've already seen
↓
Solution: Use HashMap for instant O(1) lookups
"Have I seen this complement before?"
↓
Trade-off: Sacrifice O(n) space to gain O(n) time
🔑 Why Check BEFORE Adding:
- If we add first, then check → Need two passes
- If we check first, then add → Single pass! ✨
- Bonus: Automatically prevents using same element twice
Algorithm / Pseudocode
Step 1: Create empty HashMap to store (number → index) mapping
Step 2: Iterate through array once (index i from 0 to length-1):
a. Calculate complement = target - nums[i]
(This is the value we need to find)
b. Check if complement exists in HashMap:
IF FOUND:
✅ We found our pair!
✅ Return [map.get(complement), i]
✅ Complement's index first (was seen earlier)
IF NOT FOUND:
⏭️ Haven't seen complement yet
⏭️ Store current element: map.put(nums[i], i)
⏭️ Continue to next iteration
Step 3: Return empty array (never reached, solution guaranteed)
Code
import java.util.HashMap;
import java.util.Map;
class Solution {
public int[] twoSum(int[] nums, int target) {
// HashMap stores each number and its index as we traverse
// Key: number value | Value: its index in array
Map<Integer, Integer> numToIndex = new HashMap<>();
// Single pass through array
for (int i = 0; i < nums.length; i++) {
// Calculate what complement we need
// If nums[i] + complement = target
// Then complement = target - nums[i]
int complement = target - nums[i];
// Check if we've already seen this complement
if (numToIndex.containsKey(complement)) {
// ✅ Found our pair! Return the two indices
// Complement was seen earlier, so its index comes first
return new int[] {numToIndex.get(complement), i};
}
// ⏭️ Haven't seen complement yet
// Store current number and index for future reference
numToIndex.put(nums[i], i);
}
// Never reached (guaranteed exactly one solution exists)
return new int[] {};
}
}
Dry Run
🔍 Step-by-Step Execution: nums = [2, 7, 11, 15], target = 9
Initial Setup:
═══════════════════════════════════════════════════════════════════
Array: [2, 7, 11, 15]
Index: 0 1 2 3
Target: 9
HashMap: {} (empty)
═══════════════════════════════════════════════════════════════════
Execution Table:
┌──────┬───┬─────────┬─────────────────┬────────────┬────────────────┬────────┬──────────────┐
│ Step │ i │ nums[i] │ Complement │ HashMap │ Complement │ Action │ HashMap │
│ │ │ │ (9-nums[i]) │ Before │ Found? │ │ After │
├──────┼───┼─────────┼─────────────────┼────────────┼────────────────┼────────┼──────────────┤
│ 1 │ 0 │ 2 │ 7 │ {} │ ❌ No │Add 2→0 │ {2→0} │
│ 2 │ 1 │ 7 │ 2 │ {2→0} │ ✅ Yes (at 0) │Return │ {2→0} │
│ │ │ │ │ │ │ [0,1] │ │
└──────┴───┴─────────┴─────────────────┴────────────┴────────────────┴────────┴──────────────┘
Detailed Trace:
═══════════════════════════════════════════════════════════════════
📍 Iteration 1: i=0
┌─────────────────────────────────────────────────────────┐
│ Current element: nums[0] = 2 │
│ Calculate complement: 9 - 2 = 7 │
│ │
│ Check HashMap for 7: │
│ HashMap: {} │
│ Contains 7? ❌ NO │
│ │
│ Action: Add current element to map │
│ map.put(2, 0) │
│ │
│ HashMap state: {2 → 0} │
│ Continue to next iteration... │
└─────────────────────────────────────────────────────────┘
📍 Iteration 2: i=1
┌─────────────────────────────────────────────────────────┐
│ Current element: nums[1] = 7 │
│ Calculate complement: 9 - 7 = 2 │
│ │
│ Check HashMap for 2: │
│ HashMap: {2 → 0} │
│ Contains 2? ✅ YES! │
│ │
│ Action: Found our pair! │
│ Complement 2 is at index 0 (from HashMap) │
│ Current element 7 is at index 1 │
│ Return [0, 1] immediately │
└─────────────────────────────────────────────────────────┘
═══════════════════════════════════════════════════════════════════
🎯 Final Result: [0, 1]
⚡ Efficiency: Found answer in just 2 iterations (out of 4 possible)
✨ Never checked pairs: (2,11), (2,15), (7,11), (7,15)
═══════════════════════════════════════════════════════════════════
Key Insights from This Run:
───────────────────────────────────────────────────────────────────
✅ HashMap provided instant O(1) lookup for complement
✅ Early exit as soon as solution found
✅ Single pass through array (optimal)
✅ No redundant pair checking
Time & Space Complexity
⏰ Time Complexity: O(n)
- Single pass through array: n iterations maximum
- Each iteration performs:
- HashMap lookup (containsKey): O(1) average
- HashMap insertion (put): O(1) average
- Total: n × O(1) = O(n) linear time
💾 Space Complexity: O(n)
- HashMap can store up to n elements in worst case
- Worst case: Answer is last two elements
- Must store all previous n-2 elements before finding solution
- Example: [1,2,3,4,5], target=9 → stores 1,2,3,4 before finding 4+5
- Trade-off: Used O(n) space to improve time from O(n²) to O(n)
Space-Time Trade-off Visualization:
═══════════════════════════════════════════════════════════════════
Brute Force: Time O(n²) Space O(1) ⚠️ Slow but no extra space
Optimal: Time O(n) Space O(n) ✨ Fast with reasonable space
═══════════════════════════════════════════════════════════════════
🔍 Edge Cases & Testing
Edge Cases
1. Minimum Size Array (n=2):
Input: [1, 2], target = 3
Output: [0, 1]
🧪 Tests: Base case with smallest valid input
2. Negative Numbers:
Input: [-3, 4, 3, 90], target = 0
Output: [0, 2] (because -3 + 3 = 0)
🧪 Tests: Handling of negative values
3. Duplicate Values (Same value, different indices):
Input: [3, 3], target = 6
Output: [0, 1]
🧪 Tests: Can use same value at different positions
🧪 Tests: HashMap overwrites correctly
4. Zero in Array:
Input: [0, 4, 3, 0], target = 0
Output: [0, 3] (because 0 + 0 = 0)
🧪 Tests: Zero handling
5. Large Numbers Near Integer Limits:
Input: [1000000000, 999999999, 1], target = 1999999999
🧪 Tests: Boundary of int range
🧪 Tests: No integer overflow in calculations
6. Solution at Beginning:
Input: [2, 7, 11, 15], target = 9
Output: [0, 1]
🧪 Tests: Early exit optimization
7. Solution at End:
Input: [11, 15, 2, 7], target = 9
Output: [2, 3]
🧪 Tests: Full traversal scenario
8. Negative Target:
Input: [-1, -2, -3, -4], target = -6
Output: [1, 3] (because -2 + -4 = -6)
🧪 Tests: Negative target handling
Test Suite
✅ Basic Tests:
Test 1: nums = [2,7,11,15], target = 9
Expected: [0,1]
Test 2: nums = [3,2,4], target = 6
Expected: [1,2]
Test 3: nums = [3,3], target = 6
Expected: [0,1]
🔍 Edge Tests:
Test 4: Minimum size
nums = [1,2], target = 3
Expected: [0,1]
Test 5: Negative numbers
nums = [-1,-2,-3,-4,-5], target = -8
Expected: [2,4] (because -3 + -5 = -8)
Test 6: With zeros
nums = [0,4,3,0], target = 0
Expected: [0,3]
Test 7: Negative target
nums = [1,-1,2,-2], target = -3
Expected: [1,3] (because -1 + -2 = -3)
💪 Stress Tests:
Test 8: Large array (performance test)
nums = [1,2,3,...,9999,10000], target = 19999
Expected: [9998,9999]
Validates: O(n) time efficiency
Test 9: Large values near limits
nums = [1000000000,-999999999,1], target = 1
Expected: [1,2]
Validates: No integer overflow
Test 10: Solution at different positions
nums = [5,75,25], target = 100
Expected: [1,2]
Validates: Works regardless of solution position
📝 Weekly Quick Revision (Memory Boosters)
🎯 The Essence in 7 Lines
Two Sum asks for indices of two numbers that sum to target
Brute Force: Check all pairs in O(n²) time with nested loops
↓
Optimal: Use HashMap to store seen numbers for O(1) complement lookup
↓
For each number, calculate complement (target - current)
↓
Check if complement exists in map BEFORE adding current number
↓
Single pass O(n) time, O(n) space solution
💡 Mental Trigger
┌──────────────────────────────────────────────────────────────┐
│ WHEN YOU SEE: │
│ "Find two elements that sum/match to target" │
│ │
│ IMMEDIATELY THINK: │
│ ✨ HashMap for complement lookup │
│ ✨ Check before storing │
│ ✨ Single pass solution │
└──────────────────────────────────────────────────────────────┘
🚀 Quick Algorithm Recall
// The 5-line pattern you need to remember:
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) return new int[] {map.get(complement), i};
map.put(nums[i], i);
}
🔑 Core Pattern Recognition
Problem Type: Two Sum → HashMap Complement Pattern
When to Apply:
✓ Finding pairs with specific relationship
✓ Can rearrange equation to isolate search target
✓ Need to optimize from O(n²) to O(n)
✓ Order doesn't matter for correctness
Related Problems:
→ Two Sum II (sorted array → use two pointers instead)
→ 3Sum (extends to three elements)
→ 4Sum (extends to four elements)
→ Subarray Sum Equals K (uses similar complement concept)