Kotlin: Two-Sum — Find Two Numbers That Add Up to a Target

Walk the list once with a HashSet of seen values. For each num, check if target - num is in the set. O(n) time, O(n) memory. Beats the naive O(n²) double loop.

The classic two-sum problem: given a list of integers and a target, find any pair that sums to the target. Copilot's suggested solution is the canonical hashmap approach.

The Copilot prompt

// Find two numbers in the list that add up to the target. Return them as a Pair, or null if none.
fun findTwoNumbersThatAddUpToTarget(numbers: List<Int>, target: Int): Pair<Int, Int>? {

Copilot generates:

fun findTwoNumbersThatAddUpToTarget(numbers: List<Int>, target: Int): Pair<Int, Int>? {
  val seen = mutableSetOf<Int>()
  for (num in numbers) {
    val complement = target - num
    if (complement in seen) {
      return Pair(complement, num)
    }
    seen.add(num)
  }
  return null
}

fun main() {
  val numbers = listOf(2, 7, 11, 15)
  val result = findTwoNumbersThatAddUpToTarget(numbers, 9)
  println(result)   // (2, 7)
}

Walkthrough

The trick is to convert "do these two numbers sum to T" into a single-element check: "is T - num something I've seen before?"

1. val seen = mutableSetOf<Int>(). Start with an empty set.

2. For each num: - Compute the complement — the number that, paired with num, sums to target. - If the complement is already in seen, we have a pair. Return. - Otherwise, add num to seen and continue.

3. If the loop completes without finding a match, return null.

The whole thing is one pass through the list. Set lookup is O(1) amortized. Total: O(n) time.

The naive O(n²) solution

For comparison:

fun findTwoSumNaive(numbers: List<Int>, target: Int): Pair<Int, Int>? {
  for (i in numbers.indices) {
    for (j in i + 1 until numbers.size) {
      if (numbers[i] + numbers[j] == target) {
        return Pair(numbers[i], numbers[j])
      }
    }
  }
  return null
}

Two nested loops, checks every pair. For n = 1000, that's 500,000 iterations. The hashmap version does 1,000.

For very small lists, the naive version may even be faster (no hash overhead). For anything practical, the O(n) version wins.

Returning indices instead

The classic LeetCode version asks for the indices, not the values:

fun twoSumIndices(numbers: List<Int>, target: Int): Pair<Int, Int>? {
  val seen = mutableMapOf<Int, Int>()   // value -> index
  for ((i, num) in numbers.withIndex()) {
    val complement = target - num
    if (complement in seen) {
      return Pair(seen[complement]!!, i)
    }
    seen[num] = i
  }
  return null
}

Same algorithm, but the set becomes a map from value to index. When we find a match, we return the stored index of the complement plus the current index.

Multiple matches

The version above returns the first matching pair. For all matching pairs:

fun allTwoSums(numbers: List<Int>, target: Int): List<Pair<Int, Int>> {
  val pairs = mutableListOf<Pair<Int, Int>>()
  val seen = mutableSetOf<Int>()
  for (num in numbers) {
    val complement = target - num
    if (complement in seen) {
      pairs.add(Pair(complement, num))
    }
    seen.add(num)
  }
  return pairs
}

The same algorithm, but record every match. Note: this gives unordered pairs without duplicates as ordered tuples; for unordered set-style "find {a, b} pairs," handle duplicates explicitly.

Three-sum (related)

fun threeSum(numbers: List<Int>, target: Int): Triple<Int, Int, Int>? {
  val sorted = numbers.sorted()
  for (i in 0 until sorted.size - 2) {
    var left = i + 1
    var right = sorted.size - 1
    while (left < right) {
      val sum = sorted[i] + sorted[left] + sorted[right]
      when {
        sum == target -> return Triple(sorted[i], sorted[left], sorted[right])
        sum < target -> left++
        else -> right--
      }
    }
  }
  return null
}

Sort, then for each i, use the two-pointer technique on the remainder. O(n²). Faster than O(n³) brute force.

Edge cases

• Empty list. No pair possible. Returns null.
• One element. Same — needs at least two.
• Duplicate values. [3, 3] with target = 6. The first pass adds 3 to seen. The second pass: complement = 3, found. Returns (3, 3).
• Same element used twice. [3] with target = 6 doesn't return (3, 3) — the algorithm only pairs distinct indices.
• Negative numbers. Works fine; subtraction handles them.
• Overflow. For very large target and very large numbers, target - num could overflow Int. Use Long for safety.

Common mistakes

Adding num to seen before checking complement. Then [3] with target 6 would match itself. Always check first, then add.

Using List.contains(complement) instead of a Set. That's O(n) per lookup, dropping you back to O(n²) total.

Returning Pair(num, complement) instead of Pair(complement, num). Subtle ordering bug — the complement was found first (it's already in seen), so logically it appears first in the pair. Either order is fine, but pick one and document.

Modifying the input list. The function shouldn't sort or rearrange numbers. The hashmap approach preserves the input.

Forgetting null for "not found." Throwing or returning a sentinel like Pair(-1, -1) makes callers fragile. null + Kotlin's null-safety is the idiom.

Why this is a classic interview problem

• Forces hashmap thinking. Brute force is O(n²); the hashmap drops it to O(n). It's the simplest "trade memory for time" example.
• Edge cases. Duplicates, negatives, overflow — small enough to discuss in 15 minutes.
• Generalizes. Three-sum, four-sum, and target-subset problems all use related techniques.

If you've never solved it without help, do — it's the foundation for many harder problems.

What's next

Episode 14: Count numbers divisible by 7. A count + filter pattern that scales to any "how many match this predicate" question.

Recap

Two-sum in O(n): walk once, keep a Set<Int> of seen values, for each num check if target - num is in the set. The naive O(n²) double-loop also works but slower. For indices, use a Map<value, index> instead. Generalizes to three-sum (sort + two pointers, O(n²)). Edge cases: duplicates handled if you check-before-add; overflow needs Long for huge values.

Next episode: count divisibles.