Find the longest sequence of consecutive numbers - Leetcode Solution

Companies:

LeetCode: Find the longest sequence of consecutive numbers Leetcode Solution

Difficulty: Unknown

Given an unsorted array with only distinct elements, find the length of the longest sequence of consecutive numbers in the array.

Example Test Cases

Sample Test Case 1

Array: 0, 7, 2, 1, 6, 5, 3
Expected Output: 4
Explanation: There are only two possible subsequences with consecutive elements [5, 6, 7 ] and [0, 1, 2, 3] . The 2nd one has larger length 4.

Sample Test Case 2

Array: 2, 4, 6, 8, -1
Expected Output: 1
Explanation: Each element can be considered a consecutive element sequence of length 1.

Solution

The core idea is that each number in the array, can either be start of some consecutive sequence or it can be a part of some already existing sequence.

If it is a start of some sequence, we will simulate the whole process of counting all the numbers. for example, if the number which is start of sequence is 5 then we will check for the existence of 6 then 7 and so on.

If it is not a part of some sequence, then we will ignore the number.

We can implement the above solution by maintaining a Hash table corresponding to all the distinct elements in the array. We will first insert all the numbers into the hash table and then if any corresponding number can be a starting number for a new consecutive sequence, we will compute the length of that sequence.

See the code below for implementation

Time Complexity

Since each element will be counted at most two times as a part of either outer loop or inner while loop, the total complexity of the solution would be O(n)

Similar Problems