128. Longest Consecutive Sequence

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

Table of Content

• Reference
• Problem Statement
• Approach
• Code
• Complexity

Reference: 128. Longest Consecutive Sequence

Problem statement

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

Approach

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.

Code

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;
};

Complexity

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).