DEV Community

Tammy Vo
Tammy Vo

Posted on

Longest Consecutive Sequence

Leetcode Problem: Longest Consecutive Sequence


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


  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.


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)){
                    } else {
                        flag = false;
                    maxLength = Math.max(maxLength, count);
        return maxLength;
Enter fullscreen mode Exit fullscreen mode

Top comments (0)