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 _aboolean array _result,where eachresult[j]istrue if thejth _friend request issuccessful or _false if it is not.

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

Examples

Example 1

1
2
3
4
5
6
7
8


    
    
    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

1
2
3
4
5
6
7
8


    
    
    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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


    
    
    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

Solution

Method 1 – Union-Find with Rollback

Intuition

We use Union-Find (Disjoint Set Union) to track friend groups. For each request, we check if merging the groups would violate any restriction. If not, we merge; otherwise, we skip. To avoid affecting future requests, we can simulate the merge and roll back if needed.

Approach

  1. For each request, find the roots of both people.
  2. If already in the same group, accept.
  3. Otherwise, check if merging would violate any restriction (i.e., if any restricted pair would end up in the same group).
  4. If not, merge and accept; else, reject.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {
        vector<int> parent(n);
        iota(parent.begin(), parent.end(), 0);
        function<int(int)> find = [&](int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); };
        vector<bool> res;
        for (auto& req : requests) {
            int u = find(req[0]), v = find(req[1]);
            bool ok = true;
            if (u != v) {
                for (auto& r : restrictions) {
                    int x = find(r[0]), y = find(r[1]);
                    if ((u == x && v == y) || (u == y && v == x)) {
                        ok = false; break;
                    }
                }
            }
            if (ok) {
                res.push_back(true);
                if (u != v) parent[u] = v;
            } else {
                res.push_back(false);
            }
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func friendRequests(n int, restrictions [][]int, requests [][]int) []bool {
    parent := make([]int, n)
    for i := range parent { parent[i] = i }
    var find func(int) int
    find = func(x int) int { if parent[x] != x { parent[x] = find(parent[x]) }; return parent[x] }
    res := make([]bool, 0, len(requests))
    for _, req := range requests {
        u, v := find(req[0]), find(req[1])
        ok := true
        if u != v {
            for _, r := range restrictions {
                x, y := find(r[0]), find(r[1])
                if (u == x && v == y) || (u == y && v == x) { ok = false; break }
            }
        }
        if ok {
            res = append(res, true)
            if u != v { parent[u] = v }
        } else {
            res = append(res, false)
        }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import java.util.*;
class Solution {
    public boolean[] friendRequests(int n, int[][] restrictions, int[][] requests) {
        int[] parent = new int[n];
        for (int i = 0; i < n; ++i) parent[i] = i;
        boolean[] res = new boolean[requests.length];
        for (int k = 0; k < requests.length; ++k) {
            int u = find(parent, requests[k][0]), v = find(parent, requests[k][1]);
            boolean ok = true;
            if (u != v) {
                for (int[] r : restrictions) {
                    int x = find(parent, r[0]), y = find(parent, r[1]);
                    if ((u == x && v == y) || (u == y && v == x)) { ok = false; break; }
                }
            }
            if (ok) {
                res[k] = true;
                if (u != v) parent[u] = v;
            } else {
                res[k] = false;
            }
        }
        return res;
    }
    private int find(int[] parent, int x) {
        if (parent[x] != x) parent[x] = find(parent, parent[x]);
        return parent[x];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    fun friendRequests(n: Int, restrictions: Array<IntArray>, requests: Array<IntArray>): BooleanArray {
        val parent = IntArray(n) { it }
        val res = BooleanArray(requests.size)
        fun find(x: Int): Int {
            if (parent[x] != x) parent[x] = find(parent[x])
            return parent[x]
        }
        for ((k, req) in requests.withIndex()) {
            val u = find(req[0]); val v = find(req[1])
            var ok = true
            if (u != v) {
                for (r in restrictions) {
                    val x = find(r[0]); val y = find(r[1])
                    if ((u == x && v == y) || (u == y && v == x)) { ok = false; break }
                }
            }
            if (ok) {
                res[k] = true
                if (u != v) parent[u] = v
            } else {
                res[k] = false
            }
        }
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

from typing import List
class Solution:
    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:
        parent = list(range(n))
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        res = []
        for u, v in requests:
            ru, rv = find(u), find(v)
            ok = True
            if ru != rv:
                for x, y in restrictions:
                    rx, ry = find(x), find(y)
                    if (ru == rx and rv == ry) or (ru == ry and rv == rx):
                        ok = False
                        break
            if ok:
                res.append(True)
                if ru != rv:
                    parent[ru] = rv
            else:
                res.append(False)
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

impl Solution {
    pub fn friend_requests(n: i32, restrictions: Vec<Vec<i32>>, requests: Vec<Vec<i32>>) -> Vec<bool> {
        let n = n as usize;
        let mut parent: Vec<usize> = (0..n).collect();
        fn find(parent: &mut Vec<usize>, x: usize) -> usize {
            if parent[x] != x { parent[x] = find(parent, parent[x]); }
            parent[x]
        }
        let mut res = Vec::new();
        for req in requests.iter() {
            let u = find(&mut parent, req[0] as usize);
            let v = find(&mut parent, req[1] as usize);
            let mut ok = true;
            if u != v {
                for r in restrictions.iter() {
                    let x = find(&mut parent, r[0] as usize);
                    let y = find(&mut parent, r[1] as usize);
                    if (u == x && v == y) || (u == y && v == x) { ok = false; break; }
                }
            }
            if ok {
                res.push(true);
                if u != v { parent[u] = v; }
            } else {
                res.push(false);
            }
        }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    friendRequests(n: number, restrictions: number[][], requests: number[][]): boolean[] {
        const parent = Array.from({length: n}, (_, i) => i);
        function find(x: number): number {
            if (parent[x] !== x) parent[x] = find(parent[x]);
            return parent[x];
        }
        const res: boolean[] = [];
        for (const [u, v] of requests) {
            const ru = find(u), rv = find(v);
            let ok = true;
            if (ru !== rv) {
                for (const [x, y] of restrictions) {
                    const rx = find(x), ry = find(y);
                    if ((ru === rx && rv === ry) || (ru === ry && rv === rx)) { ok = false; break; }
                }
            }
            if (ok) {
                res.push(true);
                if (ru !== rv) parent[ru] = rv;
            } else {
                res.push(false);
            }
        }
        return res;
    }
}

Complexity

  • ⏰ Time complexity: O(R * K) where R is the number of requests and K is the number of restrictions (since for each request we may check all restrictions).
  • 🧺 Space complexity: O(N) for the union-find structure.