Given a list of integers and a target sum, write a function to find two numbers that add up to the target. Return their indices. If no such pair exists, return null.

Overview

The Two Sum problem is one of the most popular coding interview questions. Given an array of integers and a target sum, find two numbers that add up to the target and return their indices.

Example: Given

[2, 7, 11, 15]

9

[0, 1]

2 + 7 = 9

This problem tests your understanding of hash maps, time-space tradeoffs, and algorithmic optimization.

Approach 1: Hash Map (Optimal)

Use a Map to store seen numbers and their indices for O(n) time.

dartCopy
List<int>? twoSum(List<int> nums, int target) {
  Map<int, int> seen = {};

  for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];

    if (seen.containsKey(complement)) {
      return [seen[complement]!, i];
    }

    seen[nums[i]] = i;
  }

  return null;
}

void main() {
  print(twoSum([2, 7, 11, 15], 9));     // [0, 1]
  print(twoSum([3, 2, 4], 6));          // [1, 2]
  print(twoSum([3, 3], 6));             // [0, 1]
  print(twoSum([1, 2, 3], 10));         // null
}

Time Complexity: O(n) - single pass through array Space Complexity: O(n) - hash map storage

Why it works:

• For each number, calculate what value would sum to target (complement)
• Check if complement exists in our seen map
• If yes, return both indices
• If no, store current number with its index

Approach 2: Brute Force

Check all possible pairs. Simple but inefficient.

dartCopy
List<int>? twoSumBruteForce(List<int> nums, int target) {
  for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] == target) {
        return [i, j];
      }
    }
  }
  return null;
}

void main() {
  print(twoSumBruteForce([2, 7, 11, 15], 9));  // [0, 1]
  print(twoSumBruteForce([3, 2, 4], 6));       // [1, 2]
}

Time Complexity: O(n²) - nested loops Space Complexity: O(1) - no extra storage

When to use: Only for very small arrays or educational purposes.

Approach 3: Two Pointers (Sorted Array)

If array is sorted or can be sorted, use two-pointer technique.

dartCopy
class IndexedValue {
  final int value;
  final int originalIndex;
  IndexedValue(this.value, this.originalIndex);
}

List<int>? twoSumSorted(List<int> nums, int target) {
  // Create indexed values to preserve original indices
  List<IndexedValue> indexed = List.generate(
    nums.length,
    (i) => IndexedValue(nums[i], i),
  );

  // Sort by value
  indexed.sort((a, b) => a.value.compareTo(b.value));

  int left = 0;
  int right = indexed.length - 1;

  while (left < right) {
    int sum = indexed[left].value + indexed[right].value;

    if (sum == target) {
      return [indexed[left].originalIndex, indexed[right].originalIndex];
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }

  return null;
}

void main() {
  print(twoSumSorted([2, 7, 11, 15], 9));  // [0, 1]
}

Time Complexity: O(n log n) - sorting dominates Space Complexity: O(n) - indexed values storage

Approach 4: Return All Pairs

Variation: Find all pairs that sum to target (not just first).

dartCopy
List<List<int>> twoSumAllPairs(List<int> nums, int target) {
  Map<int, List<int>> valueIndices = {};
  List<List<int>> result = [];
  Set<String> seen = {};

  // Group indices by value
  for (int i = 0; i < nums.length; i++) {
    valueIndices.putIfAbsent(nums[i], () => []).add(i);
  }

  for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];

    if (valueIndices.containsKey(complement)) {
      for (int j in valueIndices[complement]!) {
        if (i < j) {
          String key = '$i,$j';
          if (!seen.contains(key)) {
            result.add([i, j]);
            seen.add(key);
          }
        }
      }
    }
  }

  return result;
}

void main() {
  print(twoSumAllPairs([1, 2, 3, 2, 1], 3));
  // Output: [[0, 2], [1, 3], [3, 4]]
}

Complete Solution Class

dartCopy
class TwoSumSolver {
  // Optimal: Hash map approach
  static List<int>? solve(List<int> nums, int target) {
    Map<int, int> seen = {};

    for (int i = 0; i < nums.length; i++) {
      int complement = target - nums[i];
      if (seen.containsKey(complement)) {
        return [seen[complement]!, i];
      }
      seen[nums[i]] = i;
    }

    return null;
  }

  // Return values instead of indices
  static List<int>? solveValues(List<int> nums, int target) {
    Map<int, int> seen = {};

    for (int i = 0; i < nums.length; i++) {
      int complement = target - nums[i];
      if (seen.containsKey(complement)) {
        return [complement, nums[i]];
      }
      seen[nums[i]] = i;
    }

    return null;
  }

  // Check if solution exists (no indices needed)
  static bool exists(List<int> nums, int target) {
    Set<int> seen = {};

    for (int num in nums) {
      if (seen.contains(target - num)) {
        return true;
      }
      seen.add(num);
    }

    return false;
  }
}

void main() {
  print(TwoSumSolver.solve([2, 7, 11, 15], 9));        // [0, 1]
  print(TwoSumSolver.solveValues([2, 7, 11, 15], 9));  // [2, 7]
  print(TwoSumSolver.exists([1, 2, 3], 5));            // true
}

Comparison

Edge Cases

dartCopy
void testEdgeCases() {
  // No solution
  assert(twoSum([1, 2, 3], 10) == null);

  // Empty array
  assert(twoSum([], 5) == null);

  // Single element
  assert(twoSum([5], 5) == null);

  // Duplicate values
  assert(twoSum([3, 3], 6) == [0, 1]);

  // Negative numbers
  assert(twoSum([-1, -2, -3, -4, -5], -8)?.length == 2);

  // Zero in array
  assert(twoSum([0, 4, 3, 0], 0) == [0, 3]);

  // Same number used twice (should use different indices)
  assert(twoSum([3, 2, 4], 6) == [1, 2]);  // Not [0, 0]
}

Best Practices

1. Use Hash Map for Optimal Performance

dartCopy
// ✅ Recommended - O(n)
List<int>? twoSum(List<int> nums, int target) {
  Map<int, int> seen = {};
  for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];
    if (seen.containsKey(complement)) return [seen[complement]!, i];
    seen[nums[i]] = i;
  }
  return null;
}

2. Handle Null Safety

dartCopy
List<int>? twoSumSafe(List<int>? nums, int target) {
  if (nums == null || nums.length < 2) return null;
  // ... rest of logic
}

3. Return Early

dartCopy
// ✅ Return as soon as pair is found
if (seen.containsKey(complement)) {
  return [seen[complement]!, i];
}

4. Clear Variable Names

dartCopy
// ✅ Good
int complement = target - nums[i];

// ❌ Bad
int x = target - nums[i];

Interview Tips

Common Follow-ups:

1. "What if the array is sorted?" → Use two-pointer approach (O(n) time, O(1) space)

2. "Find all pairs, not just one?" → Track all pairs while avoiding duplicates

3. "Can same element be used twice?" → Clarify: Usually no (different indices required)

4. "Return values or indices?" → Clarify requirements first

5. "What if no solution exists?" → Return null, empty array, or throw exception (clarify)

Resources

• Two Sum - LeetCode
• Hash Table - Wikipedia
• Dart Map Class