LeetCode #2076 — HARD

Process Restricted Friend Requests

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The Problem

Problem Statement

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] = [x_i, y_i] means that person x_i and person y_i 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] = [u_j, v_j] is a friend request between person u_j and person v_j.

A friend request is successful if u_j and v_j 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, u_j and v_j become direct friends for all future friend requests.

Return a boolean array result, where each result[j] is true if the j^th friend request is successful or false if it is not.

Note: If u_j and v_j 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 <= x_i, y_i <= n - 1
x_i != y_i
1 <= requests.length <= 1000
requests[j].length == 2
0 <= u_j, v_j <= n - 1
u_j != v_j

Step 01

Brute Force Baseline

Problem summary: 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

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Union-Find

Example 1

3
[[0,1]]
[[0,2],[2,1]]

Example 2

3
[[0,1]]
[[1,2],[0,2]]

Example 3

5
[[0,1],[1,2],[2,3]]
[[0,4],[1,2],[3,1],[3,4]]

Core Insight

What unlocks the optimal approach

For each request, we could loop through all restrictions. Can you think of doing a check-in close to O(1)?
Could you use Union Find?

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #2076: Process Restricted Friend Requests
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;
        }
        int m = requests.length;
        boolean[] ans = new boolean[m];
        for (int i = 0; i < m; ++i) {
            int u = requests[i][0], v = requests[i][1];
            int pu = find(u), pv = find(v);
            if (pu == pv) {
                ans[i] = true;
            } else {
                boolean ok = true;
                for (var r : restrictions) {
                    int px = find(r[0]), py = find(r[1]);
                    if ((pu == px && pv == py) || (pu == py && pv == px)) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    ans[i] = true;
                    p[pu] = pv;
                }
            }
        }
        return ans;
    }

    private int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }
}

// Accepted solution for LeetCode #2076: Process Restricted Friend Requests
func friendRequests(n int, restrictions [][]int, requests [][]int) (ans []bool) {
	p := make([]int, n)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for _, req := range requests {
		pu, pv := find(req[0]), find(req[1])
		if pu == pv {
			ans = append(ans, true)
		} else {
			ok := true
			for _, r := range restrictions {
				px, py := find(r[0]), find(r[1])
				if px == pu && py == pv || px == pv && py == pu {
					ok = false
					break
				}
			}
			ans = append(ans, ok)
			if ok {
				p[pv] = pu
			}
		}
	}
	return
}

# Accepted solution for LeetCode #2076: Process Restricted Friend Requests
class Solution:
    def friendRequests(
        self, n: int, restrictions: List[List[int]], requests: List[List[int]]
    ) -> List[bool]:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        p = list(range(n))
        ans = []
        for u, v in requests:
            pu, pv = find(u), find(v)
            if pu == pv:
                ans.append(True)
            else:
                ok = True
                for x, y in restrictions:
                    px, py = find(x), find(y)
                    if (pu == px and pv == py) or (pu == py and pv == px):
                        ok = False
                        break
                ans.append(ok)
                if ok:
                    p[pu] = pv
        return ans

// Accepted solution for LeetCode #2076: Process Restricted Friend Requests
/**
 * [2076] Process Restricted Friend Requests
 *
 * 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 j^th 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
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/process-restricted-friend-requests/
// discuss: https://leetcode.com/problems/process-restricted-friend-requests/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn friend_requests(
        n: i32,
        restrictions: Vec<Vec<i32>>,
        requests: Vec<Vec<i32>>,
    ) -> Vec<bool> {
        vec![]
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_2076_example_1() {
        let n = 3;
        let restrictions = vec![vec![0, 1]];
        let requests = vec![vec![0, 2], vec![2, 1]];

        let result = vec![true, false];

        assert_eq!(Solution::friend_requests(n, restrictions, requests), result);
    }

    #[test]
    #[ignore]
    fn test_2076_example_2() {
        let n = 3;
        let restrictions = vec![vec![0, 1]];
        let requests = vec![vec![1, 2], vec![0, 2]];

        let result = vec![true, false];

        assert_eq!(Solution::friend_requests(n, restrictions, requests), result);
    }

    #[test]
    #[ignore]
    fn test_2076_example_3() {
        let n = 3;
        let restrictions = vec![vec![0, 1], vec![1, 2], vec![2, 3]];
        let requests = vec![vec![0, 4], vec![1, 2], vec![3, 1], vec![3, 4]];

        let result = vec![true, false, true, false];

        assert_eq!(Solution::friend_requests(n, restrictions, requests), result);
    }
}

// Accepted solution for LeetCode #2076: Process Restricted Friend Requests
function friendRequests(n: number, restrictions: number[][], requests: number[][]): boolean[] {
    const p: number[] = Array.from({ length: n }, (_, i) => i);
    const find = (x: number): number => {
        if (p[x] !== x) {
            p[x] = find(p[x]);
        }
        return p[x];
    };
    const ans: boolean[] = [];
    for (const [u, v] of requests) {
        const pu = find(u);
        const pv = find(v);
        if (pu === pv) {
            ans.push(true);
        } else {
            let ok = true;
            for (const [x, y] of restrictions) {
                const px = find(x);
                const py = find(y);
                if ((px === pu && py === pv) || (px === pv && py === pu)) {
                    ok = false;
                    break;
                }
            }
            ans.push(ok);
            if (ok) {
                p[pu] = pv;
            }
        }
    }
    return ans;
}

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(q × m × log(n)

Space

O(n)

Approach Breakdown

BRUTE FORCE

O(n²) time

O(n) space

Track components with a list or adjacency matrix. Each union operation may need to update all n elements’ component labels, giving O(n) per union. For n union operations total: O(n²). Find is O(1) with direct lookup, but union dominates.

UNION-FIND

O(α(n)) time

O(n) space

With path compression and union by rank, each find/union operation takes O(α(n)) amortized time, where α is the inverse Ackermann function — effectively constant. Space is O(n) for the parent and rank arrays. For m operations on n elements: O(m × α(n)) total.

Shortcut: Union-Find with path compression + rank → O(α(n)) per operation ≈ O(1). Just say “nearly constant.”

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.