Longest Consecutive Sequence

Question: Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

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

You may view the full question here.

Approach 1: Let’s sort of con the system, shall we? Well, I have just used a the java provided sort function and amped up the performance by leaps and bounds…

//Approach 1:
//Runtime: 3ms
//Memory usage: 36.3MB
class Solution {
    public int longestConsecutive(int[] nums) {
        Arrays.sort(nums);
        int count = 1;
        int max = 1;
        for(int i = 1; i<nums.length; i++){
            if(nums[i-1]==nums[i]){
                //Do nothing
            }else if(nums[i-1]+1==nums[i]){
                count++;
            } else {
                count = 1;
            }
            
            max = Math.max(count, max);
        }
        return Math.min(nums.length, max);
    }
}

Find more posts here.

Cheers & Chao!