Two Sum (LC 1)

Pattern: Hashing / Complement Lookup
Difficulty: Easy
Key Concept: Store each value’s index as you walk the array; the partner you need is target - current, which you can look up in O(1) with a map.

Problem Statement

Given an array of integers nums and an integer target, return indices i and j such that i != j and nums[i] + nums[j] == target.

You may assume that exactly one valid answer exists, and you cannot use the same element twice.

Input

• nums — integer array (length ≥ 2)
• target — integer

Output

• int[] of length 2 — the two indices (order does not matter on LeetCode)

Example

• nums = [2, 7, 11, 15], target = 9 → [0, 1] because nums[0] + nums[1] == 9.

---

1. Algorithm & Pseudocode

Brute force

1. For each index i from 0 to n - 1:
2. For each index j from i + 1 to n - 1:
3. If nums[i] + nums[j] == target, return {i, j}.
4. (Problem guarantees a solution, so you always find a pair before the loops end.)

Optimal

1. Create an empty HashMap<Integer, Integer> indexByValue mapping value → index for elements already seen.
2. For each index i from 0 to n - 1:
3. Let need = target - nums[i].
4. If indexByValue contains key need, return {indexByValue.get(need), i}.
5. Otherwise put nums[i] -> i into the map (so future elements can pair with this one).
6. Stop when you return (guaranteed solution).

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why brute force is correct
You try every unordered pair of distinct indices. One of those pairs must be the unique answer the problem promises, so you will eventually hit it.

Why brute force is slow
There are about (n(n-1)/2) pairs. Checking each pair is (O(n^2)) time, which is too slow when (n) is large (e.g. (10^4)–(10^5)).

Why the map idea works
When you are at index i, you already know nums[i]. For a sum to equal target, the other number must be need = target - nums[i]. If you have seen need before at some index j, then nums[j] + nums[i] == target. You do not need to scan all earlier elements—only ask the map: “Have I seen need, and at which index?”

Why we store index, not just “seen”
The answer must be indices. The map remembers where each value appeared.

Why we add nums[i] after checking need
If we added first, we might pair an index with itself when 2 * nums[i] == target and duplicates exist. By only recording past positions, j is always strictly less than i.

ASCII — scanning pairs (brute force)

indices:  0   1   2   3
nums:    [2,  7, 11, 15]   target = 9

i=0: compare (0,1)(0,2)(0,3) ...
         2+7 = 9  ✓  → return [0,1]

ASCII — one pass with “need” (optimal)

i=0: nums[0]=2  need=7   map {}           → store 2→0
i=1: nums[1]=7  need=2   map has 2→0      → return [0,1]

---

3. The Dry Run

Input: nums = [2, 7, 11, 15], target = 9

Step	i	nums[i]	need	Map (before step)	Action
1	0	2	7	{}	7 not in map → put 2 → 0
2	1	7	2	{2→0}	2 in map → return [0, 1]

Duplicate values note: nums = [3, 3], target = 6 — at i=1, need=3, map has 3→0, return [0,1]; we never use the same index twice.

---

4. Java Solution

Brute Force

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] { i, j };
                }
            }
        }
        return new int[0]; // unreachable if exactly one solution exists
    }
}

Time: (O(n^2)) — all pairs in worst case.
Space: (O(1)) extra.

Optimal

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> indexByValue = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (indexByValue.containsKey(need)) {
                return new int[] { indexByValue.get(need), i };
            }
            indexByValue.put(nums[i], i);
        }
        return new int[0];
    }
}

Time: (O(n)) average — one pass; each map op (O(1)) average.
Space: (O(n)) — map holds up to (n) entries.

---

5. The “Java vs. Others” Edge

• HashMap<Integer, Integer> gives (O(1)) average get/put; TreeMap would be (O(\log n)) per op and is rarely needed here.
• containsKey + get is clear; alternatively getOrDefault or computeIfAbsent if you extend the pattern.
• Primitive int keys autobox to Integer; for huge arrays and micro-optimization, libraries like Trove exist, but LeetCode style uses HashMap.
• Returning new int[] { a, b } is idiomatic; no need for ArrayList for a fixed pair.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	(O(n^2))	(O(1))	Nested loops; always correct.
Optimal	(O(n))*	(O(n))	*Average hash; worst-case hash collisions can degrade to (O(n^2)) in theory.