Group Hashmap || runtime 50.00% memory 75.00% || Python
Idk why runtime and memory is exactly at half and 3/4. Apparently my runtime(1304ms) falls right between two ends of the spectrum. Don\'t know why, but oh well.
Idk why runtime and memory is exactly at half and 3/4. Apparently my runtime(1304ms) falls right between two ends of the spectrum. Don\'t know why, but oh well. I guess nobody else tried this solution.\n![image](https://assets.leetcode.com/users/images/8009bcab-60ca-4cea-95dc-7352cc72aeac_1711676930.5786657.png)\n\n\n\nThe main idea here is to build up "groups" of friends where two friends belong to the same group if they have some common friend. We store which group an element belongs in with a hashmap mapping the element to its group. So, if we have\nA and B are friends\nB and C are friends\nA and E are friends\nF and G are friends\nD has no friends\nThen A,B,C,E is a group(say group 1), F,G is a group(say group 2), and we don\'t actually need to put D in a group. The purpose of the group is to see if there are other people connected to a person you\'re trying to friend who may have restrictions to you, and if D has no friends, there\'s nobody else to worry about, and hence no need for a group. So, our group map will look like:\n```\n{\nA: 1,\nB: 1,\nC: 1,\nE: 1,\nF: 2,\nG: 2\n}\n```\nNow, let\'s say B and F wanted to become friends. We would now have to merge the two groups. So, we\'d check if there are any restrictions between A/B/C/E and F, or restrictions between A/B/C/E and G. If there aren\'t any, we merge, and convert F and G to group 1.  Inspired by this, we can now write an outline for our code:\n\nLoop over all friend requests. Say the current request is [A,B]\n1. If there\'s an immediate restriction(A is trying to connect with B when [A,B] is a restriction) block the FR\n2. If A and B are both not in a group, assign A and B to a new group. We can do this by keeping a group counter and increase it whenever a new group is created(so new groups are always unique). There\'s nothing requiring the groups to be continuous or anything, so when two groups merge we don\'t need to worry about updating the other group numbers or the counter.\n3. If A isn\'t in a group and B is(or vice versa), check for any restrictions between A and members of B\'s group. If there aren\'t any, add A to B\'s group\n4. If A and B are both in the same group, the request is obviously fine, nothing needs to change\n5. If A and B are both in different groups, check for any restrictions between members of A\'s group and members of B\'s group. If there aren\'t any, update everyone in the smaller group to the bigger group(smaller->bigger so less overhead)\n6. If the FR was handled fine, push "true" to the results list\n\nThis is all we need! The code implementation is below.\n\n\n\n```\n"""\nRuntime: 1304 ms, faster than 50.00% of Python online submissions for Process Restricted Friend Requests.\nMemory Usage: 12.4 MB, less than 75.00% of Python online submissions for Process Restricted Friend Requests.\n"""\n\nclass Solution(object):\n    def friendRequests(self, n, restrictions, requests):\n        """\n        :type n: int\n        :type restrictions: List[List[int]]\n        :type requests: List[List[int]]\n        :rtype: List[bool]\n        """\n        \n        groupMap = {}\n        groupCounter = 0\n        result = []\n        for req in requests:\n            ans = False\n            if [req[0],req[1]] not in restrictions and [req[1],req[0]] not in restrictions:\n                # 1\n                if req[0] not in groupMap.keys() and req[1] not in groupMap.keys():\n                    groupMap.update({req[0]:groupCounter})\n                    groupMap.update({req[1]:groupCounter})\n                    groupCounter += 1\n                    ans = True\n                # 2\n                elif (req[0] not in groupMap.keys() and req[1] in groupMap.keys()) or (req[1] not in groupMap.keys() and req[0] in groupMap.keys()):\n                    if req[1] not in groupMap.keys() and req[0] in groupMap.keys():\n                        req[0], req[1] = req[1], req[0]\n                    \n                    failed = False\n                    for rest in restrictions:\n                        if (rest[0] == req[0] and rest[1] in groupMap and groupMap[rest[1]] == groupMap[req[1]]) or (rest[1] == req[0] and rest[0] in groupMap and groupMap[rest[0]] == groupMap[req[1]]):\n                            failed = True\n                            break\n                    if failed == False:\n                        groupMap.update({req[0]:groupMap[req[1]]})\n                        ans = True\n                elif req[0] in groupMap.keys() and req[1] in groupMap.keys():\n                    if groupMap[req[0]] == groupMap[req[1]]:\n                        ans = True\n                    else:\n                        g1List = [k for k,v in groupMap.items() if v == groupMap[req[0]]]\n                        g2List = [k for k,v in groupMap.items() if v == groupMap[req[1]]]\n                        failed = False\n                        for rest in restrictions:\n                            if (rest[0] in g1List and rest[1] in g2List) or (rest[1] in g1List and rest[0] in g2List):\n                                failed = True\n                                break\n                        if failed == False:\n                            ans = True\n                            if len(g1List) <= len(g2List):\n                                for k in g1List:\n                                    groupMap.update({k:groupMap[req[1]]})\n                            else:\n                                for k in g2List:\n                                    groupMap.update({k:groupMap[req[0]]})\n                        \n                            \n            \n            \n            result.append(ans)\n        \n        return result\n```
['Python']