Leetcode problem 128: Longest Consecutive Sequence

In this article, you will find a solution to Leetcode problem #128. The article covers all aspects of the problem, including the problem statement, the algorithm used, code implementation, and analysis of time and space complexity.

problem statement :

Given an unsorted array of integers nums, return the length of the longest consecutive (Continue) elements sequence.

You must write an algorithm that runs in O(n) time.

Example:

nums: [100, 4, 200, 1, 3, 2]

Intuition :

(When we see the question the first logic can our brain build is first to sort the list and find our solution easily which is the consecutive sequence But in this approach is O(nlogn) rather we find the solution is O(n) time)

Logic :

We check if our current integers have a lesser number which means the current is not our starting point. But if the lesser is not it means our current is starting and then we find its next element

Explanination :

In this solution, we use Set to get a unique number.

In the first iteration, we have no less number which means our current is starting number and then we find its next element but it has no next element and its length is one. In 2nd iteration, we also find the less number and we find the less which means it is not our starting number. In the third iteration, we can`t the less number and it is our starting number. then we find its next element and its length is 4. In the fourth iteration, we also can`t find the less number and which means it is not our starting number. In the fifth iteration also can`t find the lesser number. In the end, we return the consecutive sequence

This will output 4, which is the length of the longest consecutive sequence in the given array (1, 2, 3, 4).

Time & space Complexity :

Both are O(n)