#1 · Arrays & Hashing

Two Sum

Given an array of integers and a target, return the indices of the two numbers that add up to the target. Exactly one solution exists and you may not use the same element twice.

EasyLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Hash table (Map)

Maps a key to a value through a hash function, giving average O(1) insert and lookup. Here the key is a number we have seen and the value is its index.

Memory layout

An array of buckets (or an open-addressed table) of key/value slots. A lookup hashes the key, jumps to a slot, and compares. Entries are scattered, so each probe is a likely cache miss, unlike a linear scan.

Operation	Cost
insert / set	O(1) average, O(n) worst (resize or collisions)
lookup / has	O(1) average, O(n) worst
space	O(n) entries + load-factor slack

Array (and sorted index array)

Contiguous, index-addressable storage. Sorting it enables the two-pointer technique, which reasons about order instead of storing history.

Memory layout

One contiguous block, so a scan is prefetcher-friendly and cache-hot. A sorted index permutation adds an O(n) auxiliary array.

Operation	Cost
index access	O(1)
sort	O(n log n)
two-pointer scan	O(n)

Why it fits

Two Sum is a membership question in disguise: "have I already seen target − x?". A hash table answers that in O(1), which removes the inner loop.
Storing indices as values means we never lose position information, unlike sorting, which has to carry indices along.
Inserting after checking makes a single pass sufficient and rules out reusing the same element.

Why alternatives degrade

Nested loops over the array:: O(n²) comparisons. Fine for n = 100, painful at n = 10⁵ (about 5 × 10⁹ pairs).
Sorted array + binary search:: O(n log n) overall, and it still needs an index permutation to report original positions.
Balanced BST / TreeMap:: O(log n) per lookup and pointer-chasing nodes. It is strictly worse than a hash table unless you need ordered queries.

Four approaches, from naive to production

1 · beginner

Brute force: all pairs

time O(n²)space O(1)

Try every pair (i, j) with j > i and return the first that sums to target.

vector<int> twoSum(vector<int>& nums, int target) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] == target) {
                return {i, j};
            }
        }
    }
    return {};
}

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];
}

def two_sum(nums: list[int], target: int) -> list[int]:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

function twoSum(nums: number[], target: number): number[] {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return [];
}

Flaws & bottlenecks

O(n²) time: about 5 × 10⁹ comparisons for n = 10⁵, which will time out.
Does redundant work: element x is compared against every other element even though only one value, target − x, could ever match.
Gives no early information; a miss tells you nothing about later pairs.

Interviewer cross-questions

Can you do better than O(n²)?

Say: Yes. For each x only target − x can complete the pair, so instead of scanning for it I can look it up. Storing seen values in a hash map makes the inner loop O(1), giving O(n) time at the cost of O(n) space.

When would you actually ship the brute force?

Say: For tiny n, or when memory is hard-capped. With n ≤ ~50 it is simpler, allocation-free, and often faster than hashing because it scans contiguous memory with no hash cost.

What is the space complexity?

Say: O(1) auxiliary. Only two loop counters, nothing allocated.

2 · intermediate

Sort + two pointers

time O(n log n)space O(n)

Sort an index array by value, then walk inward from both ends: too small moves left up, too big moves right down.

vector<int> twoSum(vector<int>& nums, int target) {
    int n = nums.size();
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b) { return nums[a] < nums[b]; });
    int left = 0;
    int right = n - 1;
    while (left < right) {
        long long sum = (long long)nums[idx[left]] + nums[idx[right]];
        if (sum == target) return {idx[left], idx[right]};
        if (sum < target) left++;
        else right--;
    }
    return {};
}

public int[] twoSum(int[] nums, int target) {
    int n = nums.length;
    Integer[] idx = new Integer[n];
    for (int i = 0; i < n; i++) idx[i] = i;
    Arrays.sort(idx, (a, b) -> Integer.compare(nums[a], nums[b]));
    int left = 0;
    int right = n - 1;
    while (left < right) {
        long sum = (long) nums[idx[left]] + nums[idx[right]];
        if (sum == target) return new int[]{idx[left], idx[right]};
        if (sum < target) left++;
        else right--;
    }
    return new int[0];
}

def two_sum(nums: list[int], target: int) -> list[int]:
    idx = sorted(range(len(nums)), key=lambda i: nums[i])
    left = 0
    right = len(nums) - 1
    while left < right:
        total = nums[idx[left]] + nums[idx[right]]
        if total == target:
            return [idx[left], idx[right]]
        if total < target:
            left += 1
        else:
            right -= 1
    return []

function twoSum(nums: number[], target: number): number[] {
  const idx = nums.map((_, i) => i).sort((a, b) => nums[a] - nums[b]);
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const sum = nums[idx[left]] + nums[idx[right]];
    if (sum === target) return [idx[left], idx[right]];
    if (sum < target) left++;
    else right--;
  }
  return [];
}

Flaws & bottlenecks

