Longest Consecutive Sequence
Application of Union Find / Disjoint Set Union Data Structure

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
Problem Statement:
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. Example 2: Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9
Note: This problem is part of UnionFind Series, so please be sure to go through each and every chapter in the series in order to have a solid understand of UnionFind and become really good at solving problems using UnionFind.
Please have a very good understanding of UnionFind Fundamentals before solving this problem. Through all the problems discussed in Problem Solving using Union Find one of my goals is to show you how easy it becomes writing an UnionFind based solution for even a complex problem when you are familiar with the implementation of UnionFind data structure discussed in the Template section of UnionFind Fundamentals chapter.
Solution:
Think of all the consecutive sequences as connected components or disjoint sets. So we find all the connected components or disjoint sets and at the end return the size of the largest connected component or disjoint set.
Union Find is a perfect data structure to solve this problem efficiently. We would get all connected components or disjoint sets by unionizing every element k present in the given array with (k  1) if it is present in the union find data structure and with (k + 1) if it is present in the union find data structure.
We need to know if (k  1) or (k + 1) is present in the union find data structure to make sure that that they are present in the given array arr[0...i] where i is the index of k.
Now you might wonder why we are searching for (k  1) and (k + 1) only in the search space arr[0...i] and not in the entire given array. This is because if (k  1) or (k + 1) are present in the given array but their index is greater than i, then as we iterate over the array and encounter them and do union operation, they would be included in their appropriate disjoint set anyways.
Overall time complexity: O(N . InverseAckermann(N)) = O(N), since O(InverseAckermann(N)) = O(1) approximately.
Space Complexity: O(N) since O(N) space needed in union find data structure.
N = total number of elements in the given array.
Notice that you could sort the given array and solve this problem too, but that would not be efficient. That would be an O(nlogn) algorithm.
Java Code:
Login to Access Content
Python Code:
Login to Access Content
Please be sure to take a serious look at all the problems discussed
in Union Find Problems
to become from good to GREAT at solving problems using
UnionFind .