Longest Consecutive Sequence
Application of Union Find / Disjoint Set Union Data Structure
-
Algorithms and Data Structures: TheAlgorist.com
-
System Design: DistributedComputing.dev
-
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 Union-Find Series, so please be sure to go through each and every chapter in the series in order to have a solid understand of Union-Find and become really good at solving problems using Union-Find.
Please have a very good understanding of Union-Find 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 Union-Find based solution for even a complex problem when you are familiar with the implementation of Union-Find data structure discussed in the Template section of Union-Find 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 . Inverse-Ackermann(N)) = O(N), since O(Inverse-Ackermann(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
Union-Find .
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
