# 128. Longest Consecutive Sequence (Hard)

https://leetcode.com/problems/longest-consecutive-sequence/

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

```Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is `[1, 2, 3, 4]`. Therefore its length is 4.
```

## Solutions

``````class Solution {

public int longestConsecutive(int[] nums) {
if (nums == null) {
return 0;
}

if (nums.length <= 1) {
return nums.length;
}

// use map to keep the value and its index
Map<Integer, Set<Integer>> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (!map.containsKey(nums[i])) {
map.put(nums[i], new HashSet<>());
}

}

boolean[] visited = new boolean[nums.length];
Arrays.fill(visited, false);

int max = 0;
for (int i = 0; i < nums.length; i++) {
if (visited[i]) {
continue;
}

max = Math.max(max, visit(map, nums[i], visited));
}

return max;
}

private int visit(Map<Integer, Set<Integer>> map, int n, boolean[] visited) {
// if not exist, return 0
if (!map.containsKey(n)) {
return 0;
}

Set<Integer> idx = map.get(n);

for (Integer i : idx) {

// return 0 if any index of value n are visited, do not compute repeatedly.
if (visited[i]) {
return 0;
}

// for these not visited, set visited true and never visit it again.
visited[i] = true;
}

// get the left
int left = visit(map, n - 1, visited);
int right = visit(map, n + 1, visited);

// for different index of same value are all treated as 1, rather than
// the size of index
return left + right + 1;
}
}
``````