# Find the longest consecutive sequence in O(n) complexity

Hey Geeks, I’m so glad to see you here. I was surfing the internet and found this problem. Finding the longest consecutive sequence in O(n) complexity is hard.

Contents

I thought, let’s give it a try, cause why not? I did this code as much as I understood. Even I don’t know how to calculate the exact complexity of this code. Oh no! I told you something kept secret. Shit! But if you find any bug or if you have a better idea to solve this, let me know. Yeah? yeah.

Anyway, enough of talking, let’s dig in.

## Problem Statement

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example, given `[100, 4, 200, 1, 3, 2]`, the longest consecutive element sequence is `[1, 2, 3, 4]`. Return its length: 4.
Your algorithm should run in `O(n)` complexity.

## Solution

```/*
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package code1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
*
* @author Shankha
*/
public class LongestConsecutiveElementsSequence {

public static void main(String[] args) {
//        int[] array2 = {};                                    // Expected 0
//        int[] array2 = {0};                                   // Expected 0
//        int[] array2 = {0, 0};                                // Expected 1
//        int[] array2 = {0,-1};                                // Expected 2
//        int[] array2 = {1, 2, 0, 1};                          // Expected 3
//        int[] array2= {100,4,200,1,3,2};                      // Expected 4
int[] array2 = {9, 1, 4, 7, 3, -1, 0, 5, 8, -1, 6};     // Expected 7

System.out.println(longestConsecutive(array2));
}

public static int longestConsecutive(int[] nums) {

Integer[] array = Arrays.stream(nums).boxed().toArray(Integer[]::new);

if (array.length == 0) {
return 0;
} else if (array.length == 1) {
return 1;
}

List<Integer> list = new ArrayList<>();

Collections.sort(list);

int maxSeqCnt = 0;
int tempCnt = 0;
for (int i = 0; i < list.size() - 1; i++) {
if (list.get(i) == list.get(i + 1)) {
continue;
}
if (list.get(i) + 1 == list.get(i + 1)) {
tempCnt++;
maxSeqCnt = (maxSeqCnt > tempCnt) ? maxSeqCnt : tempCnt;
} else {
tempCnt = 0;
}
}

return maxSeqCnt + 1;

}
}
```