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<>());
}
map.get(nums[i]).add(i);
}
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;
}
}