# Longest Consecutive Sequence

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:

1. Create a set to store the elements.
2. Get the start of the sequence. The start of a sequence does not have a left neighbor.
3. Once we identify a start of a sequence, we can check if the next value exists in the set.
4. Keep track of the length of the sequence.
5. 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){
}

// 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;
}
}
``````