Longest Consecutive Sequence

Problem

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.

---

Idea

• Use a hash map to record each element in array num. The value is bool that indicates if the num[i] is checked
• If the element is checked, then continue.
• For each unchecked element in hash map, we change any consecutive elements (both > num[i] and < num[i]) as checked.
• Use local and global parameter to record the longest consecutive sequence

---

Notes

• A method to traverse the array
• A similar method to traverse the vector

---

Solution