Longest Consecutive Sequence

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

Example:
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Method 1:

Use hashmap and linkedlist

Solution 1:

Time: O(n)
Space: O(n)

public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    static class Node {
        Integer val;
        Node prev;
        Node next;
        boolean visited;
        
        public Node(Integer val) {
            this.val = val;
            this.visited = false;
        }
        
        // @Override
        // public String toString() {
        //     String p = prev == null ? "NULL" : prev.val + "";
        //     String n = next == null ? "NULL" : next.val + "";
        //     return p + " <- " + val + " -> " + n;
        // }
    }
    
    public int longestConsecutive(final List<Integer> A) {
        // [100, 4, 200, 1, 3, 2]
        Map<Integer, Node> map = new HashMap<>();
        for (Integer i : A) {
            if (map.containsKey(i)) continue;
            Node node = new Node(i);
            // System.out.print(i + ": ");
            if (map.containsKey(i + 1)) {
                Node next = map.get(i + 1);
                node.next = next;
                next.prev = node;
            }
            if (map.containsKey(i - 1)) {
                Node prev = map.get(i - 1);
                node.prev = prev;
                prev.next = node;
            }
            map.put(i, node);
            // System.out.println(map);
        }

        int max = 0;
        for (Map.Entry<Integer, Node> entry : map.entrySet()) {
            Integer i = entry.getKey();
            Node node = entry.getValue();
            int val = 1;
            if (!node.visited) {
                Node prev = node.prev;
                while (prev != null && !prev.visited) {
                    val ++;
                    prev.visited = true;
                    prev = prev.prev;
                }
                Node next = node.next;
                while (next != null && !next.visited) {
                    val ++;
                    next.visited = true;
                    next = next.next;
                }
            }
            node.visited = true;
            max = Math.max(max, val);
        }
        return max;
    }
}

Method 2:

Use a set

Solution 2:

Time: O(n)
Space: O(n)

public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public int longestConsecutive(final List<Integer> A) {
        Set<Integer> set = new HashSet<>();
        for (int i : A) {
            set.add(i);
        }
        int max = 0;
        for (int i : A) {
            if (set.contains(i - 1)) {
                continue;
            } else {
                int cur = 0;
                int val = i;
                while (set.contains(val)) {
                    cur ++;
                    val ++;
                }
                max = Math.max(max, cur);
            }
        }
        return max;
    }
}

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int val : nums) {
            set.add(val);
        }
        int max = 0;
        for (int val : nums) {
            if (set.contains(val - 1)) {
                continue;
            }
            if (set.contains(val)) {
                int curLen = 0;
                while (set.contains(val)) {
                    curLen ++;
                    max = Math.max(max, curLen);
                    val ++;
                }
            }
        }
        return max;
    }
}