0128-longest-consecutive-sequence.rb

# frozen_string_literal: true

# 128. Longest Consecutive Sequence
# https://leetcode.com/problems/longest-consecutive-sequence
# Medium

=begin
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:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
=end

# @param {Integer[]} nums
# @return {Integer}
deflongest_consecutive(nums)
return0ifnums.empty?
nums.sort.uniq.each_cons(2).inject([1,1]){ |(maxl,curl),(v1,v2)|
(v1 + 1 == v2) ? [[maxl,curl + 1].max,curl + 1] : [maxl,1]
}.first
end

# **************** #
# TEST #
# **************** #

require"test/unit"
classTest_longest_consecutive < Test::Unit::TestCase
deftest_
assert_equal4,longest_consecutive([100,4,200,1,3,2])
assert_equal9,longest_consecutive([0,3,7,2,5,8,4,6,0,1])
end
end