Longest Consecutive Sequence (With C++ and Java Solutions)

There are a lot of algorithms available to solve the problems with an efficient solution. Learning some such algorithms and practicing some quality problems may help one to increase problem-solving skills and crack many technical interviews with ease. In this article let us look into a medium-level array problem Longest Consecutive sequence with a solution.

Problem statement

We are given an unsorted array of integers, we have to find the longest consecutive sequence in the array.

Sample input:

[10,4,20,1,3,2]

Sample output:

4

Algorithm

1. First, sort the array using any one of the in-place sorting algorithms.
2. Then declare two variables to track the current length and maximum length of consecutive numbers found in the array.
3. If the length of the array is zero then return zero as the output
4. Else, iterate through the array and check whether the next element to the current element is consecutive and increment the current value.
5. If the next element is not consecutive to the current element then stop the iteration.
6. Compare and check the current and longest, and store the maximum value in the longest.
7. Repeat the steps till the length of the array.
8. The final value in the longest variable is the result.

Example of Longest Consecutive Sequence

To understand the working of our approach better, let us take an example and look into the step-by-step execution.

In the first step, the input is sorted in increasing order.

Then at each step, the current element is checked with the next element to verify whether it is a consecutive number. Then the current and longest variables are incremented. Finally, the maximum length is returned as output. Refer to the below image for a better and clear understanding of the steps.

Implementation of Longest Consecutive Sequence in Java

import java.util.*;
public class Solution
{
public static int longestConsecutive(int[] nums) {
  if (nums.length == 0) return 0;
  Arrays.sort(nums);
  int longSequence = 1;
  int currentSequence = 1;
  for (int i = 1; i < nums.length; i++) {
    if (nums[i] != nums[i-1]) {
      if (nums[i] == nums[i-1]+1) {
        currentSequence += 1;
      }
      else {
        longSequence = Math.max(longSequence, currentSequence);
        currentSequence = 1;
      }
    }
  }
  return Math.max(longSequence, currentSequence);
}
public static void main(String[] args) {
  int nums[]={10,4,20,1,3,2};
  System.out.println(longestConsecutive(nums));
}
}

Output

4

Implementation of Longest Consecutive Sequence in C++

#include <bits/stdc++.h>
using namespace std;
 

int findLongestConseqSubseq(int arr[], int n) {
    unordered_set<int> S;
    int ans = 0;
    for (int i = 0; i < n; i++)
        S.insert(arr[i]);
    // check each possible sequence from the start then update optimal length
    for (int i = 0; i < n; i++) {
        // if current element is the starting element of a sequence
        if (S.find(arr[i] - 1) == S.end()) {
            // Then check for next elements
            int j = arr[i];
            while (S.find(j) != S.end())
                j++;
            // update length if new length is more
            ans = max(ans, j - arr[i]);
        }
    }
    return ans;
}
 
int main() {
    int n = 7;
    int arr[] = { 10,4,20,1,3,2 };
    cout << "Length of the Longest contiguous subsequence is :"
         << findLongestConseqSubseq(arr, n);
    return 0;
}

Output

4

Time complexity

The execution time varies according to the input values has to be analyzed for the solution we build to check the efficiency of the approach. For our solution, the respective time complexity will be O(nlogn). Since the sorting algorithm takes the logarithmic time complexity and we are iterating through a single loop.

Space complexity

The extra space required to execute the program is the space complexity of the program. In our case, we are using the in-place sorting algorithm for arranging the elements and no new array is used so the space complexity will be O(1). That is constant space complexity which remains constant irrespective of the input size.

Conclusion

In this article, we have solved a medium-level problem related to arrays. This problem can also be solved with data structure concepts like a heap. We have covered C++ and java codes but if you want to learn how to find the longest consecutive sequence in python our online python tutors are available 24/7 to assist you.