DEV Community

Tammy Vo
Tammy Vo

Posted on

1 1

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){
            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;
    }
}
Enter fullscreen mode Exit fullscreen mode

AWS GenAI LIVE image

Real challenges. Real solutions. Real talk.

From technical discussions to philosophical debates, AWS and AWS Partners examine the impact and evolution of gen AI.

Learn more

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay