# Process Restricted Friend Requests
**Difficulty:** HARD
[External](https://leetcode.com/problems/process-restricted-friend-requests)
Canonical: https://scaleengineer.com/dsa/problems/process-restricted-friend-requests
**Algorithms:** [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Graph
---
## Problem
You are given an integer `n` indicating the number of people in a network. Each person is labeled from `0` to `n - 1`.

You are also given a **0-indexed** 2D integer array `restrictions`, where `restrictions[i] = [xi, yi]` means that person `xi` and person `yi` **cannot** become **friends**,either **directly** or **indirectly** through other people.

Initially, no one is friends with each other. You are given a list of friend requests as a **0-indexed** 2D integer array `requests`, where `requests[j] = [uj, vj]` is a friend request between person `uj` and person `vj`.

A friend request is **successful** if `uj` and `vj` can be **friends**. Each friend request is processed in the given order (i.e., `requests[j]` occurs before `requests[j + 1]`), and upon a successful request, `uj` and `vj` **become direct friends** for all future friend requests.

Return _a **boolean array**_ `result`, _where each_ `result[j]` _is_ `true` _if the_ `jth` _friend request is **successful** or_ `false` _if it is not_.

**Note:** If `uj` and `vj` are already direct friends, the request is still **successful**.

**Example 1:**

**Input:** n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]]
**Output:** [true,false]
**Explanation:**
Request 0: Person 0 and person 2 can be friends, so they become direct friends. 
Request 1: Person 2 and person 1 cannot be friends since person 0 and person 1 would be indirect friends (1--2--0).

**Example 2:**

**Input:** n = 3, restrictions = [[0,1]], requests = [[1,2],[0,2]]
**Output:** [true,false]
**Explanation:**
Request 0: Person 1 and person 2 can be friends, so they become direct friends.
Request 1: Person 0 and person 2 cannot be friends since person 0 and person 1 would be indirect friends (0--2--1).

**Example 3:**

**Input:** n = 5, restrictions = [[0,1],[1,2],[2,3]], requests = [[0,4],[1,2],[3,1],[3,4]]
**Output:** [true,false,true,false]
**Explanation:**
Request 0: Person 0 and person 4 can be friends, so they become direct friends.
Request 1: Person 1 and person 2 cannot be friends since they are directly restricted.
Request 2: Person 3 and person 1 can be friends, so they become direct friends.
Request 3: Person 3 and person 4 cannot be friends since person 0 and person 1 would be indirect friends (0--4--3--1).

**Constraints:**

* `2 <= n <= 1000`
* `0 <= restrictions.length <= 1000`
* `restrictions[i].length == 2`
* `0 <= xi, yi <= n - 1`
* `xi != yi`
* `1 <= requests.length <= 1000`
* `requests[j].length == 2`
* `0 <= uj, vj <= n - 1`
* `uj != vj`

# Approaches
## Brute-Force with Graph Traversal
This approach models the network of friends as a graph. For each friend request, we tentatively add the new friendship (an edge) and then check if this new connection violates any of the given restrictions. A violation occurs if a restricted pair of people become connected, directly or indirectly.
**Time:** O(R * S * (n + E)), where `R` is the number of requests, `S` is the number of restrictions, `n` is the number of people, and `E` is the current number of friendships (edges). Since `E` can be at most `R`, the complexity is O(R * S * (n + R)). · **Space:** O(n + R) to store the adjacency list and auxiliary data structures for BFS/DFS (like a visited array and queue). The temporary copy of the graph also contributes to this space.
**Pros:** Conceptually simple and directly follows the problem's logic.; Easy to implement if familiar with basic graph algorithms.
**Cons:** Highly inefficient due to repeated graph traversals.; Creates a temporary copy of the graph for each request, which is memory-intensive.; Will likely result in a 'Time Limit Exceeded' error for large inputs.
### Explanation
We maintain an adjacency list to represent the current friendships, which is initially empty. We process each friend request `[u, v]` in order. For a given request, we simulate adding an edge between `u` and `v` by creating a temporary copy of the graph. Then, we check if this temporary change leads to a violation. A violation means that for at least one pair `[x, y]` in `restrictions`, `x` and `y` are now connected in the temporary graph. We can check for connectivity using a graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS). If any restriction is violated, the request is unsuccessful. If we check all restrictions and find no violations, the request is successful, and we update the main graph by permanently adding the edge `(u, v)`. This process is repeated for all requests.

