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?
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:
One approach I’ve found useful for problems like this is to look at the requirements:
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:
num is in seen, we’re done hereseen is smaller than the maximum, record num and go onto the next oneseen and carry onI’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
© Copyright Elixir Forum | Terms | Privacy & Cookies
