LeetCode-in-All

128. Longest Consecutive Sequence

Medium

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2]

Output: 4

Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]

Output: 9

Constraints:

Solution

defmodule Solution do
  @spec longest_consecutive(nums :: [integer]) :: integer
  def longest_consecutive(nums) do
    nums 
      |> Enum.sort()
      |> count_consecutive([1])
      |> Enum.max() # find max 
  end

  defp count_consecutive(nums = [head_1, head_2 | tail], 
                         seq_lens = [seq_head | _seq_tail]) do
    new_len = 
      case (head_1 - head_2) do
        -1 -> seq_head + 1 # element is consecutive, increment
        0  -> seq_head     # element is same, do nothing
        _  -> 1            # element not consecutive, reset count
      end

    # Prepend count of consecutive elements
    count_consecutive([head_2 | tail], [new_len | seq_lens]) 
  end

  defp count_consecutive([_h | []], seq_lens), do: seq_lens # terminates when list is empty

  defp count_consecutive([], [_h | []]), do: [0] # runs if list has single number
end