128. Longest Consecutive Sequence

Intuition

The problem requires finding the length of the longest consecutive elements sequence in an unsorted array. A naive approach would involve sorting the array, which would take O(n log n) time. However, we need an O(n) time complexity solution. By using a set to store the elements, we can achieve O(1) average time complexity for lookups, enabling an efficient way to find consecutive sequences.

Approach

1. Convert the array to a set: This allows for O(1) average time complexity for element lookups.
2. Iterate through the array: For each number in the array: - Check if it is the start of a sequence by ensuring that the number just before it (num - 1) is not in the set. - If it is the start of a sequence, use a while loop to count the length of the sequence by incrementing the current number and checking if the incremented number is in the set. - Keep track of the maximum sequence length found.
3. Return the maximum sequence length: After iterating through all the numbers, return the length of the longest sequence found.

Complexity

Time Complexity:

O(n), where n is the number of elements in the array. Each element is inserted into the set and looked up a constant number of times.

Space Complexity:

O(n), where n is the number of elements in the array. In the worst case, all elements are unique and stored in the set.

Code

C++

class Solution {
public:
    int longestConsecutive(vector& nums) {
        unordered_set numsSet(nums.begin(), nums.end());
        int longestSequence = 0;
        for (const int& num : nums) {
            if (numsSet.find(num - 1) == numsSet.end()) {
                int currentLength = 0;
                while (numsSet.find(num + currentLength) != numsSet.end()) {
                    currentLength++;
                }
                longestSequence = max(longestSequence, currentLength);
            }
        }
        return longestSequence;
    }
};

Python

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numsSet = set(nums)
        longestSequence = 0
        for num in nums:
            if num - 1 not in numsSet:
                currentLength = 1
                while num + currentLength in numsSet:
                    currentLength += 1
                longestSequence = max(longestSequence, currentLength)
        return longestSequence

Java

class Solution {
    public int longestConsecutive(int[] nums) {
        Set numsSet = new HashSet<>();
        for (int num : nums) {
            numsSet.add(num);
        }
        int longestSequence = 0;
        for (int num : nums) {
            if (!numsSet.contains(num - 1)) {
                int currentLength = 1;
                while (numsSet.contains(num + currentLength)) {
                    currentLength++;
                }
                longestSequence = Math.max(longestSequence, currentLength);
            }
        }
        return longestSequence;
    }
}

JavaScript

var longestConsecutive = function (nums) {
    const numsSet = new Set([...nums]);
    let longestSequence = 0;
    for (const num of nums) {
        if (!numsSet.has(num - 1)) {
            let currentLength = 0;
            while (numsSet.has(num + currentLength)) {
                currentLength++;
            }
            longestSequence = Math.max(longestSequence, currentLength)
        }
    }
    return longestSequence;
};