Longest Consecutive Sequence medium

Problem Statement

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

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

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

Steps:

1. Create a HashSet: Insert all numbers from the input array into a HashSet. This allows for O(1) lookup time.

2. Iterate through the array: For each number num in the input array:

3. Check for the start of a sequence: Check if num - 1 exists in the HashSet. If it doesn't, it means num is the start of a potential consecutive sequence.

4. Extend the sequence: If num is the start of a sequence, iterate upwards (num + 1, num + 2, etc.) as long as the next number exists in the HashSet. Count the length of this sequence.

5. Update the maximum length: Keep track of the maximum length encountered so far.

6. Return the maximum length: After iterating through all numbers, return the maximum length of a consecutive sequence found.

Explanation:

The HashSet is crucial for achieving O(n) time complexity. By using a HashSet, we can efficiently check if a number is present in the set in constant time. The algorithm avoids redundant checks by only starting a sequence length calculation when it finds a number that is not preceded by a consecutive number. This ensures that each number is considered only once in the process of finding the longest sequence.

Code:

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

class Solution {
    public 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)) { // Potential start of a sequence
                int currentNum = num;
                int currentStreak = 1;

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

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

        return longestStreak;
    }
}

Complexity:

• Time Complexity: O(n). The HashSet operations (insertion and lookup) take constant time on average. We iterate through the array once. The inner while loop iterates only through the elements of a sequence, and each element is part of only one sequence. Therefore, the total number of iterations of the inner loop is proportional to n.

• Space Complexity: O(n). In the worst case, the HashSet can store all the numbers from the input array.