LC-0128 Medium LeetCode

128. Longest Consecutive Sequence

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 47% Topics: Array, Hash Table, Union Find

Reading material

Arrays & Hashing 12 min Union–Find (DSU) 12 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    # @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

Solution from kamyu104/LeetCode-Solutions · MIT