JavaScript Union Find
This solution uses a boilerplate for DSU that can be reused for other problems. Approach is based on other solutions posted on the discussion section. Please le
This solution uses a boilerplate for DSU that can be reused for other problems. Approach is based on other solutions posted on the discussion section. Please let me know if you have improvements or comments on time complexity.\n\n**Friend request function:**\n\t1. Add nodes 0 to n - 1 to DSU instance\n\t2. For each friend request [f1, f2], check each restriction pair [e1, e2]. \n\t3. Perform find on each of the four persons (f1, f2, e1, e2). \n\t4. If unionFind(f1) = unionFind(e1) and unionFind(f2) = unionFind(e2) OR viceversa, request is not valid.\n\n**Time complexity** \nI believe is O(N + MK). Step 1 takes O(N) where N is number of friends. Steps 2 - 4 take O(MK) where M are number of requests and K are number of restrictions.\nDSU finds and unions take an amortized time of O(1) because we are using path compression and union by rank.\n\n\n```\n/*\nDSU Class Template\n*/\nclass DSU {\n    constructor() {\n        this.parents = new Map();\n        this.rank = new Map();\n    }\n    \n    add(x) {\n        this.parents.set(x, x);\n        this.rank.set(x, 0);\n    }\n    \n    find(x) {\n        const parent = this.parents.get(x);\n        if (parent === x) return x;\n        const setParent = this.find(parent);\n        this.parents.set(x, setParent);\n        return setParent;\n    }\n    \n    union(x, y) {\n        const xParent = this.find(x), yParent = this.find(y);\n        const xRank = this.rank.get(xParent), yRank = this.rank.get(yParent);\n        if (xParent === yParent) return;\n        if (xRank > yRank) {\n            this.parents.set(yParent, xParent);\n        } else if (yRank > xRank) {\n            this.parents.set(xParent, yParent);\n        } else {\n            this.parents.set(xParent, yParent);\n            this.rank.set(yParent, yRank + 1);\n        }   \n    }\n}\n\n/*\nFriend Requests\n*/\nvar friendRequests = function(n, restrictions, requests) {\n    const dsu = new DSU(), result = [];\n    for (let i = 0; i < n; i++) dsu.add(i);\n    \n    for (let [friend1, friend2] of requests) {\n        const parent1 = dsu.find(friend1), parent2 = dsu.find(friend2);\n        let friendshipPossible = true;\n        for (let [enemy1, enemy2] of restrictions) {\n            const enemyParent1 = dsu.find(enemy1), enemyParent2 = dsu.find(enemy2);\n            const condition1 = (enemyParent1 === parent1 && enemyParent2 === parent2);\n            const condition2 = (enemyParent1 === parent2 && enemyParent2 === parent1);\n            if (condition1 || condition2) {\n                friendshipPossible = false;\n                break;\n            }\n        }\n        if (friendshipPossible) dsu.union(friend1, friend2);\n        result.push(friendshipPossible);\n    }\n    return result;\n};\n```
['Union Find', 'JavaScript']