Two Sum

Exactly one solution. You may not use the same element twice. Return indices of the two numbers such that they add up to target.

We need to return the indices. Create a map where the key is the number value and the value is its index.

Iterate over numbers: store visited numbers and their indices in the map.

As you iterate, check whether current number has a complement in the map that adds up to target. If it does, return the indices. If it doesn't, add number to the map.

Complexity analysis: \(n\) is the number of elements in the list.

  • Time complexity: \(O(n)\), as you might iterate over the whole list.
  • Space complexity: \(O(n)\), as you might need to store almost all elements and their indices in the map.

Other solutions:

  • Brute force: double loop, return when the two numbers add up to the target.
    • Time complexity: \(O(n^2)\), for each of $n$ elements, we try to find its complement by looping through the rest of the list.
    • Space complexity: \(O(1)\), no extra space that depends on the input size is necessary.
  • Sort list first, then on a sorted list, find values with two pointers (from start and end).
    • Time complexity: \(O(n \log n)\), because sort \(O(n \log n)\) + two pointers \(O(n)\).
    • Space complexity: \(O(n)\), sort and two-pointers would be possible with \(O(1)\), but we need to store original indices \(O(n)\).
    • This solution, as the list is not already sorted and we need to return the original indices, is fairly complicated, and doesn't perform too well (neither in space nor time complexity).
/// Given an array of integers [numbers] and an integer [target],
/// returns the indices of the two numbers such that they add up to [target].
List<int> twoSum(List<int> numbers, int target) {
  // The key is the number, the value is the index of this number in the
  // original [numbers] list.
  final map = <int, int>{};

  for (var i = 0; i < numbers.length; i++) {
    final number = numbers[i];
    final complementIndex = map[target - number];

    if (complementIndex != null) return [complementIndex, i];

    map[number] = i;
  }

  throw ArgumentError('Input violates assumption: exactly one solution');
}