Check if array contains nearby duplicates

In elixir you can pattern match on a list:

def myfun([first_item, second_item | tail]) do

end

Then, you would use recursion to traverse the whole list.

Does it help?

You could group values by their indexes and for each grouped values, recursively iterate with a look ahead pointer on a list that has at least two elements comparing if the indexes abs diff is <= k, if you do all of this lazily and then try to take at least 1 and if it’s not an empty list then you’ve found one pair of indexes.

I think something like this would do it:

defmodule Solution do
  defp has_index_diff_le?(values, k) do
    case values do
      [index1, index2 | rest] ->
        case abs(index2 - index1) <= k do
          true -> true
          false -> has_index_diff_le?([index2 | rest], k)
        end

      _ ->
        false
    end
  end

  def contains_dup?(values, k) do
    result =
      values
      |> Stream.with_index()
      |> Enum.group_by(fn x -> elem(x, 0) end, fn x -> elem(x, 1) end)
      |> Map.values()
      |> Stream.filter(&match?([_head | _tail], &1))
      |> Stream.map(fn vals -> has_index_diff_le?(vals, k) end)
      |> Stream.drop_while(&(&1 == false))
      |> Stream.take(1)
      |> Enum.to_list()

    case result do
      [] -> false
      [_] -> true
    end
  end
end

false = [1, 2, 3, 4, 2] |> Solution.contains_dup?(1)
false = [1, 2, 3, 4, 2] |> Solution.contains_dup?(2)
true = [1, 2, 3, 4, 2] |> Solution.contains_dup?(3)
false = [1, 2, 3, 4] |> Solution.contains_dup?(4)
true = [1, 0, 1, 1] |> Solution.contains_dup?(1)

Isn’t your solution a bit complicated?

Based on your example I wrote my own solution using pattern-matching, [head | tail] notation and recursion as suggested by @lud. Since all checks are guard and the list is iterated only once my version should be much more faster.

First of all we can add index and perform all checks in one call. Secondly we do not need to store old index that failed our checks. Only noticing it allows us to much reduce out code.

defmodule Example do
  # function head for shared default argument values
  def sample(nums, k, acc \\ %{}, current_index \\ 1)

  # when check failed for all nums return false
  def sample([], _k, _acc, _current_index), do: false

  # check if num is in acc and then
  # check if abs of expression
  # current index - last saved index for same num
  # is less or equal to k
  def sample([num | _nums], k, acc, current_index)
      when is_map_key(acc, num) and abs(current_index - :erlang.map_get(num, acc)) <= k do
    true
  end

  # otherwise save current index in acc for this num
  # and continue checking rest nums
  def sample([num | nums], k, acc, current_index) do
    sample(nums, k, Map.put(acc, num, current_index), current_index + 1)
  end
end

false = [1, 2, 3, 4, 2] |> Example.sample(1)
false = [1, 2, 3, 4, 2] |> Example.sample(2)
true = [1, 2, 3, 4, 2] |> Example.sample(3)
false = [1, 2, 3, 4] |> Example.sample(4)
true = [1, 0, 1, 1] |> Example.sample(1)

Helpful resources:

1. Elixir official page |> Getting Started |> Recursion
2. Elixir documentation |> Pages |> Patterns and Guards
3. :erlang.map_get/2
4. Kernel.abs/1
5. Kernel.is_map_key/2
6. Map.put/3

One approach I’ve found useful for problems like this is to look at the requirements:

• this needs to loop over each element of the input
• needs to maintain state between elements of the input to track what’s already been seen
• can stop early (if a duplicate is detected)

A tool that matches these requirements is Enum.reduce_while/3, a skeleton of a use for it would look something like:

Enum.reduce_while(nums, SOME_STATE_NOT_DECIDED_YET, fn num, STATE ->
  if SHOULD_STOP?(num, STATE) do
    {:halt, true}
  else
    {:cont, UPDATE_STATE(num, STATE)}
  end
end)
|> case do
  true -> true
  _STATE_DONT_CARE -> false
end

The bits in all-caps are going to vary based on the problem, but this is the general idea. The final case handles the situation when the reduce_while makes it to the end and returns whatever shape the “state” is.

A simple example for using this approach is “Contains Duplicate” (the prequel to “Contains Duplicate II”). A solution for that might look like:

