Java Clean and Commented Code With Explanation | Union-Find Algorithm
PREREQUISITE: UNION-FIND ALGORITHM\n\nThis problem is pretty straightforwad. Basically they are saying that two people can be friends if they have no restrictio
**PREREQUISITE: UNION-FIND ALGORITHM**\n\nThis problem is pretty straightforwad. Basically they are saying that two people can be friends if they have no restrictions or any of their mutual friends have no restriction.\n\nThe simplest way to solve this would be to use the union-find technique to link all the persons with mutual friends to one common ancestor. Now for every request we simply check that whether those ancestors have any restrictions or not. If they do they can\'t be friends or else they can be.\n\n**EDIT - There is a nice optimization that could be done inside findParent, check @chinghsuanwei0206\'s comment for explanation.**\n\nHere is the code for the same,\n\n```\nclass Solution {\n    \n    //Classic Union-Find Algorithm to find Common Ancestor\n    private int findParent(int[] parent, int index) {\n        if(parent[index] == index) return index;\n        return findParent(parent, parent[index]);\n    }\n   \n    public boolean[] friendRequests(int n, int[][] restrictions, int[][] requests) {\n        int resLength = restrictions.length, reqLength = requests.length;\n        boolean[] result = new boolean[reqLength];\n        int[] parent = new int[n];\n        \n        //Initially ith person\'s parent is i itself\n        for(int i = 0; i < n; i++) parent[i] = i;\n        \n\n        for(int i = 0; i < reqLength; i++) {\n            //finding the parents of the first person and second person of ith request\n            int firstParent = findParent(parent, requests[i][0]);\n            int secondParent = findParent(parent, requests[i][1]);\n            \n            //if they have same parents i.e. mutual friends they can be friends\n            if(firstParent == secondParent) {\n                result[i] = true;\n                continue;\n            }\n            \n            //iterating through the restrictions array to find whether the parents of first ans second person have a conflict \n            boolean flag = true;\n            for(int j = 0; j < resLength; j++) {\n                //finding parents of the restriction persons\n                int firstRestriction = findParent(parent, restrictions[j][0]);\n                int secondRestriction = findParent(parent, restrictions[j][1]);\n                \n                //if any of the parents are matching i.e. if the parents of first and second person have a mutual conflict they can\'t be friend\n                if((firstRestriction == firstParent && secondRestriction == secondParent) || (secondRestriction == firstParent && firstRestriction == secondParent)) {\n                    flag = false;\n                    break;\n                }\n            }\n            \n            if(flag) {\n                result[i] = true;\n                parent[firstParent] = secondParent; //setting the common ancestor -> classic union find technique\n            }\n        }\n        \n        return result;\n    }\n}\n```
['Java']