```java
class Solution {
    public boolean[] processRequests(int n, int[][] restrictions, int[][] requests) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        boolean[] result = new boolean[requests.length];

        for (int i = 0; i < requests.length; i++) {
            int u = requests[i][0];
            int v = requests[i][1];

            // Create a temporary graph to test the new connection
            List<List<Integer>> tempAdj = new ArrayList<>();
            for(int k=0; k<n; k++) {
                tempAdj.add(new ArrayList<>(adj.get(k)));
            }
            tempAdj.get(u).add(v);
            tempAdj.get(v).add(u);

            boolean possible = true;
            for (int[] restriction : restrictions) {
                int x = restriction[0];
                int y = restriction[1];
                if (areConnected(x, y, n, tempAdj)) {
                    possible = false;
                    break;
                }
            }

            result[i] = possible;
            if (possible) {
                adj.get(u).add(v);
                adj.get(v).add(u);
            }
        }
        return result;
    }

    private boolean areConnected(int start, int end, int n, List<List<Integer>> adj) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            if (curr == end) {
                return true;
            }
            for (int neighbor : adj.get(curr)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
        return false;
    }
}
```
### Algorithm
1. Initialize an adjacency list `adj` for `n` people to represent the friendship graph.
2. Create a boolean array `result` to store the outcome of each request.
3. Iterate through each request `[u, v]`:
    a. Create a temporary copy of the current adjacency list.
    b. Add an edge between `u` and `v` in the temporary copy.
    c. Assume the request is valid (`possible = true`).
    d. For each restriction `[x, y]`:
        i. Use BFS or DFS on the temporary graph to check if `x` and `y` are connected.
        ii. If they are connected, set `possible = false` and break the loop.
    e. Store `possible` in the `result` array.
    f. If `possible` is true, update the main adjacency list `adj` by adding the edge `(u, v)`.
4. Return the `result` array.

## Optimized Approach using Union-Find
A more efficient solution uses a Union-Find (or Disjoint Set Union - DSU) data structure. This structure is ideal for tracking sets of connected elements, which in this problem are the friend groups. Instead of simulating each potential friendship on a full graph, we use DSU to quickly check if merging two friend groups would violate a restriction.
**Time:** O(R * S * α(n)), where `R` is the number of requests, `S` is the number of restrictions, and `α(n)` is the extremely slow-growing inverse Ackermann function. For all practical purposes, `α(n)` is a small constant (less than 5). · **Space:** O(n) to store the parent and rank/size arrays for the DSU structure.
**Pros:** Very efficient, with near-constant time operations for `find` and `union`.; Low memory overhead.; The standard and optimal solution for dynamic connectivity problems.
**Cons:** Requires understanding of the Union-Find data structure, which is less common than basic graph traversal.
### Explanation
We start by initializing a DSU structure where each of the `n` people is in their own disjoint set. We then process each friend request `[u, v]` sequentially.
For each request, we first find the representatives (or roots) of the sets containing `u` and `v`. If they are already the same, they are in the same friend group, and the request is trivially successful.
If they are in different groups, we must check if merging their groups is permissible. A merge is not allowed if it would place a restricted pair `[x, y]` in the same group. This would happen if one person from the restricted pair is in `u`'s group and the other is in `v`'s group. We can check this by iterating through all restrictions `[x, y]` and comparing their group representatives with those of `u` and `v`. If `find(x) == find(u)` and `find(y) == find(v)` (or vice-versa), the merge is invalid.
If no such conflict is found after checking all restrictions, the request is successful, and we perform the `union(u, v)` operation to merge their groups permanently. Otherwise, the request is unsuccessful, and we do nothing.
The results for each request are stored and returned.

