O(n) solution in Java
Intuition\n Describe your first thoughts on how to solve this problem. \nSince I have not seen O(n) solution in Java, decided to share mine. Cannot use Arrays.s
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSince I have not seen O(n) solution in Java, decided to share mine. Cannot use Arrays.sort because it is O(nlogn) complexity. Need to use Set or Map.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nPut all items to the HashSet which is O(n) complexity and then iterate again over the array. If element belongs to the sequence, calculate its length (both ways) and *remove* elements that belong to that sequence from HashSet so that they are not calculated again keeping time complexity at O(n).\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int longestConsecutive(int[] nums) {\n        int maxSeq = 0;\n        Set<Integer> sequences = new HashSet();\n        for (int num : nums) {\n            sequences.add(num);\n        }\n        for (int num : nums) {\n            int nextInSeq = num + 1;\n            int prevInSeq = num - 1;\n            int currentSequence = 1;\n            while (sequences.remove(prevInSeq--)) {\n                currentSequence++;\n            }\n            while (sequences.remove(nextInSeq++)) {\n                currentSequence++;\n            }\n            if (currentSequence > maxSeq) {\n                maxSeq = currentSequence;\n            }\n        }\n        return maxSeq;\n    }\n}\n```
['Java']