Python UnionFind
Expand size of neighbors if they are at least 1. longest() just returns the size of parent of 0.\n\nTime:\n- upload: amortized O(1)\n- longest: amortized O(1)\n
Expand size of neighbors if they are at least 1. longest() just returns the size of parent of 0.\n\nTime:\n- upload: amortized O(1)\n- longest: amortized O(1)\n\nSpace: O(n)\n\n```python\nclass UF:\n    def __init__(self, n):\n        self.parents = [i for i in range(n)]\n        self.size = [0] * n\n        \n    def find(self, x):\n        px = self.parents[x]\n        if x != px:\n            self.parents[x] = self.find(px)\n            \n        return self.parents[x]\n    \n    def union(self, x, y):\n        px, py = self.find(x), self.find(y)\n        if px != py:\n            self.parents[px] = py\n            self.size[py] += self.size[px]\n\t\t\t\n    def getsize(self, x):\n        return self.size[self.find(x)]\n\t\t\nclass LUPrefix:\n\n    def __init__(self, n: int):\n        self.uf = UF(n)\n        self.n = n\n                \n    def upload(self, video: int) -> None:\n        i = video - 1\n        self.uf.size[i] += 1\n        if i > 0 and self.uf.getsize(i-1) > 0:\n            self.uf.union(i, i-1)\n        if i+1 < self.n and self.uf.getsize(i+1) > 0:\n            self.uf.union(i, i+1)\n        \n    def longest(self) -> int:\n        return self.uf.getsize(0)\n```
['Union Find', 'Python']