Solution: Longest Consecutive Sequence

Let's solve the Longest Consecutive Sequence problem using the Union Find pattern.

We'll cover the following

Statement

Given an unsorted array, nums, your task is to return the length of the longest consecutive sequence of elements. The consecutive sequence of elements is such that there are no missing elements in the sequence. The consecutive elements can be present anywhere in the input array.

Note: Two elements, xx and yy, are called consecutive if the difference between them is equal to 11.

Constraints:

  • 0≤0 \leq nums.lengths ≤103\leq 10^{3}
  • −106≤-10^{6} \leq nums[i] ≤106\leq 10^{6}

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

A naive approach to solve this problem would be to sort the input array and then iterate through the sorted array. For each element, we check if the next consecutive element exists in the sorted array. If it does, we keep incrementing until we reach the end of the sequence. After reaching the end of the sequence, we compare its length with the previous longest sequence found and update the result accordingly. The time complexity of this approach is O(nlog⁡n)O(n \log n), and the space complexity is O(1)O(1).

Optimized approach using union find

The consecutive sequence of elements in the given array can be considered connected components. The idea is to combine all the consecutive elements into single connected components, which makes it easier to determine the length of consecutive sequences. We can streamline this process using the Union Find pattern. We iterate through each number in the array, and for each number encountered, we check if the next consecutive number exists in the array. If it does, using the Union method, the current number is merged with the next consecutive number into the same set within the Union Find structure using the union method. We also maintain the size of each set that reflects the total number of elements within that set. Once all numbers have been processed, we return the length of the connected component with most numbers, providing the length of the longest consecutive sequence within the given array.

The algorithm works as follows:

  • Initialize a union find data structure, ds, with the given, nums, which results in the creation of data structure(s) necessary for proceeding with the algorithm. For this specific algorithm, two dictionaries, parent and size, and a variable, maxLength are created.

    • The parent dictionary is initialized such that each number in nums is its own parent initially. This means that each number is considered to be in its own sequence, and it is the root of that sequence.

    • The size dictionary is initialized with each number having a size of 11. This represents that each sequence initially contains only one element.

    • The maxLength variable is initialized to 11. This variable will keep track of the length of the longest consecutive sequence found so far.

  • Loop through each number, nums[i], in nums. For each number, nums[i], in nums, we’ll check if nums[i] + 1 is present in the parent dictionary. If it is present, we’ll apply a union method of the UnionFind class on nums[i] and nums[i] + 1 as follows:

    • Find the roots of sequences containing the given elements using the find method. If they are not equal, combine the roots of these consecutive sequences by setting the parent of the root of the smaller sequence to the root of the larger sequence.

    • Update the length of the larger sequence by adding the current sequence’s length and the smaller sequence’s length.

    • Update maxLength as shown below. This compares the current value of maxLength with the updated length of the larger sequence (xRoot) and stores the larger of the two values in maxLength.

maxLength = max(maxLength, size[xRoot])

After iterating through all the numbers in nums, return maxLength, which represents the length of the longest consecutive sequence.

Let’s take a look at the code for this solution below:

main.java
UnionFind.java
import java.util.*;
class Main {
    public static int longestConsecutiveSequence(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        
        UnionFind ds = new UnionFind(nums);
        for (int num : nums) {
            if (ds.parent.containsKey(num + 1)) {
                ds.union(num, num + 1);
            }
        }
        return ds.maxLength;
    }
    // driver code
    public static void main(String[] args) {
        int[][] inputNums = {
            {150, 14, 200, 1, 3, 2},
            {1, 2, 3, 4, 5, 6, 7},
            {1, 3, 5, 7},
            {7, 6, 5, 4, 3, 2, 1},
            {7, 6, 5, 1}
        };
        for (int i = 0; i < inputNums.length; i++) {
            System.out.println((i + 1) + ".\tnums = " + Arrays.toString(inputNums[i]));
            System.out.println("\tThe length of the longest consecutive sequence is: " + longestConsecutiveSequence(inputNums[i]));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Longest Consecutive Sequence

Summary

This problem involves finding the length of the longest consecutive sequence, given an unsorted array of integers. We initialize the Union Find data structure with each element in the array as a separate component using dictionaries. Then, we iterate through the array, evaluating for each element if its neighbor with a value of one greater is present in the Union Find data structure. If found, the two components are combined. Once all the elements have been processed, the size of the largest connected component is returned as the length of the longest consecutive sequence.

Time complexity

The time complexity of this solution is O(n)O(n), where nn is the number of integers in the array.

Space complexity

The space complexity of this solution is O(n)O(n) since we need to store the parent and size of each integer in the dictionaries.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.