LeetCode Problems

In this tutorial we will solve 128. Longest Consecutive Sequence from leetcode.

Reference: 128. Longest Consecutive Sequence

In this problem we have an unsorted input array of integers `nums`

. We are asked to return the length of the longest consecutive elements.

We must solve this in **O(n)** time complexity.

Example from leetcode.

```
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
```

```
Constraints:
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
```

To solve this problem we will use a set. This way we will get rid of duplicates. We will traverse through the input array and for each element we will check if it is the start of the sequence. If there is no element before the current element of the array then it marks the start of a sequence. Once we get an element that marks the start of a sequence, we would check all the elements to its right. This will help in getting the number of elements in the sequence.

Let's solve the input nums = [100,4,200,1,3,2].

```
longestSequenceLength = 0
set = {100, 4, 200, 1, 3, 2}
nums = [100, 4, 200, 1, 3, 2]
^
is (100-1) i.e. 99 in the set? no
-> this marks the start of a sequence
-> currentSequenceLength = 1
-> is (100+1) in the set? no
-> sequence ends
-> longestSequenceLength = max(longestSequenceLength, currentSequenceLength) = 1
longestSequenceLength = 1
nums = [100, 4, 200, 1, 3, 2]
^
is (4-1) i.e. 3 in the set? yes
-> this is not the start of the sequence
longestSequenceLength = 1
nums = [100, 4, 200, 1, 3, 2]
^
is (200-1) i.e. 199 in the set? no
-> this marks the start of a sequence
-> currentSequenceLength = 1
-> is (200+1) in the set? no
-> sequence ends
-> longestSequenceLength = max(longestSequenceLength, currentSequenceLength) = 1
longestSequenceLength = 1
nums = [100, 4, 200, 1, 3, 2]
^
is (1-1) i.e. 0 in the set? no
-> this marks the start of a sequence
-> currentSequenceLength = 1
-> is (1+1) i.e. 2 in the set? yes
-> currentSequenceLength = 2
-> is (2+1) i.e. 3 in the set? yes
-> currentSequenceLength = 3
-> is (3+1) i.e. 4 in the set? yes
-> currentSequenceLength = 4
-> is (4+1) i.e. 5 in the set? no
-> sequence ends
-> longestSequenceLength = max(longestSequenceLength, currentSequenceLength)
= max(1, 4)
= 4
longestSequenceLength = 4
nums = [100, 4, 200, 1, 3, 2]
^
is (3-1) i.e. 2 in the set? yes
-> this is not the start of the sequence
longestSequenceLength = 4
nums = [100, 4, 200, 1, 3, 2]
^
is (2-1) i.e. 1 in the set? yes
-> this is not the start of the sequence
```

So, the longest consecutive sequence is of length 4.

JavaScript

```
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function(nums) {
let set = new Set(nums);
let longest = 0;
let length = 0;
for(let n of nums) {
if (!set.has(n-1)) {
length = 0;
while(set.has(n+length)) {
length++;
}
longest = Math.max(longest, length);
}
}
return longest;
};
```

**Time complexity: O(n)**

Creating a set of n elements would take O(n) time. Then we have to loop through the n elements using the for loop which is O(n) time. The inner while loop checks element in the set if they are part of a sequence. In worst case, this while loop could run for the entire length of the sequence. However, the while loop in total runs for n times across all the iteration of the for loop. So, overall time complexity is O(n).

**Space complexity: O(n)**

We are creating a set of size n using the input array. Therefore, space complexity is O(n).

ADVERTISEMENT