Sorting dominates at O(n log n), and it is not needed for this problem.
Needs an O(n) index array, because plain sorting would destroy the original positions the answer requires.
Not online: you cannot answer before the whole input has been read and sorted.

Interviewer cross-questions

Why does moving a single pointer never skip the answer?

Say: If sum < target, then left paired with any right′ ≤ right gives an even smaller sum, so left cannot be part of any answer with the current or a smaller right. Discarding it is safe. The same argument holds symmetrically for right. This is the invariant that makes the scan O(n).

What if the array is already sorted?

Say: Then I skip the sort and the index array, and the two-pointer scan alone gives O(n) time and O(1) space. This is the Two Sum II variant.

Why sort indices and not the values?

Say: The problem asks for original indices. Sorting values loses them, so I sort a permutation of indices by key. A decorated array of (value, index) pairs works too and is more cache-friendly.

3 · advanced

One-pass hash map

time O(n)space O(n)

For each x, ask whether target − x has been seen. If yes, we are done; if not, record x and its index and move on.

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;
    for (int i = 0; i < (int)nums.size(); i++) {
        int need = target - nums[i];
        auto it = seen.find(need);
        if (it != seen.end()) {
            return {it->second, i};
        }
        seen[nums[i]] = i;
    }
    return {};
}

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[0];
}

def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return []

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) {
      return [seen.get(need)!, i];
    }
    seen.set(nums[i], i);
  }
  return [];
}

Flaws & bottlenecks

O(n) extra memory: the map can grow to n−1 entries before a hit.
Hash costs: boxing, collisions, and rehashing on growth; the constant factor is much larger than a plain array scan.
Average-case O(1) only; adversarial keys can degrade a poorly seeded hash table.

Interviewer cross-questions

Why insert after checking, not before?

Say: So an element cannot pair with itself. With nums = [3, 2, 4] and target 6, inserting first would match 3 with 3. Checking first also handles real duplicates like [3, 3] correctly, since the first 3 is already stored when the second arrives.

What if the data stream is infinite or does not fit in memory?

Say: The hash map approach is already online, so it works on a stream, but memory is unbounded. For data larger than RAM I would partition by hash(x) so that x and target − x land in the same shard, or use external sort and then the two-pointer merge. A Bloom filter can cheaply prefilter candidates at the cost of false positives.

How does it behave on a multi-threaded system?

Say: A shared mutable map needs synchronization. Better to shard: hash-partition the input by min(x, target − x) so each worker owns a disjoint map and no locking is needed, then merge any hits.

4 · expert

Defensive, single-lookup version

time O(n)space O(n)

Same O(n) algorithm, hardened for production: validate inputs, accept any ArrayLike (including typed arrays), use one map lookup per element, and return a typed tuple or null instead of a magic empty array.

optional<pair<int, int>> twoSum(const vector<int>& nums, long long target) {
    int n = nums.size();
    if (n < 2 || target < 2LL * INT_MIN || target > 2LL * INT_MAX) return nullopt;
    unordered_map<int, int> seen;
    seen.reserve(2 * n);
    for (int i = 0; i < n; i++) {
        int x = nums[i];
        long long need = target - x;
        if (need < INT_MIN || need > INT_MAX) continue;
        auto it = seen.find((int)need);
        if (it != seen.end()) return pair<int, int>{it->second, i};
        seen.emplace(x, i);
    }
    return nullopt;
}

public static int[] twoSum(int[] nums, long target) { // null if no pair
    if (nums == null || nums.length < 2) return null;
    Map<Integer, Integer> seen = new HashMap<>(nums.length * 2);
    for (int i = 0; i < nums.length; i++) {
        int x = nums[i];
        long need = target - x;
        if (need < Integer.MIN_VALUE || need > Integer.MAX_VALUE) continue;
        Integer j = seen.get((int) need);
        if (j != null) return new int[]{j, i};
        seen.put(x, i);
    }
    return null;
}

def two_sum(nums: Sequence[int], target: int) -> tuple[int, int] | None:
    if not isinstance(target, int) or len(nums) < 2:
        return None
    seen: dict[int, int] = {}
    for i in range(len(nums)):
        x = nums[i]
        if not isinstance(x, int):
            continue
        j = seen.get(target - x)
        if j is not None: return (j, i)
        seen[x] = i
    return None

function twoSum(nums: ArrayLike<number>, target: number): [number, number] | null {
  if (!Number.isSafeInteger(target) || nums.length < 2) return null;
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const x = nums[i];
    if (!Number.isSafeInteger(x)) continue;
    const j = seen.get(target - x);
    if (j !== undefined) return [j, i];
    seen.set(x, i);
  }
  return null;
}

Flaws & bottlenecks

Still O(n) memory; hardening does not change the asymptotics.
Number.isSafeInteger silently skips non-integers; whether to throw or skip is a product decision that must be documented.
Returns only the first pair; if "all pairs" were required, the output size and duplicate handling change the problem.

Interviewer cross-questions

Can target − x overflow?

