Program

import java.util.HashSet;

public class LongestConsecutiveSequence {
    /**
     * Finds the length of the longest consecutive elements sequence.
     * 
     * @param nums an array of integers
     * @return the length of the longest consecutive sequence
     */
    public static int longestConsecutive(int[] nums) {
        HashSet numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int longestStreak = 0;

        for (int num : numSet) {
            // Only check for the start of a sequence
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                // Count the streak
                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};
        int result = longestConsecutive(nums);
        System.out.println("The length of the longest consecutive sequence is: " + result);
    }
}
    

Explanation of the Program Structure

The program consists of a single class named LongestConsecutiveSequence, which includes:

• longestConsecutive(int[] nums): A method that takes an array of integers as input and returns the length of the longest consecutive sequence.
• main(String[] args): The main method that initializes an example array and calls the longestConsecutive method, printing the result.

Documentation

The longestConsecutive method works as follows:

1. It uses a HashSet to store all unique elements from the input array. This allows for O(1) average time complexity for lookups.
2. For each number in the set, it checks if it is the beginning of a sequence by verifying that the previous number does not exist in the set.
3. If it is the start of a sequence, it counts how many consecutive numbers follow and updates the longest streak found.

This approach ensures that each number is processed only once, leading to an efficient overall time complexity of O(n), where n is the number of elements in the array.