Two sum

code ↗ problem ↗

Given an array of integers, find the two elements in that array which sum to a given target integer, and return the indices of those two elements.

General set-up

Input validation

The problem statement tells us to assume that there is exactly one pair which we are looking for, and that we cannot use the same element twice. That implies two properties of the input array:

• Non-empty. Since the array contains exactly one pair, it must have at least some elements in it.
• Not a single element. Since the same element cannot be used twice, the input array must not be only a single element.

Gleam requires that we handle all patterns for an array, including these two which we are told cannot exist. So, even though the question tells us to assume these, we'll need to encode our answer with a Result type to account for the possible failures. We can then reuse this first step for any of our solutions.

pub fn solution(input: List(Int), target: Int) -> Result(#(Int, Int), Nil) {
  case is_valid_input(input) {
    False -> Error(Nil)
    True -> todo
  }
}

/// Check if an array is a valid input for the two-sum problem.
fn is_valid_input(list: List(Int)) -> Bool {
  case list {
    [] -> False
    [_] -> False
    [_, _, ..] -> True
  }
}

Indexing the elements

We need to keep track of both the elements and their indices, but in Gleam, indexing is an expensive operation; that's because under the hood, every list in Gleam is a singly-linked list, so an indexing operation requires traversing the whole list up to that point.

Thankfully, we have a standard library function list.index_map which can traverse the list in O(n) (so, quickly) and give us the index and the pair as we go. To save ourselves some future annoyances, let's further prepare the input list by transforming each element into an #(Int, Int) pair to explicitly track the index.

 pub fn solution(input: List(Int), target: Int) -> Result(#(Int, Int), Nil) {
-    True -> todo
+    True ->
+      input
+      |> list.index_map(fn(value, index) { #(index, value) })
+      |> todo
 }

Brute-force implementation

The brute-force implementation is the easiest solution: Simply attempt every single pair of elements until you find the one you're looking for. Since we are told to assume there's only one result, we will simply terminate once we find the first pair that matches our desired outcome.

This is obviously unoptimized since we're checking every single pair, but it is a good illustration of how to apply the five recursive problem-solving steps.

In a loop-based language, we can do this with some nested for loops:

for x in xs:
    for y in ys:
        if x.value + y.value == target:
            return x.index, y.index

In Gleam, we'll need to exhaustively go over the list instead, which is a little more syntax.

Five steps to solve the brute force approach

The simplest possible input

The simplest possible input (that still has at least two elements!) is a list with two elements who directly sum up to our target:

let input = [2, 4]
let target = 6

Then how do we check that this works?

1. Take the first element, 2, and the rest of the list, [4].
2. Take the first element of the rest of the list, 4.
3. Does 2 + 4 == 6? It does, so this is a match.
4. Return the index of 2 and the index of 4.

Our base case, then, is that the current head of the list (that is, 2) and the head of the rest of the list (that is, [4]) happen to sum up to the desired target.

Create small examples

We can consider one of the canonical examples from the problem statement:

let input = [3, 2, 4]
let target = 6

In this case, the first index isn't going to be part of the solution, so we have to consider how we handle the rest of the loop.

1. Take the head, 3, and the rest of the list, [2, 4].
   1. Take the head of the rest of the list, 2. Does 3 + 2 == 6? No. So, advance the rest of the list to [4].
   2. Take the head of the rest of the list, 4. Does 3 + 4 == 6? No. So, advance the rest of the list to [].
   3. There's no head for [], so we've proven that 3 is not in the solution.
2. Advance the head to 2, and the rest of the list as [4].
   1. Take the head of the rest of the list, 4. Does 2 + 4 == 6? Yes, so we've found the solution.

This is a straightforward list-traversal.

Relate hard cases to simpler cases

After we've reduced to just the final step, the problem has become the same as our base case; so we can be confident that this is our recursive step, and that our recursion will terminate.

Generalize the pattern

1. Take the current head of the entire list, and the rest of the list as the tail.
2. Search the tail for the complement of the current head (the element which sums to the total.)
   1. If the current candidate is the complement, then return the two indices.
   2. If the current candidate is not the complement, update the tail by removing the current candidate and trying again on the rest of the tail.
3. If no complement is found, advance the head and repeat the process.
4. If you reach the end of the list without finding any complementary pair, then something has gone horribly wrong.

Write the code to combine the cases

Our solution is thus as follows:

fn solve(list: List(Int), target: Int) -> Result(#(Int, Int), Nil) {
    case list {
      // Something has gone terribly wrong
      [] -> Error(Nil)

      // We still have candidates to compare
      [head, ..tail] ->
        case find_complement(tail, look_for: target - head.1) {
          todo
        }
    }
}

If we find the complement, we should return it as a value; if we don't find the complement, we need to indicate failure. This is also a Result!

 fn solve(list: List(Int), target: Int) -> Result(#(Int, Int), Nil) {
     case list {
       // Something has gone terribly wrong
       [] -> Error(Nil)

       // We still have candidates to compare
       [head, ..tail] ->
         case find_complement(tail, look_for: target - head.1) {
-          todo
+          // We found the complement, so we have an answer
+          Ok(complement_index) -> Ok(#(head.0, complement_index))
+
+          // After exhaustively searching the rest of the list, we did not
+          // find a complement, so we need to advance the head to the
+          // next element
+          Error(_) -> solve(tail, target)
         }
     }
 }

This gives us the exact signature we need for the find_complement function.

fn find_complement(
    list: List(#(Int, Int)),
    look_for desired_value: Int,
) -> Result(Int, Nil) {
  case list {
    // There's nothing left to search, so we didn't find the complement.
    [] -> Error(Nil)

    [candidate, ..tail] ->
      case candidate.1 == desired_value {
        // We found the complement, so we return the index for it
        True -> Ok(candidate.0)

        // This isn't the complement, but we still need to check the rest
        // of the list
        False -> find_complement(tail, look_for: desired_value)
      }
  }
}

Complete brute force solution

In total, we get the following:

import gleam/list

pub fn solution(input: List(Int), target: Int) -> Result(#(Int, Int), Nil) {
  case is_valid_input(input) {
    True ->
      input
      |> list.index_map(fn(value, index) { #(index, value) })
      |> solve(target)
    False -> Error(Nil)
  }
}

fn solve(list: List(#(Int, Int)), target: Int) -> Result(#(Int, Int), Nil) {
  case list {
    [] -> Error(Nil)
    [#(index, value), ..tail] ->
      case find_complement(tail, look_for: target - value) {
        Ok(complement_index) -> Ok(#(index, complement_index))
        Error(_) -> solve(tail, target)
      }
  }
}

fn find_complement(
  list: List(#(Int, Int)),
  look_for desired_value: Int,
) -> Result(Int, Nil) {
  case list {
    [] -> Error(Nil)
    [#(index, value), ..tail] ->
      case value == desired_value {
        True -> Ok(index)
        False -> find_matching_value(tail, look_for: desired_value)
      }
  }
}

fn is_valid_input(list: List(Int)) -> Bool {
  case list {
    [] | [_] -> False
    [_, _, ..] -> True
  }
}

Hashmap implementation

The 'optimized' implementation uses a hashmap to retain a record of the elements we have already seen. In languages like C or Python, the hashmap access is in constant time (although hashing is not inexpensive), so a hashmap is essentially "free". Gleam's dicts are not quite constant-time for access, but they are pretty quick, certainly sub-linear, so the loop through the linked list will still dominate the algorithm.

Five steps to solve the hashmap approach

The simplest possible input

As before, our simplest possible input is a case with two elements:

let input = [3, 4]
let target = 7

With the dict approach, we can iterate like so:

1. Take the head 3 and the tail of the list [4], and our dict of known indices, currently empty.
2. The complement of the current head is 7 - 3 = 4.
3. We consult the dict; have we already seen an entry with a value of 4?
   1. We have not.
   2. We add the current head 3 to the dict with the index 0. If we see a value in the future whose complement is 3, we will know where to find it.
4. We move the head forward; the new head is 4 and the tail is []. Our dict of known indices is dict.from_list(#(3, 0)).
5. The complement of the current head is 7 - 4 = 3.
6. We consult the dict; have we already seen an entry with a value of 3?
   1. We have, so we can return the current index and the index of the value 3.
7. The answer is #(0, 1).

Create small examples, relate hard cases to simpler cases, and generalize the pattern

This algorithm is a simple step-forward algorithm, so the "smaller case" will be the rest of the list, and a growing accumulator in the dict. As long as we make sure each forward step gets an accumulated dict passed to it, the next step can rely on the previous work

Write the code to combine the cases

The setup for this is the same as in the brute force approach. Most of our difference lies in the solve function. Since we do not need to iterate over the complete tail every time we step forward, we can significantly simplify the recursion.

fn solve(
  list: List(#(Int, Int)),
  target: Int,
  seen: Dict(Int, Int),
) -> Result(#(Int, Int), Nil) {
  case list {
    // We've reached the end of the list without finding a pair, so something
    // has gone horribly wrong
    [] -> Error(Nil)

    // Step forward
    [#(index, value), ..tail] ->
      case dict.get(seen, target - value) {
        // Since we have seen the complement _previously_, it is guaranteed
        // to have a smaller index.
        Ok(complement_index) -> Ok(#(complement_index, index))

        // We add the current head to the accumulator and step forward
        Error(_) -> solve(tail, target, dict.insert(seen, value, index))
      }
  }
}

That's the whole algorithm!

Complete dict implementation

In total, our solution is:

pub fn solution(input: List(Int), target: Int) -> Result(#(Int, Int), Nil) {
  case is_valid_input(input) {
    True ->
      input
      |> list.index_map(fn(value, index) { #(index, value) })
      |> solve(target, dict.new())
    False -> Error(Nil)
  }
}

fn solve(
  list: List(#(Int, Int)),
  target: Int,
  seen: Dict(Int, Int),
) -> Result(#(Int, Int), Nil) {
  case list {
    [] -> Error(Nil)
    [#(index, value), ..tail] ->
      case dict.get(seen, target - value) {
        Ok(complement_index) -> Ok(#(complement_index, index))
        Error(_) -> solve(tail, target, dict.insert(seen, value, index))
      }
  }
}

/// Check if an array is a valid input for the two-sum problem.
fn is_valid_input(input: List(Int)) -> Bool {
  case input {
    [] | [_] -> False
    [_, _, ..] -> True
  }
}