Longest Consecutive Sequence

121.Longest Consecutive Sequence

Hash Table

Problem Statement:

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

• The sequence must be strictly consecutive.
• The algorithm should run in O(n) time.

Algorithm:

1. Create a hash set containing all the elements of nums.
2. Iterate through the set:
   • If the current number is the start of a sequence (i.e., num - 1 is not in the set), calculate the length of the sequence.
   • Use a while loop to count consecutive numbers, starting from the current number and moving upwards.
   • Update the maximum sequence length if the current sequence is longer.
3. Return the maximum sequence length.

Complexity:

Time: O(n), where n is the number of elements in the input array | Space: O(n) for the hash set.

Java Implementation:

class Solution {
    public int longestConsecutive(int[] nums) {
        Set set = new HashSet<>();
        int max = 0;

        // Add all elements to the set
        for (int num : nums) 
            set.add(num);

        // Iterate through the set
        for (int num : set) {
            // Ensure starting at the lowest number of a sequence
            if (set.contains(num - 1)) 
                continue;

            int count = 1;
            int i = num;

            // Count consecutive numbers
            while (set.contains(++i)) 
                count++;

            // Update the maximum sequence length
            max = Math.max(count, max);
        }
        return max;
    }
}
                

Python Implementation:

def longestConsecutive(nums):
    num_set = set(nums)
    max_length = 0

    for num in num_set:
        # Check if the number is the start of a sequence
        if num - 1 not in num_set:
            current_num = num
            current_streak = 1

            # Count consecutive numbers
            while current_num + 1 in num_set:
                current_num += 1
                current_streak += 1

            # Update the maximum sequence length
            max_length = max(max_length, current_streak)

    return max_length
                

C++ Implementation:

#include 
#include 
using namespace std;

class Solution {
public:
    int longestConsecutive(vector& nums) {
        unordered_set numSet(nums.begin(), nums.end());
        int maxLength = 0;

        for (int num : numSet) {
            // Check if the number is the start of a sequence
            if (numSet.find(num - 1) == numSet.end()) {
                int currentNum = num;
                int currentStreak = 1;

                // Count consecutive numbers
                while (numSet.find(currentNum + 1) != numSet.end()) {
                    currentNum++;
                    currentStreak++;
                }

                // Update the maximum sequence length
                maxLength = max(maxLength, currentStreak);
            }
        }
        return maxLength;
    }
};