Java | Set and Union Find | Easy explanation ✅
Terminology\nLet\'s call a contiguous section of videos a component.\nEx: [1,2,4,5,6,8,9]\nComponents: [1,2], [4,5,6], [8,9]\n\n#### Logic:\n Keep a set for see
#### Terminology\nLet\'s call a contiguous section of videos a component.\nEx: [1,2,4,5,6,8,9]\nComponents: [1,2], [4,5,6], [8,9]\n\n#### Logic:\n* Keep a set for seen elements.\n* Maintain a union find set with n+1 elements\n\t* Larger root will become the root while doing union operation. Thus, root of an element would be the largest element of that component.\n* upload():\n\t* add the element to set\n\t* if neighbors are already uploaded, union with them as well\n* longest():\n\t* return the root of 0(the largest element of the component having 0).\n\n```\nclass LUPrefix {\n    \n    private Set<Integer> seen;\n    private DisjointSet ds;\n    \n    public LUPrefix(int n) {\n        seen = new HashSet<>();\n        seen.add(0);\n        \n        ds = new DisjointSet(n+1);\n    }\n    \n    public void upload(int video) {\n        seen.add(video);\n        \n        if(seen.contains(video-1))\n            ds.union(video-1, video);\n        if(seen.contains(video+1))\n            ds.union(video, video+1);\n    }\n    \n    public int longest() {\n        return ds.find(0);\n    }\n}\n\nclass DisjointSet {\n    int[] root;\n\n    public DisjointSet(int n) {\n        root = new int[n+1];\n\n        for(int i=0 ; i<n+1 ; i++) {\n            root[i] = i;\n        }\n    }\n\n    public void union(int x, int y) {\n        int rootX = find(x);\n        int rootY = find(y);\n\n        if(rootX != rootY) {\n            if(rootX > rootY)\n                root[rootY] = rootX;\n            else\n                root[rootX] = rootY;\n        }\n    }\n\n    public int find(int x) {\n        if(root[x]==x)\n            return root[x];\n\n        root[x] = find(root[x]);\n        return root[x];\n    }\n}\n```
['Union Find', 'Ordered Set', 'Java']