Last updated on February 2nd, 2025 at 06:03 am

Here, we see a Longest Consecutive Sequence LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Union-Find

Companies

Facebook, Google

Level of Question

Medium

Longest Consecutive Sequence LeetCode Solution

1. Problem Statement

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.

Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is “Hashing and Sorting for Sequence Detection”. The Python implementation, however, uses a HashSet-based approach to optimize the solution by avoiding sorting and directly checking for consecutive elements.

3. Code Implementation in Different Languages

3.1 Longest Consecutive Sequence C++

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int n = nums.size();
        if(n == 0){
            return 0;
        }
        sort(nums.begin(), nums.end());
        int currentConsecutiveSequence = 1;
        int longestConsecutiveSequence = 0;
        for(int i=1; i<n; i++){
            if(nums[i] != nums[i-1]){
                if(nums[i] == nums[i-1] + 1){
                    currentConsecutiveSequence++;
                }
                else{
                    longestConsecutiveSequence = max(longestConsecutiveSequence, currentConsecutiveSequence);
                    currentConsecutiveSequence = 1;
                }
            }
        }
        return max(longestConsecutiveSequence, currentConsecutiveSequence);
    }
};

3.2 Longest Consecutive Sequence Java

class Solution {
    public int longestConsecutive(int[] nums) {int result = 0;
        if (nums.length > 0) {
            if (nums.length < 1000) {
                Arrays.sort(nums);
                int current = 0;
                for (int i = 1; i < nums.length; i++) {
                    if (nums[i] != nums[i - 1]) {
                        if (nums[i] - nums[i - 1] == 1) {
                            current++;
                        } else {
                            if (current + 1 > result) {
                                result = current + 1;
                            }
                            current = 0;
                        }
                    }
                }
                if (current + 1 > result) {
                    result = current + 1;
                }
            } else {
                int min = Integer.MAX_VALUE;
                int max = Integer.MIN_VALUE;
                for (int num : nums) {
                    if (num > max) {
                        max = num;
                    }
                    if (num < min) {
                        min = num;
                    }
                }
                byte[] bits = new byte[max - min + 1];
                for (int num : nums) {
                    bits[num - min] = 1;
                }
                int current = 0;
                for (byte bit : bits) {
                    if (bit > 0) {
                        current++;
                    } else {
                        if (current > result) {
                            result = current;
                        }
                        current = 0;
                    }
                }
                if (current > result) {
                    result = current;
                }
            }
        }
        return result;
    }
}

3.3 Longest Consecutive Sequence JavaScript

var longestConsecutive = function(nums) {
    if(nums.length==0) return 0
    let count=1, max = 1
    nums.sort((a, b) => a - b)
    for(let i=0; i<nums.length; i++) {
        if(nums[i]- nums[i-1] == 1) {
            count=count+1 ;
            max = Math.max(max, count)
        } 
        else if(nums[i]==nums[i-1]) continue
        else {
            count = 1
        }
    }
    return max
};

3.4 Longest Consecutive Sequence Python

class Solution(object):
    def longestConsecutive(self, nums):
        longest = 0
        num_set = set(nums)
        for n in num_set:
            if (n-1) not in num_set:
                length = 1
                while (n+length) in num_set:
                    length += 1
                longest = max(longest, length)
        return longest

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n log n)	O(1)
Java	O(n log n)	O(n)
JavaScript	O(n log n)	O(1)
Python	O(n)	O(n)