```java
class DSU {
    private int[] parent;
    private int[] rank;

    public DSU(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]); // Path compression
    }

    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            // Union by rank
            if (rank[rootI] > rank[rootJ]) {
                parent[rootJ] = rootI;
            } else if (rank[rootI] < rank[rootJ]) {
                parent[rootI] = rootJ;
            } else {
                parent[rootJ] = rootI;
                rank[rootI]++;
            }
        }
    }
}

class Solution {
    public boolean[] processRequests(int n, int[][] restrictions, int[][] requests) {
        DSU dsu = new DSU(n);
        boolean[] result = new boolean[requests.length];

        for (int i = 0; i < requests.length; i++) {
            int u = requests[i][0];
            int v = requests[i][1];

            int rootU = dsu.find(u);
            int rootV = dsu.find(v);

            if (rootU == rootV) {
                result[i] = true; // Already friends, request is successful
                continue;
            }

            boolean canBeFriends = true;
            for (int[] restriction : restrictions) {
                int x = restriction[0];
                int y = restriction[1];
                int rootX = dsu.find(x);
                int rootY = dsu.find(y);

                if ((rootX == rootU && rootY == rootV) || (rootX == rootV && rootY == rootU)) {
                    canBeFriends = false;
                    break;
                }
            }

            result[i] = canBeFriends;
            if (canBeFriends) {
                dsu.union(u, v);
            }
        }

        return result;
    }
}
```
### Algorithm
1. Initialize a DSU data structure for `n` people.
2. Create a boolean array `result` to store outcomes.
3. For each request `[u, v]`:
    a. Find the representatives for `u` and `v`: `rootU = find(u)`, `rootV = find(v)`.
    b. If `rootU == rootV`, the request is successful. Continue to the next request.
    c. Otherwise, assume the request is valid (`canBeFriends = true`).
    d. For each restriction `[x, y]`:
        i. Find representatives for `x` and `y`: `rootX = find(x)`, `rootY = find(y)`.
        ii. Check if `(rootX == rootU && rootY == rootV) || (rootX == rootV && rootY == rootU)`. 
        iii. If the condition is true, a restriction is violated. Set `canBeFriends = false` and break.
    e. Store `canBeFriends` in the `result` array.
    f. If `canBeFriends` is true, perform `union(u, v)`.
4. Return the `result` array.

# Solutions
### Java

```java
class Solution {
private
  int[] p;
public
  boolean[] friendRequests(int n, int[][] restrictions, int[][] requests) {
    p = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    boolean[] ans = new boolean[requests.length];
    int i = 0;
    for (int[] req : requests) {
      int u = req[0], v = req[1];
      if (find(u) == find(v)) {
        ans[i++] = true;
      } else {
        boolean valid = true;
        for (int[] res : restrictions) {
          int x = res[0], y = res[1];
          if ((find(u) == find(x) && find(v) == find(y)) ||
              (find(u) == find(y) && find(v) == find(x))) {
            valid = false;
            break;
          }
        }
        if (valid) {
          p[find(u)] = find(v);
          ans[i++] = true;
        } else {
          ans[i++] = false;
        }
      }
    }
    return ans;
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> p;
  vector<bool> friendRequests(int n, vector<vector<int>> &restrictions,
                              vector<vector<int>> &requests) {
    p.resize(n);
    for (int i = 0; i < n; ++i)
      p[i] = i;
    vector<bool> ans;
    for (auto &req : requests) {
      int u = req[0], v = req[1];
      if (find(u) == find(v))
        ans.push_back(true);
      else {
        bool valid = true;
        for (auto &res : restrictions) {
          int x = res[0], y = res[1];
          if ((find(u) == find(x) && find(v) == find(y)) ||
              (find(u) == find(y) && find(v) == find(x))) {
            valid = false;
            break;
          }
        }
        ans.push_back(valid);
        if (valid)
          p[find(u)] = find(v);
      }
    }
    return ans;
  }
  int find(int x) {
    if (p[x] != x)
      p[x] = find(p[x]);
    return p[x];
  }
};

```

### Python

```python
class Solution:
    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]: p = list(range(n)) def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] ans = [] i = 0 for u, v in requests: if find(u) == find(v): ans . append(True) else: valid = True for x, y in restrictions: if (find(u) == find(x) and find(v) == find(y)) or (find(u) == find(y) and find(v) == find(x)): valid = False break ans . append(valid) if valid: p[find(u)] = find(v) return ans

```