Say: In JS, numbers are doubles, so the subtraction is exact only inside ±2⁵³. That is why I guard with Number.isSafeInteger. In Java or C++ I would widen to long, or check x > 0 && target < MIN + x style bounds before subtracting.

How would you optimize memory locality for huge inputs?

Say: Replace Map<number, number> with an open-addressed table over two Int32Arrays (keys and indices) sized to a power of two ≥ 2n. Linear probing keeps probes adjacent in cache and avoids per-entry allocation and GC pressure.

Why a single get() instead of has() then get()?

Say: Halves the hash computations per element and removes a non-null assertion. The cost is that a stored value of undefined would be ambiguous, which cannot happen here because we only store numbers.

Synchronized code walkthrough

Showing: Brute force: all pairs — shares the player above; click any step to jump.

vector<int> twoSum(vector<int>& nums, int target) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] == target) {
                return {i, j};
            }
        }
    }
    return {};
}

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];
}

def two_sum(nums: list[int], target: int) -> list[int]:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

function twoSum(nums: number[], target: number): number[] {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return [];
}

vector<int> twoSum(vector<int>& nums, int target) {
    int n = nums.size();
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b) { return nums[a] < nums[b]; });
    int left = 0;
    int right = n - 1;
    while (left < right) {
        long long sum = (long long)nums[idx[left]] + nums[idx[right]];
        if (sum == target) return {idx[left], idx[right]};
        if (sum < target) left++;
        else right--;
    }
    return {};
}

public int[] twoSum(int[] nums, int target) {
    int n = nums.length;
    Integer[] idx = new Integer[n];
    for (int i = 0; i < n; i++) idx[i] = i;
    Arrays.sort(idx, (a, b) -> Integer.compare(nums[a], nums[b]));
    int left = 0;
    int right = n - 1;
    while (left < right) {
        long sum = (long) nums[idx[left]] + nums[idx[right]];
        if (sum == target) return new int[]{idx[left], idx[right]};
        if (sum < target) left++;
        else right--;
    }
    return new int[0];
}

def two_sum(nums: list[int], target: int) -> list[int]:
    idx = sorted(range(len(nums)), key=lambda i: nums[i])
    left = 0
    right = len(nums) - 1
    while left < right:
        total = nums[idx[left]] + nums[idx[right]]
        if total == target:
            return [idx[left], idx[right]]
        if total < target:
            left += 1
        else:
            right -= 1
    return []

function twoSum(nums: number[], target: number): number[] {
  const idx = nums.map((_, i) => i).sort((a, b) => nums[a] - nums[b]);
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const sum = nums[idx[left]] + nums[idx[right]];
    if (sum === target) return [idx[left], idx[right]];
    if (sum < target) left++;
    else right--;
  }
  return [];
}

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;
    for (int i = 0; i < (int)nums.size(); i++) {
        int need = target - nums[i];
        auto it = seen.find(need);
        if (it != seen.end()) {
            return {it->second, i};
        }
        seen[nums[i]] = i;
    }
    return {};
}

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[0];
}

def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return []

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) {
      return [seen.get(need)!, i];
    }
    seen.set(nums[i], i);
  }
  return [];
}

optional<pair<int, int>> twoSum(const vector<int>& nums, long long target) {
    int n = nums.size();
    if (n < 2 || target < 2LL * INT_MIN || target > 2LL * INT_MAX) return nullopt;
    unordered_map<int, int> seen;
    seen.reserve(2 * n);
    for (int i = 0; i < n; i++) {
        int x = nums[i];
        long long need = target - x;
        if (need < INT_MIN || need > INT_MAX) continue;
        auto it = seen.find((int)need);
        if (it != seen.end()) return pair<int, int>{it->second, i};
        seen.emplace(x, i);
    }
    return nullopt;
}

public static int[] twoSum(int[] nums, long target) { // null if no pair
    if (nums == null || nums.length < 2) return null;
    Map<Integer, Integer> seen = new HashMap<>(nums.length * 2);
    for (int i = 0; i < nums.length; i++) {
        int x = nums[i];
        long need = target - x;
        if (need < Integer.MIN_VALUE || need > Integer.MAX_VALUE) continue;
        Integer j = seen.get((int) need);
        if (j != null) return new int[]{j, i};
        seen.put(x, i);
    }
    return null;
}

def two_sum(nums: Sequence[int], target: int) -> tuple[int, int] | None:
    if not isinstance(target, int) or len(nums) < 2:
        return None
    seen: dict[int, int] = {}
    for i in range(len(nums)):
        x = nums[i]
        if not isinstance(x, int):
            continue
        j = seen.get(target - x)
        if j is not None: return (j, i)
        seen[x] = i
    return None

function twoSum(nums: ArrayLike<number>, target: number): [number, number] | null {
  if (!Number.isSafeInteger(target) || nums.length < 2) return null;
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const x = nums[i];
    if (!Number.isSafeInteger(x)) continue;
    const j = seen.get(target - x);
    if (j !== undefined) return [j, i];
    seen.set(x, i);
  }
  return null;
}