Question

link

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

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

This class offers constant time performance for 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:

1. implements Set interface

2. implemented by using a hash table

3. un-ordered

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

5. can have null element

6. 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;
}