9. Longest Consecutive Sequence

Description

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

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

Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Constraints:

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

Approach 1

• Store the original nums in a Set
• Then iterate through it check if element-1 exist if it does not that means it is a start of a new sequence then keep checking if +1 exists adding to the count then find the max
• One way to make it even more optimized is to check if the longest sequence is greater then half of the input size because there can not be a sequence bigger than this

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
 
        Set<Integer> numbers = new HashSet<>();
        int longest = 1;
 
        for (int num: nums) {
            numbers.add(num);
        }
 
        for(int num: nums) {
            if(!numbers.contains(num-1)) {
                int count = 1;
                while(numbers.contains(num+1)) {
                    count++;
                    num++;
                }
                longest = Math.max(longest,count);
            }
 
            if(longest > nums.length/2) break;
        }
 
        return longest;
    }
}