Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9
Example 3:
Input: nums = [1,0,1,2] Output: 3
Constraints:
0 <= nums.length <= 105-109 <= nums[i] <= 109class Solution {
public int longestConsecutive(int[] nums) {
Arrays.sort(nums);
int n = nums.length, streak = 1, ans = 0;
if (n == 0)
return 0;
for (int i = 0; i < n - 1; i++) {
if (nums[i + 1] == nums[i])
;
else if (nums[i + 1] - nums[i] == 1)
streak++;
else {
ans = Math.max(ans, streak);
streak = 1;
}
}
return Math.max(ans, streak);
}
}class Solution {
private class UnionFind {
Map<Integer, Integer> root = new HashMap<>();
Map<Integer, Integer> rank = new HashMap<>();
UnionFind(int[] nums) {
for (int i : nums) {
root.put(i, i);
rank.put(i, 1);
}
}
private int find(int x) {
int rootX = root.get(x);
if (rootX == x)
return x;
int head = find(rootX);
root.put(x, head);
return head;
}
private void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
int rankX = rank.get(x), rankY = rank.get(y);
if (rankX < rankY)
root.put(rootY, rootX);
else if (rankX > rankY)
root.put(rootX, rootY);
else {
root.put(rootY, rootX);
rank.put(rootX, rank.get(rootX) + 1);
}
}
}
private boolean connected(int x, int y) {
return find(x) == find(y);
}
private boolean validKey(int x) {
return root.containsKey(x);
}
private int getMaxFreq() {
Map<Integer, Integer> freq = new HashMap<>();
for (Integer key : root.keySet()) {
int head = find(key);
freq.put(head, freq.getOrDefault(head, 0) + 1);
}
int ans = 0;
for (Integer value : freq.values())
ans = Math.max(ans, value);
return ans;
}
}
public int longestConsecutive(int[] nums) {
UnionFind uf = new UnionFind(nums);
for (int i : nums) {
if (uf.validKey(i - 1))
uf.union(i, i - 1);
if (uf.validKey(i + 1))
uf.union(i, i + 1);
}
// System.out.println(uf.root);
return uf.getMaxFreq();
}
}class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = IntStream.of(nums).boxed().collect(Collectors.toSet());
int ans = 0;
for (int i : set) {
if (!set.contains(i - 1)) {
int streak = 1, prev = i;
while (set.contains(++prev))
streak++;
ans = Math.max(streak, ans);
}
}
return ans;
}
}