128. Longest Consecutive Sequence

Description

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

Your algorithm should run in O(n) complexity.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

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.

Solutions

Solution 1

/**
 * Time complexity : O(NlogN)
 * Space complexity : O(N)
 */

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        Arrays.sort(nums);

        int longestStreak = 1;
        int currentStreak = 1;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i-1]) {
                if (nums[i] == nums[i-1]+1) {
                    currentStreak++;
                } else {
                    longestStreak = Math.max(longestStreak, currentStreak);
                    currentStreak = 1;
                }
            }
        }

        return Math.max(longestStreak, currentStreak);
    }
}

Solution 2

/**
 * Time complexity : O(N)
 * Space complexity : O(N)
 */

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

Follow up