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:

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

Blog

Longest Consecutive Sequence

Tammy Vo

Join Our Newsletter. No Spam, Only the good stuff.

Related