Union Find Thinking Process
If we regard a consecutive sequence as a conected component (or a disjoint set), the problem becomes to get the size of largest connected component (or set).\n\
If we regard a consecutive sequence as a `conected component` (or a `disjoint set`), the problem becomes to get the size of largest connected component (or `set`).\n\nA node is a value of an element in nums in this case.\nTwo nodes are **connected** if they are consecutive.\n\nO(N) time complexity is reqruired, so given `nums[i]`, we should tell index of `nums[i] - 1` if any, and `nums[i] + 1` if any in O(1). That can be achieved using a map that maps value to index.\n\nPlease note that for duplicate elements, we count only once. \n****\n```\nclass Solution {\n    public int longestConsecutive(int[] nums) {\n        UF uf = new UF(nums.length);\n        // Map val to index in nums\n        Map<Integer, Integer> valToIndex = new HashMap<>();\n        \n        for (int i = 0; i < nums.length; i++) {\n            if (valToIndex.containsKey(nums[i])) {\n                continue;\n            }\n            \n            if (valToIndex.containsKey(nums[i] - 1)) {\n                uf.union(i, valToIndex.get(nums[i] - 1));\n            }\n            \n            if (valToIndex.containsKey(nums[i] + 1)) {\n                uf.union(i, valToIndex.get(nums[i] + 1));\n            }\n            \n            valToIndex.put(nums[i], i);\n        }\n        \n        return uf.getLargetComponentSize();\n    }\n    \n    class UF {\n        private int[] parent;\n        private int[] size;\n        \n        public UF(int n) {\n            parent = new int[n];\n            size = new int[n];\n            for (int i = 0; i < n; i++) {\n                parent[i] = i;\n                size[i] = 1;\n            }\n        }\n        \n        public void union(int x, int y) { // connected if consecutive\n            int rootX = find(x);\n            int rootY = find(y);\n            if (rootX != rootY) {\n                parent[rootX] = rootY;\n                size[rootY] += size[rootX];\n            }\n        };\n        \n        private int find(int x) {\n            if (parent[x] == x) {\n                return x;\n            }\n            \n            return parent[x] = find(parent[x]);\n        };\n        \n        public int getLargetComponentSize() {\n            int maxSize = 0;\n            for (int i = 0; i < parent.length; i++) {\n                if (parent[i] == i && size[i] > maxSize) {\n                    maxSize = size[i];\n                }\n            }\n            \n            return maxSize;\n        }\n    }\n}\n```
['Union Find']