Longest Consecutive Sequence

class Solution {
public:
    int longestSequence(vector<int>& nums) {
        unordered_set<int> elements(nums.begin(), nums.end());
        int maxSequenceLength = 0;
        for (int n : elements) {
            if (!elements.count(n - 1)) {
                int currentElement = n;
                int sequenceLength = 1;
                while (elements.count(currentElement + 1)) {
                    currentElement++;
                    sequenceLength++;
                }
                maxSequenceLength = max(maxSequenceLength, sequenceLength);
            }
        }
        return maxSequenceLength;
    }
};

The provided C++ code offers a solution to find the longest consecutive sequence in an array of integers. Here's an explanation of how this solution operates:

• The solution utilizes an unordered_set (elements) to hold all unique numbers from the input vector (nums), eliminating any duplicates and allowing for constant-time complexity lookups.
• The code iterates over each number (n) in the set. For each number, it checks whether its predecessor (n-1) is not in the set. This check is crucial because it helps in identifying the start of a new sequence.
• If n is identified as the start of a sequence, the code initiates two variables:
  • currentElement, starting at n
  • sequenceLength, starting at 1
• Within the nested while loop, currentElement is incremented by one each time the subsequent number (currentElement + 1) exists in the set, simultaneously incrementing sequenceLength.
• After the while loop concludes (when no consecutive number is found), the maxSequenceLength gets updated if sequenceLength from the current sequence exceeds the previously recorded maximum.
• The function finally returns maxSequenceLength, which represents the length of the longest consecutive sequence found.

This approach ensures an efficient solution with a time complexity roughly of O(n), where n is the number of elements in nums. This solution is particularly optimal when compared to a brute-force method, due to the efficient look-up capabilities offered by the unordered_set and the direct skip to potential sequence beginnings, avoiding redundant checks.

class Solution {
    public int maxConsecutiveSequence(int[] elements) {
        Set<Integer> uniqueElements = new HashSet<Integer>();
        for (int element : elements) {
            uniqueElements.add(element);
        }

        int maxStreak = 0;

        for (int element : uniqueElements) {
            if (!uniqueElements.contains(element - 1)) {
                int currentElement = element;
                int currentSequenceLength = 1;

                while (uniqueElements.contains(currentElement + 1)) {
                    currentElement += 1;
                    currentSequenceLength += 1;
                }

                maxStreak = Math.max(maxStreak, currentSequenceLength);
            }
        }

        return maxStreak;
    }
}

The problem "Longest Consecutive Sequence" involves finding the length of the longest consecutive elements' sequence in an array. This implementation is programmed in Java.

Here is a clear breakdown of the solution approach:

• First, use a HashSet to hold unique elements from the input array. This operation helps eliminate any duplicates and supports efficient order-independent lookup.
• Initialize a variable maxStreak to store the maximum sequence length found during the execution.
• Iterate through each element in the HashSet. For each element, check if its predecessor (element-1) is not in the HashSet to ensure that the sequence calculation starts only from the first consecutive element.
• For each starting element of a potential sequence, use a while loop to count how many consecutive elements exist after it by continuously checking the presence of the next consecutive element in the HashSet and updating the sequence length accordingly.
• Continuously update maxStreak with the highest sequence length encountered.
• After finishing the check for all elements, return the value of maxStreak as it represents the length of the longest sequence of consecutive numbers.

The approach essentially capitalizes on the HashSet's properties, ensuring that the time complexity is linear, O(n), due to the constant time complexity O(1) for insertions and lookups in the HashSet. This technique efficiently handles the challenge of finding consecutive sequences without needing the array to be sorted, leading to a direct, efficient solution.

// Structure for hash table used for number storage
typedef struct {
    int number;          // the integer value itself
    UT_hash_handle hash_handle;  // makes this structure suitable for hashing
} NumberHash;

// Function to insert a number into a hash set
void insert_number(NumberHash **set, int value) {
    NumberHash *item;
    HASH_FIND_INT(*set, &value, item);
    if (!item) {
        item = (NumberHash *)malloc(sizeof(NumberHash));
        item->number = value;
        HASH_ADD_INT(*set, number, item);
    }
}

// Function to verify presence of a number in the set
int contains(NumberHash *set, int value) {
    NumberHash *item;
    HASH_FIND_INT(set, &value, item);
    return item != NULL;
}

