LeetCode 1 Two Sum Elixir solution

LeetCode problem link: 1. Two Sum

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.

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.putreturns 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.

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

LeetCode 1 Two Sum problem: Elixir solution

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

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().