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.
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.
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Contents
- Solution 1 - Store numbers into HashSet, find the starting of a sequence then find the longest consecutive sequence
In the problem statement, we were asked to find a solution with O(n) time complexity, so in this approach first we are going to
store elements into a HashSet, then loop through every element num from array and check if num-1 exists
in the HashSet, if it exists that means this number is not the starting element of the consecutive sequence and if it does not exist then the number
is a starting element of a consecutive sequence and then we will find how long that sequence can be and finally take the longest sequence found.
import java.util.HashSet;
import java.util.stream.IntStream;
public class LongestConsecutiveSequence {
/**
*
* First store elements into a HashSet, then loop through each element in the array and find if
* previous number (num-1) exists in set, if it exists that means that is not the first number of
* a starting sequence, and if previous number does not exist, then this is the first number of a
* starting sequence.
*
* When you find a starting number of sequence, keep checking if next number exists (num+1)
* and find the longest
*/
static int longestConsecutiveUsingHashSet(int[] nums) {
HashSet<Integer> set = new HashSet<>(nums.length);
IntStream.of(nums).forEach(set::add);
int longest =0;
for(int num: nums) {
if(!set.contains(num-1)) {
// if the previous number is not in the set, that means this is the starting of sequence.
int currentLong = 1;
int currentNum = num;
while(set.contains(currentNum+1)) {
currentLong++;
currentNum++;
}
if(currentLong >longest) {
longest = currentLong;
}
}
}
return longest;
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time where n is the input array nums length.
Space complexity: O(n) since we are storing input array into a HashSet.
Above implementations source code can be found at
GitHub link for Java code