LeetCode - Longest Consecutive Sequence

Problem description

description

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.

Analysis

Basically we can use HashMap to store the information. We can use two HashMaps to save the start val and number of consecutive sequence from that start. And another HashMap will save the end val and number of consecutive sequence to that end.

A question is that how we should deal with the duplicates. We can’t save the information if there’s already a val has been dealed with. Otherwise it will make the HashMap with a wrong number of consecutive sequence.

class Solution {
    public int longestConsecutive(int[] nums) {
        HashMap<Integer, Integer> start = new HashMap<>();
        HashMap<Integer, Integer> end = new HashMap<>();
        
        HashSet<Integer> inserted = new HashSet<>();
        
        for (int i:nums){
            if (inserted.contains(i)){
                continue;
            }
            
            int low = i-1;
            int high = i+1;
            
            int c1 = start.getOrDefault(high, 0);
            int c2 = end.getOrDefault(low, 0);
                
            if (c1 != 0){
                start.remove(high);
            }
            
            if (c2 != 0){
                end.remove(low);
            }
                
            start.put(i-c2, c1+c2+1);
            end.put(i+c1, c1+c2+1);
            
            inserted.add(i);
        }
        
        int max = 0;
        for (Map.Entry<Integer, Integer> entry:start.entrySet()){
            max = Math.max(entry.getValue(), max);
        }
        
        return max;
    }
}

Another solution is much better and easier to understand. The idea is to save all the nums in a HashSet. And find the smallest val in a consecutive sequence and check this consecutive sequence’s length.

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {
            if (!num_set.contains(num-1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum+1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

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

        return longestStreak;
    }
}

What to improve

• be careful about the duplicates.