LeetCode - Two Sum Problem | Elixir Solution

I’ve started working through problems on LeetCode and wanted to document solutions and details to help others work through the problems with Elixir.

The first problem is called Two Sum.

Problem

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

1. 2 <= nums.length <= 104
2. -109 <= nums[i] <= 109
3. -109 <= target <= 109
4. Only one valid answer exists.

Solution

defmodule Solution do  
  @spec two_sum(nums :: [integer], target :: integer) :: [integer]
  def two_sum(nums, target) do
    Enum.reduce_while(nums, {%{}, 0}, fn num, {acc, index} ->
      diff = target - num

      if Map.has_key?(acc, diff) do
        {:halt, [Map.get(acc, diff), index]}
      else
        acc = Map.put(acc, num, index)
        {:cont, {acc, index + 1}}
      end
    end)
  end
end

TLDR;

Loop over input values storing indices and seen values until a value equal to the difference between the target input and the current value is found.  

When the difference is found, return the indices of the current value and the difference value.

Time Complexity: O(N)

Source: https://github.com/tmartin8080/leet

Approach and Explanation

Walking through the solution, the function accepts 2 arguments: nums and target.

Let’s use the simplest example to illustrate the solution:

nums = [3,3], target = 6

First, we loop over the nums list to add indices (the solution should return the indices):

[3, 3] 
|> [{3, 0}, {3, 1}]

First Iteration

Then, we use reduce_while which can :halt anytime while reducing the new list into an empty map.   The anonymous function is invoked for each element in the list:

fn {3, 0}, %{} -> ... end

We check the difference between the target value and the current num:

diff = 6 - 3

We can then check if the accumulator (short-term storage) map has the difference value:

if Map.has_key?(%{}, 3) do

This returns false because the accumulator is empty.

Next, we store the seen value/index and continue:

{:cont, Map.put(%{}, 3, 0)}

Second iteration

The next element is then processed:

fn {3, 1}, %{3 => 0} -> ... end

But this time, the accumulator includes a value equal to the difference:

diff = 6 - 3

if Map.has_key?(%{3 => 0}, 3) do
  {:halt, [Map.get(%{3 => 0}, 3), 1]}
else
  ...
end

So reduce_while halts, returning the values [0, 1] which are the indices of the values that sum up to the target 6.

Time Complexity

N = size of the array/list

Adding indices to each value in the list requires a full traversal of the array and there is 1 insertion step for each element.

Next, looking at the reduce_while loop, in the worst-case scenario the values we’re looking for are at the end of the array and the second pass over the list will traverse the entire list a second time and here are the steps per iteration:

1 difference step; 1 map lookup; 1 map get/put step;

So we have 4 steps per element in the input array: 4 * N.

In total the steps are: O(1 + 4 * N)and because we drop constants for Big O, the time complexity is:

O(N) or linear time

N    | steps
------------
1    | 5
10   | 50
100  | 500
1000 | 5000

Wrapping up

That's all for the first problem.  We used Enum.reduce_while/3 to keep the solution simple and to traverse the input list only once.

Thanks for reading!

-- Troy

Twitter: @tmartin8080  | ElixirForum