Given an unsorted integer array arr consisting of n integers, write a program to find the length of the longest consecutive sequence of integers in the array.

Problem Note

• The longest consecutive sequence is a consecutive sequence of integers(like [1, 2, 3, 4], [66, 67, 68], etc.), which is longest in that array.
• The consecutive numbers can be in any order.
• The time complexity of finding the length of the longest consecutive sequence should be O(n).

Example 1

Input: arr[] = [1, 9, 3, 10, 4, 20, 2]
Output: 4
Explanation: The longest consecutive sequence in the above input array is [1, 2, 3, 4]. Hence, its length is 4.

Example 2

Input: arr[] = [20, 28, 12, 18, 23, 19]
Output: 3
Explanation: The longest consecutive sequence in the above input array is [18, 19, 20]. Hence, its length is 3.