Leetcode 128. Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence/

Using hash table. This is actually not very hard. Note the little trick in this solution: when left or right is zero, the lengths[i] will get updated. If its left and right are both existed, actually the length is passed and this number is in the middle hence it is no use afterwards so its length does not need update.

Solution:

# T:O(n) S:O(n)
class Solution:
    # @param num, a list of integer
    # @return an integer
    def longestConsecutive(self, num):
        result, lengths = 1, {key: 0 for key in num}
        for i in num:
            if lengths[i] == 0:
                lengths[i] = 1
                left, right = lengths.get(i - 1, 0), lengths.get(i + 1, 0)
                length = 1 + left + right
                result, lengths[i - left], lengths[i + right] =\
    max(result, length), length, length
        return result

Run Time: 80 ms