Longest Consecutive Sequence in an Array

Longest Consecutive Sequence – Medium Level

Given an array of integers nums, return the length of the longest consecutive sequence of elements.

A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element.

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

Valid Sudoku to check

Constraints:

  • 0 <= nums.length <= 1000
  • -10^9 <= nums[i] <= 10^9

Check Sudoku board configuration is valid or not Solution

Recommendation for Time and Space Complexity – You should aim for a solution as good or better than O(n) time and O(n) space, where n is the size of the input array.

Hints for solving problems

Hint 1 :

A brute force solution would be to consider every element from the array as the start of the sequence and count the length of the sequence formed with that starting element. This would be an O(n^2) solution. Can you think of a better way?

Hint 2 :

Is there any way to identify the start of a sequence? For example, in [1, 2, 3, 10, 11, 12], only 1 and 10 are the beginning of a sequence. Instead of trying to form a sequence for every number, we should only consider numbers like 1 and 10.

Hint 3 :

We can consider a number num as the start of a sequence if and only if num – 1 does not exist in the given array. We iterate through the array and only start building the sequence if it is the start of a sequence. This avoids repeated work. We can use a hash set for O(1) lookups by converting the array to a hash set.

There are mainly 4 approach to solve this problem-

  1. Brute Force Method
  2. Sorting Method
  3. Hash Set Method
  4. Hash Map Method

1. Brute Force Method

This method check every possible sequence starting from each element in the array to find the longest consecutive sequence.

  • Time complexity: O(n^2)
  • Space complexity: O(n)

Code

2. Sorting Method

This method sort the array, then iterate through it to find the length of the longest consecutive sequence.

  • Time complexity: O(n logn)
  • Space complexity: O(1)

Code

3. Hash Set Method

This method store all elements in a hash set for O(1) lookups, then iterate through the array and start counting the length of a sequence only when the current number is the start of a sequence (no smaller number exists).

  • Time complexity: O(n)
  • Space complexity: O(n)

Code

4. Hash Map Method

This method use a hash map to dynamically update the lengths of consecutive sequences while iterating through the array, achieving O(n) time complexity.

  • Time complexity: O(n)
  • Space complexity: O(n)

Code

More Articles