Data Structures & Algorithms (HashMap): Longest Consecutive Subsequence

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

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.

Playground: Leetcode 128

General Observations

Q. What will be the output if nums contain duplicate numbers (e.g., nums = [1, 0, 1, 2])?
A. Only count unique consecutive progression.

Sorting Approach (Brute Force)

Sort nums in ascending order, iterate through it to find all consecutive subarrays and keep track of the length of the longest subarray found.

Algorithm

public int longestConsecutive(int[] nums) {

    // Edge Case: If nums is empty
    if (nums.length == 0) {
        return 0;
    }

    // Step 1: Sort the array
    Arrays.sort(nums);

    // Step 2: Explore all consecutive subarrays
    int maxLength = 1;
    int currLength = 1;
    
    for(int i = 1; i < nums.length; i++) {
        // Case 1: Duplicate → skip
        if (nums[i] == nums[i-1]) {
            continue;
        }

        // Case 2: Consecutive
        if (nums[i] == nums[i-1] + 1) {
            currLength++;
            maxLength = Math.max(maxLength, currLength);
        } 
        // Case 3: Break in sequence
        else {
            currLength = 1;
        }
    }

    return maxLength;

}

Visualization

Time Complexity

Sorting takes O(n * log n) and the scan pass takes O(n), so overall complexity is dominated by sorting: O(n * log n).

Space Complexity

If sorting in place, extra space is O(1) (ignoring sort implementation details). If the language runtime uses extra stack/temporary memory for sorting, practical space can be higher.

Set-Based Approach

We can store all the unique elements in the set and, for each element, try to build a consecutive sequence starting from it by checking the next elements.

Algorithm

public int longestConsecutive(int[] nums) { 

    // Edge Case: If nums is empty
    if (nums.length == 0) {
        return 0;
    }

    // Step 1: Populate set with all unique elements
    Set<Integer> set = new HashSet<>();
    for(int num: nums) {
        set.add(num);
    }

    // Step 2: Explore consecutive subsequences starting from each element
    int maxLength = 1;

    for(int num: set) {
        int currLength = 1;
        int current = num;

        while (set.contains(current + 1)) {
            currLength++;
            current++;
        }

        maxLength = Math.max(maxLength, currLength);
    }

    return maxLength;

}

Visualization

Time Complexity

In the worst-case scenario, i.e., when nums of size n contains n consecutive unique elements, for every element num, the inner subsequence exploration loop runs proportional to how many larger consecutive elements exist after it.

Total operations performed = (n-1) + (n-2) + (n-3) + ... + 0 = n(n-1)/2 = (n² - n)/2. Ignoring the constants and lower-order terms, the overall time complexity simplifies to O(n²).

Space Complexity

In the worst case, we store all n elements in the set, since all elements in nums would be unique. Hence, overall space complexity = O(n).

Key Observation

Every element in nums can either be start of a new consecutive subsequence or part of an existing one.

Exploring a subsequence starting from an element that is already part of an existing subsequence is redundant, since it will always produce a shorter sequence.

Optimized Set-Based Approach

Instead of exploring subsequences starting from every number in nums, we only start building a sequence if the current element marks the beginning of a sequence, i.e., if (nums-1) does not exist.

NOTE: Iterate over the set instead of nums to avoid processing duplicate elements multiple times.

Algorithm

public int longestConsecutive(int[] nums) {

    // Edge Case: If nums is empty
    if (nums.length == 0) {
        return 0;
    }

    // Step 1: Populate set with all unique elements
    Set<Integer> set = new HashSet<>();
    for(int num: nums) {
        set.add(num);
    }

    // Step 2: Explore non-overlapping consecutive subsequences
    int maxLength = 0;
    for(int num: set) {
        // Start only if it's the beginning of a sequence
        if (!set.contains(num-1)) {

            int currLength = 1;
            int current = num;

            while (set.contains(current+1)) {
                currLength++;
                current++;
            }
            maxLength = Math.max(maxLength, currLength);
        }     
    }

    return maxLength;

}

Visualization

Time Complexity

Each element would be visited twice.

Each element is processed at most twice: once when inserting it into the set, and once during sequence expansion. Hence, the overall time complexity = O(n).

Space Complexity

In the worst case, we store all n elements in the set. Hence, overall space complexity = O(n).