# Longest Consecutive Sequence Solution

• Brute force Solution [Accepted]
Sort the given array into ascending or descending order. Then scan the array once to find the longest consecutive sequence. The time complexity of this solution is O(nlogn), but the space complexity is O(1).

``````public int longestConsecutive(int[] nums) {
/* Sorting : Sort the array and find the longest subarray
by counting consecutive element. It will not work for
duplicates in the array.
TC : O(nlog n)
SC : O(1)
*/

// if the array is null just return
if(nums.length == 0)
return 0;

// sort the array
Arrays.sort(nums);
int count = 1;
int res = 1;

for(int i=0; i<nums.length - 1; i++){
System.out.println(nums[i]);
if (nums[i] == nums[i+1]){
continue; // for duplicates skip the next element
}
if(i<nums.length -1){
if(nums[i]+1 == nums[i+1] ){
count++;
res = Math.max(res,count);
}
else
count = 1;
} // end of if

} // end of for loop
return res;
} // method
``````

Efficient Solution using HashSet[Accepted]
We can design a O(n) solution using O(n) space complexity by creating a HashSet.

``````public int longestConsecutive(int[] nums) {
/* Using HashSet to store the distinct elements of the given array in the set.
We do not need HashMap becuase index is of no importance.
Then seaarch for the vales after num[i], since it is the first element in the sequence.
TC : O(n)
SC : O(n)
*/

Set<Integer> lookup = new HashSet<Integer>();

for(int i =0; i<nums.length; i++)

int res =0; // stores the length of solution
for(int i =0; i<nums.length; i++){
if(!lookup.contains(nums[i]-1)){
int j = nums[i];
while(lookup.contains(j))
j++;
if(res < j-nums[i])
res = j-nums[i]; // since j is ahead of i always.
} // end of if
}// end of for
return res;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.