Longest Consecutive Sequence

Problem Statement: Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Algorithm Explanation:

1. Use a hash set to store the elements for O(1) average time complexity lookups.

2. Iterate through the array, and for each number, check if it's the start of a sequence.

3. If it is, count the length of the sequence by continuously checking for the next consecutive numbers.

Steps:

1. Store all elements in a hash set.

2. Initialize a variable to track the longest sequence.

3. For each element in the array, check if it's the start of a sequence (i.e., num - 1 is not in the set).

4. Count the length of the sequence and update the longest sequence length if necessary.

Time and Space Complexity:

• Time Complexity: O(N), where N is the number of elements in the array.

• Space Complexity: O(N) for storing elements in a hash set.

Code Implementation:

C++

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> num_set(nums.begin(), nums.end());
    int longest_streak = 0;

    for (int num : nums) {
        if (num_set.find(num - 1) == num_set.end()) { // Check if it's the start of a sequence
            int current_num = num;
            int current_streak = 1;

            while (num_set.find(current_num + 1) != num_set.end()) {
                current_num++;
                current_streak++;
            }
            longest_streak = max(longest_streak, current_streak);
        }
    }
    return longest_streak;
}

int main() {
    vector<int> nums = {100, 4, 200, 1, 3, 2};
    cout << "Longest consecutive sequence length: " << longestConsecutive(nums) << endl;
    return 0;
}

Java

import java.util.HashSet;

public class LongestConsecutiveSequence {
    public static int longestConsecutive(int[] nums) {
        HashSet<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        int longestStreak = 0;

        for (int num : nums) {
            if (!numSet.contains(num - 1)) { // Check if it's the start of a sequence
                int currentNum = num;
                int currentStreak = 1;

                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        return longestStreak;
    }

    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println("Longest consecutive sequence length: " + longestConsecutive(nums));
    }
}

Python

def longest_consecutive(nums):
    num_set = set(nums)
    longest_streak = 0

    for num in nums:
        if num - 1 not in num_set:  # Check if it's the start of a sequence
            current_num = num
            current_streak = 1

            while current_num + 1 in num_set:
                current_num += 1
                current_streak += 1
            longest_streak = max(longest_streak, current_streak)

    return longest_streak

nums = [100, 4, 200, 1, 3, 2]
print("Longest consecutive sequence length:", longest_consecutive(nums))