LeetCode · #1
Two Sum Solution
Given an array of integers and a target, return indices of the two numbers that add up to the target. Exactly one solution exists. You may not use the same element twice.
01
Section One · Problem
Problem Statement
Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Each input has exactly one solution, and you may not use the same element twice.
Example
Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1]
// Because nums[0] + nums[1] = 2 + 7 = 9
Constraints
• 2 ≤ nums.length ≤ 10⁴ • -10⁹ ≤ nums[i] ≤ 10⁹ • -10⁹ ≤ target ≤ 10⁹ • Exactly one valid answer exists • You may not use the same element twice
02
Section Two · Approach 1
Brute Force — O(n²)
The most straightforward approach: for every element, scan the rest of the array looking for its complement. Two nested loops — the outer picks the first number, the inner searches for target - nums[i].
Why it works
By checking every pair (i, j) where j > i, we guarantee we find the pair that sums to target. It's correct but slow — O(n²) comparisons.
Why we can do better
Problem: The inner loop repeats work. For each element, we ask "have I seen the complement before?" — but we're scanning the array from scratch every time. A HashMap answers that question in O(1) instead of O(n).
Java — Brute Force
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[] {i, j};
}
}
}
return new int[] {}; // unreachable per constraints
}
Python — Brute Force
class Solution:
def twoSum(self, nums: list[int], target: int) -> list[int]:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return [] # unreachable
| Metric | Value |
|---|---|
| Time | O(n²) — every pair checked |
| Space | O(1) — no extra storage |
03
Section Three · Approach 2
HashMap — O(n)
The key insight: as we scan the array, we need to answer "have I already seen the number that would complete this pair?" — that's a lookup problem. A HashMap maps each value to its index, giving O(1) lookups.
💡 Mental model: Imagine you're at a party looking for your dance partner. Instead of walking up to every person and asking "are you the one?", you write your name and what you need on a whiteboard by the entrance. Each new guest checks the whiteboard first — if their complement is already listed, it's a match. If not, they add themselves and walk in. That whiteboard is your HashMap.
Algorithm — One-pass HashMap
- Step 1: Create an empty HashMap<Integer, Integer> — maps value → index.
- Step 2: For each element nums[i], compute
complement = target - nums[i]. - Step 3: Check if complement exists in the map → if yes, return [map.get(complement), i].
- Step 4: If not, store nums[i] → i in the map and continue.
🎯 When to recognize this pattern:
- Any time a problem says "find two elements that satisfy condition X" — especially sums, differences, or complements — think HashMap complement lookup.
- If you're scanning an array and asking "have I seen the other half before?", a HashMap turns that O(n) scan into O(1).
- This pattern appears in Two Sum, Three Sum (as a sub-routine), pair-with-given-difference, and subarray-sum problems.
Why one pass works:
- We store each element after checking for its complement.
- This guarantees we never match an element with itself (the "don't use same element twice" constraint) — because an element is only added to the map after it has been processed as a potential match.
- When we find a complement, it must be a different, earlier element.
04
Section Four · Trace
Visual Walkthrough
Trace through nums = [2, 7, 11, 15], target = 9:
One-pass HashMap — all 4 iterations
Notice:
- We found the answer on the second element. Steps 3 and 4 are greyed out — they never execute.
- In the best case, we find the pair early and exit.
- In the worst case (answer at the end), we'd scan the entire array once building up the map — still O(n).
05
Section Five · Implementation
Code — Java & Python
Java — One-pass HashMap
import java.util.HashMap;
class Solution {
public int[] twoSum(int[] nums, int target) {
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); // store value → index
}
return new int[] {}; // unreachable — problem guarantees a solution
}
}
Python — One-pass dict
class Solution:
def twoSum(self, nums: list[int], target: int) -> list[int]:
seen = {} # value → index for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return [] # unreachable
06
Section Six · Analysis
Complexity Analysis
| Approach | Time | Space | Trade-off |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | No extra memory, but too slow for n = 10⁴ |
| Sort + Two Pointers | O(n log n) | O(n) | Need to track original indices (sort destroys them) |
| HashMap ← optimal | O(n) | O(n) | One pass, O(1) per lookup. Space for the map. |
Why not sorting?:
- Sorting would give O(n log n) time with two pointers — but the problem asks for indices, not values.
- Sorting destroys index information, so you'd need to store (value, originalIndex) pairs, adding complexity.
- The HashMap approach is simpler, faster (O(n)), and directly returns indices.
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
| Case | Input | Why It Matters |
|---|---|---|
| Negative numbers | [-1, -2, -3, -4, -5], target=-8 | HashMap handles negatives — complement lookup works the same way. |
| Zeros | [0, 4, 3, 0], target=0 | Two zeros sum to 0. One-pass ensures we find the second zero after storing the first → [0, 3]. |
| Duplicate values | [3, 3], target=6 | We check for complement before storing — so when we process the second 3, the first 3 is already in the map. |
| Minimum array | [1, 2], target=3 | Smallest valid input. Works correctly — i=0 stores 1, i=1 finds complement 1 in map. |
| Large values | [10⁹, -10⁹], target=0 | No overflow risk — we only do subtraction and comparison. Java int range handles ±2×10⁹. |
⚠ Common Mistake: Using a two-pass approach (build the full map first, then search) and accidentally matching an element with itself. One-pass avoids this: we store after checking, so an element can never be its own complement match.