Popularity — 1000+ likes on Leetcode … possibly popular
Q(Leetcode #128): Given an unsorted array of integers, find the longest consecutive element sequence, in O(N) time. Eg: given [100, 4, 200, 1, 3, 2] return [1,2,3,4]
I call this the zebra problem because every consecutive sequence of int is a black stripe and the gaps between them are white stripes. We want the widest black stripe. Obviously, each stripe has minimum size 1.
https://github.com/tiger40490/repo1/blob/py1/py/array/zebra.py is my O(N) solution, not tested on Leetcode.
What’s UnionFind? A reusable technique?
Like inserting interval #merging #80% done, I feel this is a data structure problem,
To keep things simple, i will first run one iteration to remove all duplicate items.
I will use hashtable where key a known item. The value is a pointer to a “segment” object.
A segment stores the min and max values. All integers within [min, max] of the segment are always known-items during my scan of input array.
When a new item is either min-1 or max+1, we expand the segment by adjusting the extremes…
The trick is joining two segments, without link pointers. After joining, we don’t really adjust the min/max fields. We only update the max-length global variable if needed.
To keep the hashtable small, I can optionally delete from it but we don’t want to do a range delete within the loop — O(NN)