LeetCode 3903 Elixir solution
Previously, I posted a solution to LeetCode 3903 in C++, Java, JavaScript, TypeScript, and Python. Today, I tried to solve it in Elixir. The Time and Space complexities are the same as in those solutions.
Time complexity: O(n)
Space complexity: O(n)
Elixir
defmodule Solution do
@spec first_stable_index(nums :: [integer], k :: integer) :: integer
def first_stable_index(nums, k) do
suffix_min =
nums
|> Enum.reverse()
|> Enum.scan(fn x, acc -> min(x, acc) end)
|> Enum.reverse()
nums
|> Enum.zip(suffix_min)
|> Enum.with_index()
|> find_index(k, 0)
end
defp find_index([], _k, _prefix_max), do: -1
defp find_index([{{num, suffix}, i} | rest], k, prefix_max) do
prefix_max = max(prefix_max, num)
if prefix_max - suffix <= k do
i
else
find_index(rest, k, prefix_max)
end
end
end