My really simple Java O(n) solution - Accepted
We will use HashMap. The key thing is to keep track of the sequence length and store that in the boundary points of the sequence. For example, as a result, for 
We will use HashMap. The key thing is to keep track of the sequence length and store that in the boundary points of the sequence. For example, as a result, for sequence {1, 2, 3, 4, 5}, map.get(1) and map.get(5) should both return 5.\n\nWhenever a new element **n** is inserted into the map, do two things:\n\n 1. See if **n - 1** and **n + 1** exist in the map, and if so, it means there is an existing sequence next to **n**. Variables **left** and **right** will be the length of those two sequences, while **0** means there is no sequence and **n** will be the boundary point later. Store **(left + right + 1)** as the associated value to key **n** into the map.\n 2. Use **left** and **right** to locate the other end of the sequences to the left and right of **n** respectively, and replace the value with the new length.\n\n\nEverything inside the **for** loop is O(1) so the total time is O(n). Please comment if you see something wrong. Thanks.\n\n    public int longestConsecutive(int[] num) {\n        int res = 0;\n        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();\n        for (int n : num) {\n            if (!map.containsKey(n)) {\n                int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;\n                int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;\n                // sum: length of the sequence n is in\n                int sum = left + right + 1;\n                map.put(n, sum);\n                \n                // keep track of the max length \n                res = Math.max(res, sum);\n                \n                // extend the length to the boundary(s)\n                // of the sequence\n                // will do nothing if n has no neighbors\n                map.put(n - left, sum);\n                map.put(n + right, sum);\n            }\n            else {\n                // duplicates\n                continue;\n            }\n        }\n        return res;\n    }
[]