Customer Support: email@example.com
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
- If you are a student, email to firstname.lastname@example.org to get special student discount.
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.
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.
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
Please be sure to take a serious look at all the problems discussed in Union Find Problems to become from good to GREAT in solving problems using Union-Find .
The above content is written by:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn