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.

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)