Longest Consecutive Sequence @LeetCode

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.

	package leetcode.array;
	import java.util.Arrays;
	import java.util.HashMap;
	/**
	* Solution: HashMap Space O(n) Time Complexity O(n) -- 限制O(n), 排序是O(nlog(n)) ---> 必定是空间换时间
	* {100, 2, 3, 200, 1, 4}, For a give number 2
	* first search increasing consecutive(right side), 3,4
	* then search descending consecutive(left side), 1.
	* Every node in the sequence has been visited, next time it will be skipped.
	* At most, we will visit n node. --> O(n)
	*
	* Another ways is Sort and find longest increasing sequence. O(nlog(n)) Time. O(1) Space
	*
	* @author jeffwan
	* @date Apr 15, 2014
	*/
	public class LongestConsecutive {
	public int longestConsecutive(int[] num) {
	if (num == null || num.length == 0) {
	return 0;
	}
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	for (int value : num) {
	map.put(value, 0);
	}
	int maxLength = 1;
	for (int i : num) {
	if (map.get(i) == 1) {
	continue;
	}
	// Search Increasing sequence for current element(right side)
	int temp = i;
	int current_max = 1;
	while (map.containsKey(temp + 1)) {
	current_max++;
	temp++;
	map.put(temp, 1);
	}
	// Search Descending sequence for current element(left side)
	temp = i;
	while (map.containsKey(temp - 1)) {
	current_max++;
	temp --;
	map.put(temp, 1);
	}
	maxLength = Math.max(current_max, maxLength);
	}
	return maxLength;
	}
	}

view raw LongestConsecutive.java hosted with ❤ by GitHub