Scale Engineer

Process Restricted Friend Requests

Hard
#1890Time: 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.
Algorithms
Union Find
Data structures
Graph

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem