Java | MLE BitSet to UnionFind | 90% Speed
I am very sick today but at last, I managed to do this hard. My head hurts a lot, so I\'d try my best to be as clear as I can.\n\nI convert all the treenodes in
I am very sick today but at last, I managed to do this hard. My head hurts a lot, so I\'d try my best to be as clear as I can.\n\nI convert all the treenodes in array form to tree forms first, because that\'s what I\'m familiar with, and I feel dizzy, so really hard to think straight.\nIt takes linear time, so it is not of any conern.\n```Java\n        int[] ans = new int[parents.length];\n        Node[] all = new Node[parents.length];\n        int max = 0;\n        for (int i = 0 ; i < nums.length; i++){\n            all[i] = new Node(i, nums[i]);\n            max = Math.max(max, nums[i]);\n        }\n        for (int i = 1; i < parents.length; i++){\n            all[parents[i]].nodes.add(all[i]);\n        }\n```\n\nMy first idea is to use BitSet `or` method to keep track of what each subtree has. It works great, basically we `or` all the BiSet from the subtrees, keep track of the maximum of all the missing positives from its subtree (call it `m`), and call `nextClearBit(m)` method to find the first missing positive.\n\nAs for why we are taking the maximum of all answer from a node\'s subtrees, it is because if subtree A ans (first missing positive) is `a`, and subtree B ans is `b`, then subtree A and B\'s parent\'s ans must be at least `max(a, b)`, otherwise it is a contridiction. \n\nIt quickly passes all test cases but it says "All test cases passed but used too much memory". Bummer!\n```Java\n//     private BitSet solve(Node root, int[] ans){\n//         BitSet bit = new BitSet();\n//         if (root == null)\n//             return bit;\n//         int max = 1;\n//         for (Node child : root.nodes){\n//             bit.or(solve(child, ans));\n//             max = Math.max(ans[child.idx], max);\n//         }\n//         bit.set(root.val);\n//         ans[root.idx] = bit.nextClearBit(max);\n//         return bit;\n//     }\n```\nThen I remember union find should work here. Each value is its own parent, and so just union all the subtree, and find the first missing positive with a simple `while` loop. It should use less memory than BitSet, hopefully. And it is! passed with 90% speed.\n\n```Java\n    private void solve(Node root, int[] ans, UF uf){\n        int max = 1;\n        for (Node child : root.nodes){\n            solve(child, ans, uf);\n            uf.union(root.val, child.val);\n            max = Math.max(ans[child.idx], max);\n        }\n        while(max <= ans.length && uf.isConnected(max, root.val)){\n            ++max;\n        }\n        ans[root.idx] = max;\n    }\n```\n\nHere is all the codes. It is a bit long:\n\n```Java\nclass Solution {\n    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {\n        int[] ans = new int[parents.length];\n        Node[] all = new Node[parents.length];\n        int max = 0;\n        for (int i = 0 ; i < nums.length; i++){\n            all[i] = new Node(i, nums[i]);\n            max = Math.max(max, nums[i]);\n        }\n        for (int i = 1; i < parents.length; i++){\n            all[parents[i]].nodes.add(all[i]);\n        }\n        solve(all[0], ans, new UF(++max, nums));\n        return ans;\n    }\n\n    private void solve(Node root, int[] ans, UF uf){\n        int max = 1;\n        for (Node child : root.nodes){\n            solve(child, ans, uf); // post-order traversal.\n            uf.union(root.val, child.val); // then we union cur node with its subtree\n            max = Math.max(ans[child.idx], max); // find the max\n        }\n        while(max <= ans.length && uf.isConnected(max, root.val)){\n            ++max;\n        }\n        ans[root.idx] = max;\n    }\n\n    private class Node { // TreeNode\n        int idx;\n        int val;\n        List<Node> nodes;\n        Node (int idx, int val){\n            this.idx = idx;\n            this.val = val;\n            nodes = new ArrayList<>();\n        }\n    }\n\n    private class UF { // normal union find template.\n        int[] rank;\n        int[] parent;\n        UF (int n, int[] nums){\n            rank = new int[n];\n            parent = new int[n];\n            for (int m : nums){\n                parent[m] = m;\n            }\n        }\n\n        private int find(int x){\n            return x == parent[x]? x : (parent[x] = find(parent[x]));\n        }\n\n        private void union(int x, int y){\n            x = find(x); y = find(y);\n            if (rank[x] > rank[y]){\n                parent[y] = x;\n            }else{\n                parent[x] = y;\n                if (rank[x] == rank[y]){\n                    rank[y]++;\n                }\n            }\n        }\n\n        private boolean isConnected(int x, int y){\n            return find(x) == find(y);\n        }\n    }\n}\n\n// class Solution {\n//     public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {\n//         int[] ans = new int[parents.length];\n//         Map<Integer, Node> map = new HashMap<>();\n//         for (int i = 0 ; i < nums.length; i++){\n//             map.put(i, new Node(i, nums[i]));\n//         }\n//         for (int i = 1; i < parents.length; i++){\n//             map.get(parents[i]).nodes.add(map.get(i));\n//         }\n//         solve(map.get(0), ans);\n//         return ans;\n//     }\n\n//     private BitSet solve(Node root, int[] ans){\n//         BitSet bit = new BitSet();\n//         if (root == null)\n//             return bit;\n//         int max = 1;\n//         for (Node child : root.nodes){\n//             bit.or(solve(child, ans));\n//             max = Math.max(ans[child.idx], max);\n//         }\n//         bit.set(root.val);\n//         ans[root.idx] = bit.nextClearBit(max);\n//         return bit;\n//     }\n\n//     private class Node {\n//         int idx;\n//         int val;\n//         List<Node> nodes;\n//         Node (int idx, int val){\n//             this.idx = idx;\n//             this.val = val;\n//             nodes = new ArrayList<>();\n//         }\n//     }\n// }\n```
['Union Find', 'Java']