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.
Best Solution: only scan one direction,
If the number x is the start of a streak (i.e., x-1 is not in the set), then test y = x+1, x+2, x+3, ... and stop at the first number y not in the set. The length of the streak is then simply y-x and we update our global best with that. Since we check each streak only once, this is overall O(n).
public class Solution {
/**
* @param nums: A list of integers
* @return an integer
*/
public int longestConsecutive(int[] num) {
// write you code here
HashSet<Integer> set = new HashSet<Integer>();
for (int elem : num) {
set.add(elem);
}
int longestLen = 0;
for (int n : set) {
if (!set.contains(n-1)) {
int len = 0;
while (set.contains(n)) {
len++;
n++;
}
longestLen = Math.max(longestLen, len);
}
}
return longestLen;
}
}
Union Find (optional), just to know that there's this solution
class Solution {
public int longestConsecutive(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
unionFind uf = new unionFind(nums.length);
for (int i = 0; i < nums.length; i ++) {
uf.fathers[i] = i;
uf.count ++;
if (map.containsKey(nums[i])) continue;
map.put(nums[i], i);
if (map.containsKey(nums[i] - 1)) {
uf.union(i, map.get(nums[i] - 1));
}
if (map.containsKey(nums[i] + 1)) {
uf.union(i, map.get(nums[i] + 1));
}
}
return uf.maxUnion();
}
public class unionFind {
int[] fathers;
int count;
public unionFind(int num) {
this.fathers = new int[num];
Arrays.fill(this.fathers, -1);
this.count = 0;
}
public void union(int i, int j) {
if (isConnected(i, j)) return;
int iRoot = find(i);
int jRoot = find(j);
fathers[iRoot] = jRoot;
this.count --;
}
public int find(int i) {
while (fathers[i] != i) {
i = fathers[i];
}
return i;
}
public boolean isConnected(int i, int j) {
return find(i) == find(j);
}
// returns the maxium size of union
public int maxUnion(){ // O(n)
int[] count = new int[fathers.length];
int max = 0;
for(int i=0; i<fathers.length; i++){
count[find(i)] ++;
max = Math.max(max, count[find(i)]);
}
return max;
}
}
}