Disjoint Set || Java
Intuition\nFirst thing came to my mind was to use a disjoint set since different chains are merged at some point.\n\n\n# Approach\nI want to connect the current
# Intuition\nFirst thing came to my mind was to use a disjoint set since different chains are merged at some point.\n\n\n# Approach\nI want to connect the current index to its left and right and maintain the total size of the chain. Disjoint set is a great candidate.\n\nThis approach can be used to solve this problem too:\n[2382. Maximum Segment Sum After Removals](https://leetcode.com/contest/biweekly-contest-85/problems/maximum-segment-sum-after-removals/)\n\n# Complexity\n- Time complexity: Nlog(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: N\n\n# Code\n```\nclass LUPrefix {\n    DisjointSet d;\n\n    public LUPrefix(int n) {this.d = new DisjointSet(n);}\n    \n    public void upload(int video) {\n        d.merge(video-1, video);\n        d.merge(video+1, video);\n    }\n    \n    public int longest() {\n        return d.count.get(1) == null? 0:d.count.get(d.find(1));\n    }\n}\nclass DisjointSet{\n    int [] parent;\n    Map<Integer, Integer> count;\n    public DisjointSet(int n){\n        this.parent = new int [n+1];\n        Arrays.fill(parent, -1);\n        this.count = new HashMap<>();\n    }\n    public void make(int x){\n        parent[x] = x;\n        count.put(x, 1);\n    }\n    public int find(int x){\n        if(parent[x] == x) return x;\n        return parent[x] = find(parent[x]);\n    }\n    public void merge(int x, int y){\n        if(parent[y] == -1) make(y);\n        if(x <= 0 || x >= parent.length || parent[x] == -1) return;\n        int parX = find(x), parY = find(y);   \n        if(parX != parY){\n            parent[parX] = parY;\n            count.put(parY, count.get(parY) + count.get(parX));\n        }\n    }\n}\n```
['Java']