Question
Formatted question description: https://leetcode.ca/all/128.html
128. Longest Consecutive Sequence
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.
@tag-array
Algorithm
For every num existed in set, try to probe to right to see if following numbers are also in set, and record longest possible sequence.
Code
Java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class Longest_Consecutive_Sequence {
// Time complexity : O(n)
// Space complexity : O(n)
class Solution_oN {
public int longestConsecutive(int[] nums) {
Set<Integer> hs = new HashSet<Integer>();
// remove duplicates
for (int num : nums) {
hs.add(num);
}
int longestStreak = 0;
for (int num : hs) {
if (!hs.contains(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while (hs.contains(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
}
}
class Solution_sort {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) {
return 0;
}
Arrays.sort(nums);
int longestStreak = 1;
int currentStreak = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[i-1]) {
if (nums[i] == nums[i-1]+1) {
currentStreak += 1;
}
else {
longestStreak = Math.max(longestStreak, currentStreak);
currentStreak = 1;
}
}
}
return Math.max(longestStreak, currentStreak);
}
}
}