Enum.reduce_while(nums, MapSet.new(), fn num, seen ->
  if MapSet.member?(seen, num) do
    {:halt, true}
  else
    {:cont, MapSet.put(seen, num)}
  end
end)
|> case do
  true -> true
  _ -> false
end

In this case the “state” is a single MapSet, allowing for quick checking of “is this new num one that’s already been seen?”

For “Contains Duplicate II”, the set of “seen” elements needs to be restricted to a maximum size k. When a k+1th element is seen, the oldest one needs to be dropped.

This isn’t possible with MapSet alone; it does not provide guarantees about element ordering. To handle it, we need a second piece of “state”: a queue of numbers that can answer “what element did we see k elements ago?” efficiently.

The :queue module is a decent starting point with better performance characteristics than a plain List when values are removed from the opposite end.

Another useful piece of information: the size of a MapSet is efficiently computable, especially compared to :queue.len which is O(k).

A solution for part 2 might look like (I have not run this code, beware):

Enum.reduce_while(nums, {MapSet.new(), :queue.new()}, fn num, {seen, last_seen} ->
  cond do
    MapSet.member?(seen, num) ->
      {:halt, true}

    MapSet.size(seen) < k ->
      {:cont, {MapSet.put(seen, num), :queue.in(num, last_seen)}

    true ->
      {{:value, very_last_seen}, last_seen} = :queue.out(last_seen)

      seen = MapSet.delete(seen, very_last_seen)

      {:cont, {MapSet.put(seen, num), :queue.in(num, last_seen)}    
  end
end)
|> case do
  true -> true
  _ -> false
end

The if in the skeleton has split into a 3-way cond:

• if num is in seen, we’re done here
• if seen is smaller than the maximum, record num and go onto the next one
• otherwise remove the oldest number from seen and carry on

I’d likely extract parts of this to a function, but I kept everything inline for this discussion to show the similarities.

Perhaps not the most efficient, but quite straightforward

nums
|> Stream.chunk_every(k, 1, :discard)
|> Enum.any?(&( &1 |> MapSet.new() |> MapSet.size() != k))

defmodule Test do
  def test([], _), do: false
  def test([h | t], l), do: test(t, h, 1, 0, t, l)
  defp test([h | _], h, i, j, _, l) when abs(i - j) <= l, do: true
  defp test([_ | t], x, i, j, vs, l), do: test(t, x, i + 1, j, vs, l)
  defp test([], _, _, j, [x | vs], l), do: test(vs, x, j + 1, j, vs, l)
  defp test([], _, _, _, [], _), do: false
end 

true = Test.test([1,2,3,1], 3)
true = Test.test([1,0,1,1], 1)
false = Test.test([1,2,3,1,2,3], 2)

to my eyes, this is O(n^2)

This solution doesn’t pass all cases, unfortunately..
false = ([1,2,3,1], 3) → supposed to be true
false = ([1,0,1,1], 1) → supposed to be true
false = Test.test([1,2,3,1,2,3], 2) → correct

Thank you for the detailed explanation. This solution works with some minor syntax adjustment.

def contains_nearby_duplicate(nums, k) do
    Enum.reduce_while(nums, {MapSet.new(), :queue.new()}, fn num, {seen, last_seen} ->
        cond do
          MapSet.member?(seen, num) ->
            {:halt, true}

          MapSet.size(seen) < k ->
            {:cont, {MapSet.put(seen, num), :queue.in(num, last_seen)}}

          true ->
            {{:value, very_last_seen}, last_seen} = :queue.out(last_seen)

            seen = MapSet.delete(seen, very_last_seen)

            {:cont, {MapSet.put(seen, num), :queue.in(num, last_seen)}}
        end
      end)
    |> case do
      true -> true
      _ -> false
    end
end

I like this suggestion, works just fine and is quite easy for me to understand. Thanks for the resources.

Ah, a classic “fencepost” error. The original problem was specified with indicies and I solved for count. Simple fix: use k+1 where I previously used k

iex(12)> tryme = fn nums, k ->
...(12)> nums
...(12)> |> Stream.chunk_every(k+1, 1, :discard)
...(12)> |> Enum.any?(&( &1 |> MapSet.new() |> MapSet.size() != k+1))
...(12)> end
#Function<41.3316493/2 in :erl_eval.expr/6>
iex(13)> tryme.([1,2,3,1], 3)
true
iex(14)> tryme.([1,0,1,1], 1)
true
iex(15)> tryme.([1,2,3,1,2,3], 2)
false