Canonical Deep-Dive: Two Sum

Problem: Two Sum (https://leetcode.com/problems/two-sum/) The lesson: every solution has a price, and naming that price is the skill.

This is a guided walk-through, not an answer key. It explains how to think about three approaches and what each costs. You write the actual Python yourself, in your own work repo. The tutor will not confirm your code; LeetCode’s judge will.

Restated: given an array of integers nums and a target, return the indices of the two numbers that add to the target. Exactly one answer exists, and you may not reuse the same element.

Approach 1: Brute force

The most direct idea: try every pair.

for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        if nums[i] + nums[j] == target:
            return [i, j]
  • Time: O(n^2). For each of n elements you scan the rest.
  • Space: O(1). No extra structure.

This is your baseline. Always have a baseline; you improve from something, not from nothing. Write it, run it, feel it get slow as n grows.

Approach 2: Sort, then two pointers

If the array were sorted, you could put one pointer at each end and walk them inward: if the pair sums too high, move the right pointer left; too low, move the left pointer right. The catch is that the problem wants the original indices, and sorting destroys them. The fix is to sort (value, original_index) pairs so you can still report where each number came from.

  • Time: O(n log n), dominated by the sort.
  • Space: O(n) to hold the value-index pairs.

This approach is not the fastest here, but it teaches the two-pointer move you will use heavily in Week 2, and it shows that “sort first” is a real tool with a real cost.

Approach 3: Hash map, one pass

Here is the insight that makes this an Arrays-and-Hashing problem. As you scan left to right, for the current number x you are really asking one question: “have I already passed a number equal to target - x?” A hash map answers that in O(1).

The shape of it, in words (you write the code):

  • Keep a map from value seen so far to its index.
  • For each number, compute its complement (target - number). If the complement is already a key in the map, you have found the pair; return the stored index and the current index.
  • Otherwise, record the current number and its index in the map, and move on.

Why one pass is correct: you only ever look for a partner among numbers that came before you, and every earlier number has already been recorded. You never need the full map up front.

  • Time: O(n). One pass, O(1) work per element.
  • Space: O(n) for the map.

Your work this week

  1. Implement all three approaches yourself, each in its own file in your work repo (for example two-sum-bruteforce.py, two-sum-sort.py, two-sum-hash.py).
  2. Generate a large input (n = 10000) and time each one. Watch the O(n^2) approach fall behind.
  3. Write a short reflection (about 200 words), “What I learned from solving Two Sum three ways,” in your work repo. Future canonical deep-dives build on this habit.
  4. Commit each approach with a five-question debrief in the message.

When you can explain, from memory and with no AI open, why the one-pass map is correct and what it trades for its speed, you own this problem. That explanation is exactly what an interviewer will ask for.