Longest Consecutive Sequence - Java Solution

1. Introduction

This blog post examines a common problem in array manipulation and hashing, known as the "Longest Consecutive Sequence" problem. The challenge is to identify the length of the longest consecutive elements sequence in an unsorted array of integers. The key is to develop an algorithm that accomplishes this in linear time, O(n).

Problem

Given an unsorted array of integers nums, the objective is to return the length of the longest sequence of consecutive elements. The sequence must consist of numbers that appear in the array, and their order in the array is irrelevant.

Examples:

1. Input: nums = [100, 4, 200, 1, 3, 2]

Output: 4

Explanation: The longest consecutive sequence is [1, 2, 3, 4], and its length is 4.

2. Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]

Output: 9

2. Solution Steps

1. Create a hash set and add all elements of the array to it. This allows for constant time checks for the presence of elements.

2. Iterate through the array and for each element, check if it is the start of a sequence (i.e., check if the element just before it does not exist in the set).

3. If it is the start, then count the length of the consecutive sequence following it.

4. Keep track of the maximum length of all such consecutive sequences.

5. Return the maximum length found.

3. Code Program

import java.util.HashSet;
import java.util.Set;

public class LongestConsecutiveSequence {
    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println(longestConsecutive(nums)); // Test the function
    }

    // Function to find the length of the longest consecutive elements sequence
    public static int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int longestStreak = 0;
        for (int num : nums) {
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (numSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        return longestStreak;
    }
}

Output:

4

Explanation:

1. longestConsecutive: This function computes the length of the longest consecutive elements sequence in an array nums.

2. It first creates a hash set numSet to store the elements of nums, allowing O(1) time complexity for checking the existence of an element.

3. The function then iterates through the array. For each element, it checks if it's the start of a new sequence (i.e., the previous number is not in the set).

4. If it is the start, the function counts the length of the sequence by continuously checking for the next consecutive number in the set.

5. It updates longestStreak if the current sequence is longer than the previously recorded sequences.

6. The use of a hash set for direct access and the check for sequence starts ensure that the function runs in O(n) time, making it an efficient solution.