### 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.

### Stats

Frequency | 3 |

Difficulty | 4 |

Adjusted Difficulty | 4 |

Time to use | just coding is easy |

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

**I did not solve this question**. We are going to make use of **HashSet**.

Information on HashSet from official document:

java.util.HashSetThis class

implements the Set interface, backed by ahash table(actually a HashMap instance). It makes no guarantees as to theiteration orderof the set; in particular, it does not guarantee that the order will remain constant over time. This class permits thenull element.This class offers

constant time performancefor the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets. Iterating over this set requires time proportional to the sum of the HashSet instance’s size (the number of elements) plus the “capacity” of the backing HashMap instance (the number of buckets). Thus, it’s very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.Note that this implementation is

not synchronized. If multiple threads access a hash set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.

**To summarize it, HashSet**:

implements Set interface

implemented by using a hash table

un-ordered

add, remove and contains methods have constant time O(1)

can have null element

not sync

### Solution

**Well explained in this site**.

Dump everything to a hash set.

Now go through the hashset. For each element, look up the set for all values neighboring the current value. Keep track of the largest sequence you can find, while removing the elements found from the set. Save the count for comparison.

Repeat this until the hashset is empty.

Assuming lookup, insertion and deletion are O(1) time, this algorithm would be O(N) time.

**Updated on July 4th, 2014**: Look at the 2nd for-loop. Here if I do ‘for (Integer in: set)’ to iterate all numbers, I will get “java.util.ConcurrentModificationException ”. This is because we are iterating while modifying. **The most tricky part of this solution is iteration thru the array**, instead of the set. Take note of that!

### Code

```
public int longestConsecutive(int[] num) {
int longest = 1;
HashSet<Integer> set = new HashSet<Integer>();
for (Integer in: num) set.add(in);
for (Integer in: num) {
int left = in - 1, right = in + 1;
while (set.contains(left)) {
set.remove(left);
left --;
}
while (set.contains(right)) {
set.remove(right);
right ++;
}
longest = Math.max(longest, right - left - 1);
}
return longest;
}
```