// Function to find the longest sequence of consecutive integers
int longest_sequence(int *array, int size) {
    NumberHash *hash_set = NULL;

    // Populate the hash set with array elements
    for (int i = 0; i < size; i++) {
        insert_number(&hash_set, array[i]);
    }

    int maxStreak = 0;

    // Evaluate consecutive sequences using hash set
    for (NumberHash *current = hash_set; current != NULL; current = current->hash_handle.next) {
        int number = current->number;
        // Check if it's the start of a new sequence
        if (!contains(hash_set, number - 1)) {
            int currentNumber = number;
            int currentStreak = 1;
            // Extend sequence
            while (contains(hash_set, currentNumber + 1)) {
                currentNumber++;
                currentStreak++;
            }
            // Record maximum streak length
            if (currentStreak > maxStreak) {
                maxStreak = currentStreak;
            }
        }
    }

    // Clear the hash set
    NumberHash *current_element, *temp;
    HASH_ITER(hash_handle, hash_set, current_element, temp) {
        HASH_DEL(hash_set, current_element);
        free(current_element);
    }
    return maxStreak;
}

This C program efficiently determines the length of the longest consecutive elements sequence in an integer array. It utilizes a custom hash table implementation for rapid access and manipulation of individual numbers.

The solution includes several key components:

• Data Structures: A structure, NumberHash, holds integers and integrates with the UTHash library, permitting efficient hashing operations.
• Insert Operation: insert_number function checks if a value is already in the hash set; if not, it adds the value.
• Search Operation: contains function searches for an item in the hash set to determine its presence.
• Core Logic for Finding the Sequence: The longest_sequence function first populates the hash set with array elements. Then, for each element, it checks if it is the start of a sequence (i.e., the predecessor is not in the set). If so, it counts how many consecutive numbers exist from that point, updating the longest streak found.

Here are the steps the function follows:

1. Populate a hash set with the input array’s elements.
2. Iterate through each element in the set: determine if it's the start of a new sequence and if so, check the length of this sequence.
3. Continuously track and update the length of the longest sequence found.
4. Lastly, free memory by clearing the hash set.

The approach ensures O(n) complexity in average case scenarios due to direct number lookups and minimal overhead in managing the number sequence dynamically. Additionally, by leveraging a hashing structure, the solution avoids the extensive sorting or manual boundary checking typically required in such problems. This program is practical for large datasets where efficiency is crucial.

var maxConsecutiveLength = function (numbers) {
    let numberSet = new Set(numbers);
    let maxStreak = 0;
    for (let number of numberSet) {
        if (!numberSet.has(number - 1)) {
            let currentNumber = number;
            let currentStreak = 1;
            while (numberSet.has(currentNumber + 1)) {
                currentNumber += 1;
                currentStreak += 1;
            }
            maxStreak = Math.max(maxStreak, currentStreak);
        }
    }
    return maxStreak;
};

The given problem involves finding the longest consecutive sequence present in an array of numbers using JavaScript. The provided solution employs an effective approach utilizing a Set for efficient look-ups and the main loop to expand consecutive sequences.

• Initialize a set with all numbers from the input array to facilitate unique and O(1) time complexity look-ups.
• Declares a variable maxStreak to keep track of the maximum length of consecutive numbers found.
• Iterate through each number in the set. For each number, check if its predecessor (number - 1) is not in the set, indicating the start of a new sequence.
• If it's the start of a sequence, initialize currentNumber with the starting number and currentStreak to 1.
• Use a while loop to explore subsequent numbers. If the next consecutive number (currentNumber + 1) exists in the set, update currentNumber and increment currentStreak.
• After fully exploring the current sequence, update maxStreak if currentStreak is greater.
• After completing the loop over all numbers in the set, return maxStreak, which now holds the length of the longest consecutive sequence found.

The approach is efficient, harnessing the properties of sets for quick access and avoidance of redundant checks, resulting in a streamlined solution to identify the longest consecutive sequence.

class Solution:
    def maxConsecutiveSequence(self, nums: List[int]) -> int:
        max_streak = 0
        number_set = set(nums)

        for number in number_set:
            if number - 1 not in number_set:
                current_value = number
                current_length = 1

                while current_value + 1 in number_set:
                    current_value += 1
                    current_length += 1

                max_streak = max(max_streak, current_length)

        return max_streak

The Python code provided offers an efficient solution for finding the longest consecutive sequence in a list of integers. The primary steps for achieving this are shown:

1. Convert the list of numbers to a set for O(1) time complexity checks.
2. Initialize max_streak to track the length of the longest found sequence.
3. For each number in the unique set of numbers:
   • Check if it's the start of a new sequence by confirming the absence of the previous number in the set.
   • If it's indeed the start, continuously check for consecutive numbers following the current number to determine the length of this sequence.
   • Update max_streak with the maximum value between its current value and the length of the current sequence.
4. Return the value of max_streak, representing the length of the longest consecutive sequence.

This strategy avoids unnecessary re-checks of elements, ensuring that each number is possibly part of a sequence only once. The use of a set guarantees that each membership check, crucial for determining consecutiveness, is performed in constant time, leading to an overall time complexity of O(n). This solution is not only effective but also optimized for performance.