# Check if array contains nearby duplicates

Hi all, I’m trying to solve this leetcode question in elixir. Contains Duplicate II - LeetCode

Given an integer array `nums` and an integer `k` , return `true` if there are two distinct indices `i` and `j` in the array such that `nums[i] == nums[j]` and `abs(i - j) <= k` .

The java solution is available but it was quite complicated for me to convert to elixir… Could anyone give me some hints or explanations on how to solve it in elixir?

1 Like

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?

3 Likes

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

``````
2 Likes

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)
``````

3 Likes

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+1`th 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.

4 Likes

Perhaps not the most efficient, but quite straightforward

``````nums
|> Enum.any?(&( &1 |> MapSet.new() |> MapSet.size() != k))
``````
2 Likes
``````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)

2 Likes

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