Two Sum

EASY✓ CHIP-TIMEDLC #1 — FULL STATEMENT ↗

The drill: Find the two positions in an array whose values add up to a target — each position used once. The full, official statement lives on LeetCode; this page is the training plan.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of integers and a target value arrive together. Somewhere in that array sit exactly two positions whose values add up to the target — the drill is to find them and hand back their indexes.

A position can only be used once: an index never pairs with itself, though two different positions holding the same value are fair game. Every input on this course is built so exactly one valid pair exists.

The answer is the two indexes, in either order. The interesting question is not whether you can find the pair — a double loop always can — but what it costs, and what one pass with a little memory buys you.

EX 01

nums = [4, 11, 7, 15] · target = 18

→ [1, 2]

THE BOARD'S EXAMPLE

EX 02

nums = [5, 5] · target = 10

→ [0, 1]

THE SAME VALUE TWICE

EX 03

nums = [-3, 9, 1, 4] · target = 1

→ [0, 3]

A NEGATIVE COMPLETES THE PAIR

at least two elements — a pair is always possible
values and the target can be negative, zero, or positive
exactly one valid pair per input on this course
the two indexes may come back in any order

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Brute force checks every pair — n² work, because each element keeps re-scanning the whole array. What single question does each element actually need answered?

HINT 2 THE STRUCTURE

For a value v, the only thing that matters is: have I already walked past target − v? “Have I seen it” is a membership question — and there’s a structure that answers membership in O(1).

HINT 3 ONE STEP FROM THE ANSWER

One pass with a value→index map. For each element, look up its complement before inserting itself. Miss → remember me and move on. Hit → the answer is the stored index and this one.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE HASH PASSPATTERN · HASH MAPnums = [4, 11, 7, 15] · target = 18

THE MAP — VALUE → INDEX

— empty —

STEP 1

Target 18. The map starts empty — it will remember every value we walk past.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/two-sum.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}  # value -> index
        for i, v in enumerate(nums):
            need = target - v
            if need in seen:
                return [seen[need], i]
            seen[v] = i
        return []

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 9 LN

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):              # anchor each position...
            for j in range(i + 1, n):   # ...re-scan everything after it
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

TIME O(N²)SPACE O(1)PYTHON · TRAINING PACE · 8 LN

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

TIME O(N)SPACE O(N)JAVA · RACE PACE · 13 LN

class Solution {
    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[] {};
    }
}

TIME O(N²)SPACE O(1)JAVA · TRAINING PACE · 12 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED