LeetCode 1 Two Sum: Imperative C++/Java vs Functional Elixir

First of all, I'm not an Elixir developer, so maybe someone can solve this problem in a more optimal way.

You can find the original post here

You can find the problem description and solutions in all programming languages supported by LeetCode here

The general approach for different programming languages is:

1. For the current nums[i], calculate target - nums[i]
2. Check whether we have seen this number before.
3. If yes, return the two indices.
4. If not, store the current number and its index.

What is more interesting is the difference in implementation in C++ or Java and Elixir.
The biggest conceptual difference here is between the imperative style of C++/Java and the functional style of Elixir with recursion and immutable data.

Let's see two solutions: on Java and Elixir.

Time complexity: O(n)
Space complexity: O(n)

Java

class Solution {
  public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();

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

      Integer index = map.get(val);

      if(index != null) return new int[]{index, i};

      map.put(nums[i], i);
    }

    return new int[]{};
  }
}

Elixir

defmodule Solution do
  @spec two_sum(nums :: [integer], target :: integer) :: [integer]
  def two_sum(nums, target) do
    find(nums, target, %{}, 0)
  end

  defp find([num | rest], target, map, i) do
    val = target - num

    case Map.fetch(map, val) do
      {:ok, index} ->
        [index, i]

      :error ->
        find(rest, target, Map.put(map, num, i), i + 1)
    end
  end

  defp find([], _target, _map, _i), do: []
end

Let's see the difference.

1. C++ and Java use a loop for. Elixir, on the other hand, uses recursion:

find(rest, target, ..., i + 1)

Each recursive call processes one element.

[num | rest]

This means: num is the first element of the list, rest is all remaining elements.

2. Another important difference is immutability.

In C++

map[nums[i]] = i;

we change the existing unordered_map.

In Java

map.put(nums[i], i);

we also change existing Map.

In Elixir map doesn't change and Map.put returns new map, we pass it to the next recursive call:

Map.put(map, num, i)
find(rest, target, Map.put(map, num, i), i + 1)

3. The difference in search.

C++

auto it = map.find(val);
if (it != map.end())

Java

Integer index = map.get(val);
if (index != null)

In Elixir

case Map.fetch(map, val) do
    {:ok, index} ->
    :error ->
end

Map.fetch/2 explicitly returns one of two possible results:

{:ok, index} - found
:error - not found

That is why case is very useful in this situation.

But we also have a solution without recursion using built-in Enum functions:

defmodule Solution do
  @spec two_sum(nums :: [integer], target :: integer) :: [integer]
  def two_sum(nums, target) do
    nums
    |> Enum.with_index()
    |> Enum.reduce_while(%{}, fn {num, i}, map ->
      val = target - num

      case Map.fetch(map, val) do
        {:ok, index} ->
          {:halt, [index, i]}

        :error ->
          {:cont, Map.put(map, num, i)}
      end
    end)
  end
end

The difference is in the way we iterate:

Manual tail recursion - we control the transition to the next element yourself through a recursive call.

Enum abstraction - iteration is handled by built-in Enum functions such as Enum.with_index() and Enum.reduce_while().