Problem Statement: You are given an array of ‘N’ integers. You need to find the length of the longest sequence which contains the consecutive elements.

Examples:

Example 1:

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

Output: 4

Explanation: The longest consecutive subsequence is 1, 2, 3, and 4.

Input: [3, 8, 5, 7, 6]

Output: 4

Explanation: The longest consecutive subsequence is 5, 6, 7, and 8.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: (Brute force)

Approach: We can simply sort the array and run a for loop to find the longest consecutive sequence.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int longestConsecutive(vector<int> nums) {
        if(nums.size() == 0 ){
            return 0;
        }
        
        sort(nums.begin(),nums.end());
        
        int ans = 1;
        int prev = nums[0];
        int cur = 1;
        
        for(int i = 1;i < nums.size();i++){
            if(nums[i] == prev+1){
                cur++;
            }
            else if(nums[i] != prev){
                cur = 1;
            }
            prev = nums[i];
            ans = max(ans, cur);
        }
        return ans;
    }
    int main()
    {
        vector<int> arr{100,200,1,2,3,4};
        int lon=longestConsecutive(arr);
        cout<<"The longest consecutive sequence is "<<lon<<endl;
        
    }

Output:

The longest consecutive sequence is 4

Time Complexity: We are first sorting the array which will take O(N * log(N)) time and then we are running a for loop which will take O(N) time. Hence, the overall time complexity will be O(N * log(N)).
Space Complexity: The space complexity for the above approach is O(1) because we are not using any auxiliary space

Java Code

import java.util.*;
class TUF{
public static int longestConsecutive(int[] nums) {
        if(nums.length == 0 || nums == null){
            return 0;
        }
        
        Arrays.sort(nums);
        
        int ans = 1;
        int prev = nums[0];
        int cur = 1;
        
        for(int i = 1;i < nums.length;i++){
            if(nums[i] == prev+1){
                cur++;
            }
            else if(nums[i] != prev){
                cur = 1;
            }
            prev = nums[i];
            ans = Math.max(ans, cur);
        }
        return ans;
    }
    public static void main(String args[])
    {
        int arr[]={100,200,1,2,3,4};
        int lon=longestConsecutive(arr);
        System.out.println("The longest consecutive sequence is "+lon);
        
    }
}

Output:

The longest consecutive sequence is 4

Python Code

from typing import List

def longestConsecutive(nums: List[int]) -> int:
    if not nums:
        return 0
    nums.sort()
    ans = 1
    prev = nums[0]
    cur = 1
    for i in range(1, len(nums)):
        if nums[i] == prev + 1:
            cur += 1
        elif nums[i] != prev:
            cur = 1
        prev = nums[i]
        ans = max(ans, cur)
    return ans


if __name__ == "__main__":
    arr = [100, 200, 1, 2, 3, 4]
    lon = longestConsecutive(arr)
    print("The longest consecutive sequence is", lon)

Output:

The longest consecutive sequence is 4

Solution 2: (Optimal Approach)

Approach: We will first push all elements in the HashSet. Then we will run a for loop and check for any number(x) if it is the starting number of the consecutive sequence by checking if the HashSet contains (x-1) or not. If ‘x’ is the starting number of the consecutive sequence we will keep searching for the numbers y = x+1, x+2, x+3, ….. And stop at the first ‘y’ which is not present in the HashSet. Using this we can calculate the length of the longest consecutive subsequence.

Code:

C++ Code

#include<bits/stdc++.h>

using namespace std;
int longestConsecutive(vector < int > & nums) {
  set < int > hashSet;
  for (int num: nums) {
    hashSet.insert(num);
  }

  int longestStreak = 0;

  for (int num: nums) {
    if (!hashSet.count(num - 1)) {
      int currentNum = num;
      int currentStreak = 1;

      while (hashSet.count(currentNum + 1)) {
        currentNum += 1;
        currentStreak += 1;
      }

      longestStreak = max(longestStreak, currentStreak);
    }
  }

  return longestStreak;
}
int main() {
  vector<int> arr{100,200,1,2,3,4};
  int lon = longestConsecutive(arr);
  cout << "The longest consecutive sequence is " << lon << endl;

}

Output:

The longest consecutive sequence is 4

Time Complexity: The time complexity of the above approach is O(N) because we traverse each consecutive subsequence only once. (assuming HashSet takes O(1) to search)
Space Complexity: The space complexity of the above approach is O(N) because we are maintaining a HashSet.

Java Code

import java.util.*;
class TUF {
    public static int longestConsecutive(int[] nums) {
        Set < Integer > hashSet = new HashSet < Integer > ();
        for (int num: nums) {
            hashSet.add(num);
        }

        int longestStreak = 0;

        for (int num: nums) {
            if (!hashSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (hashSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
    public static void main(String args[]) {
        int arr[]={100,200,1,2,3,4};
        int lon = longestConsecutive(arr);
        System.out.println("The longest consecutive sequence is " + lon);

    }
}

Output:

The longest consecutive sequence is 4

Time Complexity: The time complexity of the above approach is O(N) because we traverse each consecutive subsequence only once. (assuming hashset takes O(1) to search)
Space Complexity: The space complexity of the above approach is O(N) because we are maintaining a HashSet.

Python Code

from typing import List

def longestConsecutive(nums: List[int]) -> int:
    hashSet = set()
    for num in nums:
        hashSet.add(num)
    longestStreak = 0
    for num in nums:
        if (num - 1) not in hashSet:
            currentNum = num
            currentStreak = 1
            while (currentNum + 1) in hashSet:
                currentNum += 1
                currentStreak += 1
            longestStreak = max(longestStreak, currentStreak)
    return longestStreak


if __name__ == "__main__":
    arr = [100, 200, 1, 2, 3, 4]
    lon = longestConsecutive(arr)
    print("The longest consecutive sequence is", lon)

Output:

The longest consecutive sequence is 4

Special thanks to Nishant Rana and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article