128. Longest Consecutive Sequence

Question

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

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Quick Hints

• Use a Set to store numbers and do a constant lookup
• Determine length of sequence only for the start of sequence num - 1
• Length increases if num + 1 exists in the Set

Solution

Time complexity

O(n)

Space complexity

O(n)

Notes