Posts Longest Consecutive Sequence
Post
Cancel

Longest Consecutive Sequence

This question is part of NeetCode150 series.

Problem Description

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. leetcode

Solution

APPROACH 1

The brute force solution for this problem can be so loop through every element in the array and track the max length/streak possible. We can do better in terms of time complexity by first sorting the array. However, there is one key observation which can make the solution optimal. An element X can be the beginning of a streak only if the (X-1) is not present in the array. To make this lookup better, we can use HashSet. Only when we get any element which can be the start of a streak, we will continue our count.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    
    public int longestConsecutive(int[] nums) {
        
        Set<Integer> set = new HashSet<>();
        
        for(int i=0; i<nums.length; i++){
            set.add(nums[i]);
        }
        
        int maxLength=0;
        
        for(Integer x: set){
            
            //x can be the start of a streak as (x-1) is not in the HashSet
            if(!set.contains(x-1)){
                
                int currentLength=1;
                
                while(set.contains(x+1)){
                    currentLength++;
                    x++;
                }
                
                maxLength = Math.max(currentLength, maxLength);
                
            }
            
        }
        
        return maxLength;
        
    }
}

APPROACH 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public int longestConsecutive(int[] nums) {
        
        int n = nums.length;

        // Create a HashSet to store all unique elements from the array
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++)
            set.add(nums[i]);

        int maxLength = 0; // Initialize the maximum length of consecutive sequence found so far
        int currentLength = 0; // Initialize the current length of consecutive sequence

        // Loop through each element in the array
        for (int i = 0; i < n; i++) {

            // Get the current element
            int current = nums[i]; 

            // Remove the current element from the set to avoid unnecessary reprocessing
            set.remove(current);

            // Start counting the current consecutive sequence from the current element itself
            currentLength = 1;

            int left = current - 1; // Look for consecutive elements on the left side of the current element
            int right = current + 1; // Look for consecutive elements on the right side of the current element

            // Check for consecutive elements to the left of the current element
            while (set.contains(left)) {
                currentLength++;
                set.remove(left); // Remove the element from the set to avoid reprocessing
                left--;
            }

            // Check for consecutive elements to the right of the current element
            while (set.contains(right)) {
                currentLength++;
                set.remove(right); // Remove the element from the set to avoid reprocessing
                right++;
            }

            // Update the maxLength with the maximum between the currentLength and the previous maxLength
            maxLength = Math.max(maxLength, currentLength);
        }

        return maxLength;
    }
}
This post is licensed under CC BY 4.0 by the author.