1. Two Sum (Easy)

Problem

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume each input has exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example

• nums = [2, 7, 11, 15], target = 9 → [0, 1]
• nums = [3, 2, 4], target = 6 → [1, 2]
• nums = [3, 3], target = 6 → [0, 1]

LeetCode 1 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, try every pair

Iterate all (i, j) pairs with i < j; return when nums[i] + nums[j] == target.

Python

def two_sum(nums: list[int], target: int) -> list[int]:
    n = len(nums)                              # L1: O(1)
    for i in range(n):                         # L2: outer loop, n iterations
        for j in range(i + 1, n):             # L3: inner loop, up to n-i-1 iterations
            if nums[i] + nums[j] == target:    # L4: O(1) check
                return [i, j]                  # L5: O(1) return
    return []

TypeScript

function twoSum(nums: number[], target: number): number[] {
    const n = nums.length;                          // L1: O(1)
    for (let i = 0; i < n; i++) {                  // L2: outer loop, n iterations
        for (let j = i + 1; j < n; j++) {          // L3: inner loop, up to n-i-1 iterations
            if (nums[i] + nums[j] === target)       // L4: O(1) check
                return [i, j];                      // L5: O(1) return
        }
    }
    return [];
}

Go

func twoSum(nums []int, target int) []int {
  n := len(nums)                             // L1: O(1)
  for i := 0; i < n; i++ {                  // L2: outer loop, n iterations
    for j := i + 1; j < n; j++ {          // L3: inner loop, up to n-i-1 iterations
      if nums[i]+nums[j] == target {     // L4: O(1) check
        return []int{i, j}             // L5: O(1) return
      }
    }
  }
  return []int{}
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (len)	$O(1)$	1	$O(1)$
L2 (outer loop)	$O(1)$	n	$O(n)$
L3, L4 (inner loop + check)	$O(1)$	up to n²/2	$O(n²)$ ← dominates
L5 (return)	$O(1)$	1	$O(1)$

The nested loops make this quadratic. For n = 10⁴, that’s ~50 million comparisons.

Complexity

• Time: $O(n²)$, driven by L3/L4 (nested loops).
• Space: $O(1)$.

Swift

final class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        for i in 0..<nums.count {
            for j in (i + 1)..<nums.count where nums[i] + nums[j] == target { return [i, j] }
        }
        return []
    }
}

Approach 2: Sort with remembered indices + two pointers

Sort by value (keeping original indices), then use two pointers from both ends.

Python

def two_sum(nums: list[int], target: int) -> list[int]:
    indexed = sorted(enumerate(nums), key=lambda p: p[1])  # L1: O(n log n)
    l, r = 0, len(indexed) - 1                             # L2: O(1)
    while l < r:                                            # L3: loop, at most n iterations
        s = indexed[l][1] + indexed[r][1]                  # L4: O(1) sum
        if s == target:                                     # L5: O(1) check
            return sorted([indexed[l][0], indexed[r][0]])  # L6: O(1) (2-element sort)
        if s < target:                                      # L7: O(1)
            l += 1                                          # L8: O(1)
        else:
            r -= 1                                          # L9: O(1)
    return []

TypeScript

function twoSum(nums: number[], target: number): number[] {
    const indexed = nums.map((v, i) => [i, v] as [number, number])
        .sort((a, b) => a[1] - b[1]);                      // L1: O(n log n)
    let l = 0, r = indexed.length - 1;                     // L2: O(1)
    while (l < r) {                                         // L3: at most n iterations
        const s = indexed[l][1] + indexed[r][1];           // L4: O(1) sum
        if (s === target)                                   // L5: O(1) check
            return [indexed[l][0], indexed[r][0]].sort((a, b) => a - b); // L6: O(1)
        if (s < target) l++;                               // L7-L8: O(1)
        else r--;                                           // L9: O(1)
    }
    return [];
}

Go

func twoSum(nums []int, target int) []int {
  type iv struct{ idx, val int }
  indexed := make([]iv, len(nums))
  for i, v := range nums {
    indexed[i] = iv{i, v}
  }
  sort.Slice(indexed, func(i, j int) bool { return indexed[i].val < indexed[j].val }) // L1: O(n log n)
  l, r := 0, len(indexed)-1                              // L2: O(1)
  for l < r {                                             // L3: at most n iterations
    s := indexed[l].val + indexed[r].val               // L4: O(1) sum
    if s == target {                                    // L5: O(1) check
      result := []int{indexed[l].idx, indexed[r].idx}
      sort.Ints(result)
      return result                                   // L6: O(1)
    }
    if s < target {                                     // L7: O(1)
      l++                                             // L8: O(1)
    } else {
      r--                                             // L9: O(1)
    }
  }
  return []int{}
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (sort)	$O(n log n)$	1	$O(n log n)$ ← dominates
L2 (init pointers)	$O(1)$	1	$O(1)$
L3-L9 (two-pointer scan)	$O(1)$	at most n	$O(n)$

The sort owns the total cost; the two-pointer scan is linear.

Complexity

• Time: $O(n log n)$, driven by L1 (the sort).
• Space: $O(n)$, the indexed copy.

This is the right approach for LeetCode 167. Two Sum II (input already sorted), where it drops to $O(n)$ time and $O(1)$ space.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        let indexed = nums.enumerated().map { ($0.element, $0.offset) }.sorted { $0.0 < $1.0 }
        var left = 0, right = indexed.count - 1
        while left < right {
            let sum = indexed[left].0 + indexed[right].0
            if sum == target { return [indexed[left].1, indexed[right].1].sorted() }
            if sum < target { left += 1 } else { right -= 1 }
        }
        return []
    }
}

Approach 3: Hash map in a single pass (optimal)

For each element x, look up its complement target - x in a hash map of elements seen so far. If it’s there, we’ve found the pair.

Python

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}                          # L1: O(1), empty dict
    for i, x in enumerate(nums):      # L2: loop, n iterations
        complement = target - x        # L3: O(1) arithmetic
        if complement in seen:         # L4: O(1) average hash lookup
            return [seen[complement], i]  # L5: O(1) return
        seen[x] = i                    # L6: O(1) average hash insert
    return []

TypeScript

function twoSum(nums: number[], target: number): number[] {
    const seen = new Map<number, number>();  // L1: O(1), empty map
    for (let i = 0; i < nums.length; i++) { // L2: loop, n iterations
        const complement = target - nums[i]; // L3: O(1) arithmetic
        if (seen.has(complement))            // L4: O(1) average hash lookup
            return [seen.get(complement)!, i]; // L5: O(1) return
        seen.set(nums[i], i);               // L6: O(1) average hash insert
    }
    return [];
}

Go

func twoSum(nums []int, target int) []int {
  seen := make(map[int]int)          // L1: O(1), empty map
  for i, x := range nums {           // L2: loop, n iterations
    complement := target - x       // L3: O(1) arithmetic
    if j, ok := seen[complement]; ok { // L4: O(1) average hash lookup
      return []int{j, i}         // L5: O(1) return
    }
    seen[x] = i                    // L6: O(1) average hash insert
  }
  return []int{}
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (init dict)	$O(1)$	1	$O(1)$
L2 (loop)	$O(1)$	n	$O(n)$
L3 (arithmetic)	$O(1)$	n	$O(n)$
L4 (hash lookup)	$O(1)$ avg	n	$O(n)$ ← dominates
L5 (return)	$O(1)$	1	$O(1)$
L6 (hash insert)	$O(1)$ avg	up to n	$O(n)$

Every operation is $O(1)$ average per iteration. One pass over n elements gives $O(n)$ total.

Complexity

• Time: $O(n)$, driven by L4/L6 (hash operations per element).
• Space: $O(n)$. Hash map can hold up to n entries.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var seen: [Int: Int] = [:]
        for (index, value) in nums.enumerated() {
            if let match = seen[target - value] { return [match, index] }
            seen[value] = index
        }
        return []
    }
}

Summary

Approach	Time	Space
Brute force	$O(n²)$	$O(1)$
Sort + two pointers	$O(n log n)$	$O(n)$
Hash map	$O(n)$	$O(n)$

The hash-map approach is the canonical answer. It’s strictly better than sort on time and same on space. The sort variant is worth knowing because it generalizes to Two Sum II (sorted) and 3Sum.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_two_sum.py and run.
# Uses the canonical implementation (Approach 3: hash map).

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

def _run_tests():
    assert two_sum([2, 7, 11, 15], 9) == [0, 1]
    assert two_sum([3, 2, 4], 6) == [1, 2]
    assert two_sum([3, 3], 6) == [0, 1]
    assert two_sum([1, 2, 3, 4, 5], 9) == [3, 4]
    # Single-pair array
    assert two_sum([0, 4], 4) == [0, 1]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

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

console.assert(JSON.stringify(twoSum([2, 7, 11, 15], 9)) === JSON.stringify([0, 1]));
console.assert(JSON.stringify(twoSum([3, 2, 4], 6)) === JSON.stringify([1, 2]));
console.assert(JSON.stringify(twoSum([3, 3], 6)) === JSON.stringify([0, 1]));
console.assert(JSON.stringify(twoSum([1, 2, 3, 4, 5], 9)) === JSON.stringify([3, 4]));
console.assert(JSON.stringify(twoSum([0, 4], 4)) === JSON.stringify([0, 1]));
console.log("all tests pass");

Related data structures

• Arrays, input; two-pointer pattern on the sorted variant
• Hash Tables, complement-lookup (the optimal pattern)

Related concepts

• Hash Map Counting, the lookup table pattern for complements, frequencies, and seen items.
• Array Scans, the linear pass habit of carrying just enough state while reading each item once.