Two-sum: given an array and a target, return the indices of two elements that add up to it. How do you get from O(n²) to O(n), and which edge cases do you test?

29.1.1 · L2 · Interview

Reported at: Meta

Predict first

What does the one-pass dictionary version return for these five inputs?

func twoSum(_ nums: [Int], _ target: Int) -> (Int, Int)? {
    var seen: [Int: Int] = [:]              // value -> index where it was seen
    for (i, n) in nums.enumerated() {
        if let j = seen[target - n] { return (j, i) }
        seen[n] = i                         // store after checking: an element cannot pair with itself
    }
    return nil
}
func show(_ p: (Int, Int)?) -> String { p.map { "(\($0.0), \($0.1))" } ?? "none" }
print(show(twoSum([2, 7, 11, 15], 9)))
print(show(twoSum([3, 3], 6)))
print(show(twoSum([3, 2, 4], 6)))
print(show(twoSum([3], 6)))
print(show(twoSum([], 0)))
  • (0, 1) / (0, 1) / (1, 2) / none / none
  • (0, 1) / none / (1, 2) / none / none
  • (0, 1) / (0, 1) / (0, 2) / (0, 0) / none

Mental model. At a party you are looking for the person whose age completes yours to 60. You keep a list of the ages you have already met, and for each new face you glance at the list instead of asking everyone.

The brute force checks every pair, O(n²) time. The repeated work is “is there a partner for this element?”, and a dictionary answers that in O(1): walk the array once, and for each element look up target - n among the values seen so far (value to index). If it is there, you have the pair; if not, store the current element and move on. Total O(n) time and O(n) memory, one pass. Look up before you store: that order is what stops an element pairing with itself (a single 3 and target 6 must not succeed), while still allowing two separate 3s to match, as the check shows.

Say the assumptions and the edge cases out loud: is there exactly one answer, or must you handle none (return nil, not a crash) or several? Can values repeat, be negative or be zero? Is the array empty or a single element? Could target - n overflow? For extreme Int values it can, and Swift traps on overflow, so mention subtractingReportingOverflow if the inputs are unbounded. If the array is already sorted, two pointers from both ends give O(n) time with O(1) memory. Reported in candidate write-ups at Meta (anonymous, unverified); it is a common opener because it shows whether you reach for a dictionary.

It finds the pair, lets two equal values pair with each other, never pairs an element with itself, and returns nil for a single or empty array.

Common traps

  • Storing the element before looking up its partner. A lone 3 with target 6 then matches itself.
  • Returning values instead of indices, or forgetting to say what to return when there is no pair.

They might follow up with

  • What if I need all pairs, without duplicates? Sort and use two pointers, skipping equal neighbours, or keep a set of pairs already reported.
  • What about three-sum? Sort, fix one element, and run the two-pointer version on the rest: O(n²).

Related questions

  • 29.1.8 When do you use a sliding window, and how do the fixed-size and variable-size versions differ?
  • 29.1.2 Merge overlapping intervals: [[1,3],[8,10],[2,6],[15,18]] becomes [[1,6],[8,10],[15,18]]. How do you do it…
  • 29.2.2 Implement a hash map from scratch (get, set, remove), then extend it: what do you test and how does resizing…

Merge overlapping intervals: [[1,3],[8,10],[2,6],[15,18]] becomes… →