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.