Longest Consecutive Sequence


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.
Solution: intuitively, use hash table to get O(n) complexity.
However, the following code is stupid since it continues search duplicated items and the complexity becomes O(n^2).
In order to avoid additional searching, the following code deletes items from the hash table once it has been checked. Since each element will only be accessed once, and the amortized cost of insert/delete/find operations for hash table is O(1), the overall time complexity is linear.

Comments

Popular posts from this blog

Maximum Gap

[ITint5] Maximum Subarray for a Circular Array

[CC150] Chapter 4 Trees and Graphs