Leetcode Problem: Longest Consecutive Sequence
Objective:
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.
Pattern: Arrays and Hashing
Approach:
- Create a set to store the elements.
- Get the start of the sequence. The start of a sequence does not have a left neighbor.
- Once we identify a start of a sequence, we can check if the next value exists in the set.
- Keep track of the length of the sequence.
- Return the max length.
Big-O Notation:
Time Complexity: O(n)
We have iterate n times for each element.
Space Complexity: O(n)
We use a Set data structures to store n elements.
Code:
class Solution {
public int longestConsecutive(int[] nums) {
// use hashset to store n values
Set <Integer> hashSet = new HashSet<>();
// maxLength to keep track of longest consecutive sequence
int maxLength = Integer.MIN_VALUE;
// edge case
if (nums.length == 0 || nums.length == 1){
return nums.length;
}
// add all elements into hashset
for(int i : nums){
hashSet.add(i);
}
// get the first sequence
for(int curr : nums){
// does left exist in hashMap
// if it does not then it is the start of a sequence
if(!hashSet.contains(curr - 1)){
int count = 1;
boolean flag = true;
while(flag == true){
if(hashSet.contains(curr + 1)){
count++;
curr++;
} else {
flag = false;
}
maxLength = Math.max(maxLength, count);
}
}
}
return maxLength;
}
}
Top comments (0)