LeetCode 2076 - Process Restricted Friend Requests

This problem models a social network with friendship restrictions. We are given n people labeled from 0 to n - 1. Initially, nobody is connected to anyone else. Over time, friendship requests arrive one by one, and each request must be processed immediately.

leetcodehardunion-findgraph-theory

LeetCode Problem 2076

Difficulty: 🔴 Hard
Topics: Union-Find, Graph Theory

Solution

Problem Understanding

This problem models a social network with friendship restrictions. We are given n people labeled from 0 to n - 1. Initially, nobody is connected to anyone else. Over time, friendship requests arrive one by one, and each request must be processed immediately.

The important detail is that friendship is transitive. If person A is friends with B, and B is friends with C, then A and C are considered indirectly connected. Because of this, each accepted friendship request merges two social groups together.

The restrictions array defines pairs of people who are never allowed to end up in the same connected friendship group. Even indirect connections are forbidden. For example, if [0, 1] is a restriction, then any sequence of accepted friendships that would place 0 and 1 in the same connected component must be rejected.

The requests array contains friendship requests processed in order. For each request [u, v], we must determine whether accepting the friendship would violate any restriction. If not, we accept the request and permanently merge their groups. Otherwise, we reject it.

The output is a boolean array where:

  • true means the request was accepted
  • false means the request was rejected

The constraints are relatively small:

  • n <= 1000
  • restrictions.length <= 1000
  • requests.length <= 1000

These bounds are small enough that an O(R * Q) style solution is acceptable, where:

  • R is the number of restrictions
  • Q is the number of requests

However, recomputing connectivity from scratch for every request would still be unnecessarily expensive.

Several edge cases are important:

  • Two people may already belong to the same friendship group. In that case, the request is automatically valid because it changes nothing.
  • A restriction may become violated indirectly through multiple merges, not just through a direct friendship.
  • Multiple restrictions may involve the same people or groups.
  • Rejecting one request must not affect future requests.
  • Restrictions are symmetric. If [a, b] exists, then a cannot connect to b, and b cannot connect to a.

Approaches

Brute Force Approach

A straightforward solution is to explicitly maintain the friendship graph and run a graph traversal for every request.

For each request [u, v]:

  1. Temporarily add the friendship edge.
  2. For every restriction [x, y], check whether x and y become connected using DFS or BFS.
  3. If any restriction is violated, remove the temporary edge and reject the request.
  4. Otherwise, keep the edge and accept the request.

This works because it directly verifies whether the resulting graph satisfies all constraints after every request.

However, this approach is inefficient. Each request may require multiple graph traversals, and each traversal can visit the entire graph. With up to 1000 requests and 1000 restrictions, repeated connectivity searches become expensive.

Optimal Approach

The key observation is that we only care about connected components, not the exact graph structure inside them.

This naturally suggests using the Union-Find data structure, also called Disjoint Set Union, DSU.

Union-Find efficiently maintains groups of connected people. It supports:

  • Finding which group a person belongs to
  • Merging two groups together

For each friendship request [u, v]:

  1. Find the roots of u and v.
  2. Check every restriction [x, y].
  3. If merging the two groups would place x and y into the same component, reject the request.
  4. Otherwise, union the two groups.

The crucial insight is that restrictions only matter at the component level. We do not need to track individual friendship paths.

Because constraints are small, scanning all restrictions for each request is completely feasible.

Approach Time Complexity Space Complexity Notes
Brute Force O(Q × R × (N + E)) O(N + E) Repeated graph traversals after each request
Optimal O(Q × R × α(N)) O(N) Uses Union-Find to track connected components efficiently

Here:

  • Q = number of requests
  • R = number of restrictions
  • α(N) = inverse Ackermann function, effectively constant

Algorithm Walkthrough

  1. Initialize a Union-Find structure where each person starts in their own group.
  2. Maintain two arrays:
  • parent[i], which stores the representative of person i
  • rank[i] or size[i], which helps keep the tree balanced during unions
  1. For each friendship request [u, v], find their current component roots:
  • rootU = find(u)
  • rootV = find(v)
  1. If both people already belong to the same component, the request is automatically valid:
  • Accept the request
  • Append true to the answer
  • Continue to the next request
  1. Otherwise, test whether merging these two components would violate any restriction.
  2. For every restriction [x, y]:

  • Compute:

  • rootX = find(x)

  • rootY = find(y)

  • A violation occurs if:

  • rootX == rootU and rootY == rootV

  • or

  • rootX == rootV and rootY == rootU

  1. If any restriction would be violated:
  • Reject the request
  • Append false
  • Do not merge the components
  1. If no restriction is violated:
  • Union the two components
  • Append true
  1. Continue processing requests in order.

Why it works

Union-Find always maintains the exact connected components formed by accepted friendship requests. Before accepting a new request, we verify that no restriction pair would end up inside the same component after the merge. Since every accepted request preserves all restrictions, and rejected requests do not change the structure, the invariant remains true throughout the algorithm.

Python Solution

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))
        rank = [0] * n

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x: int, y: int) -> None:
            root_x = find(x)
            root_y = find(y)

            if root_x == root_y:
                return

            if rank[root_x] < rank[root_y]:
                parent[root_x] = root_y
            elif rank[root_x] > rank[root_y]:
                parent[root_y] = root_x
            else:
                parent[root_y] = root_x
                rank[root_x] += 1

        result = []

        for u, v in requests:
            root_u = find(u)
            root_v = find(v)

            if root_u == root_v:
                result.append(True)
                continue

            can_merge = True

            for x, y in restrictions:
                root_x = find(x)
                root_y = find(y)

                violates = (
                    (root_x == root_u and root_y == root_v)
                    or
                    (root_x == root_v and root_y == root_u)
                )

                if violates:
                    can_merge = False
                    break

            if can_merge:
                union(u, v)
                result.append(True)
            else:
                result.append(False)

        return result

The implementation begins by initializing the Union-Find structure. Each person initially belongs to their own component, so parent[i] = i.

The find function performs path compression. This optimization flattens the structure of the tree whenever a lookup occurs, making future operations faster.

The union function merges two components using union by rank. Smaller trees are attached under larger ones to keep the structure shallow.

For every request, we first determine whether both people are already connected. If they are, the request is automatically accepted because it introduces no new connectivity.

Otherwise, we scan every restriction pair. We check whether one restricted person belongs to the first component and the other belongs to the second component. If so, merging the components would violate the restriction.

If no restriction blocks the merge, we perform the union and accept the request.

Go Solution

package main

func friendRequests(n int, restrictions [][]int, requests [][]int) []bool {
	parent := make([]int, n)
	rank := make([]int, n)

	for i := 0; i < n; i++ {
		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]
	}

	union := func(x, y int) {
		rootX := find(x)
		rootY := find(y)

		if rootX == rootY {
			return
		}

		if rank[rootX] < rank[rootY] {
			parent[rootX] = rootY
		} else if rank[rootX] > rank[rootY] {
			parent[rootY] = rootX
		} else {
			parent[rootY] = rootX
			rank[rootX]++
		}
	}

	result := make([]bool, 0, len(requests))

	for _, request := range requests {
		u := request[0]
		v := request[1]

		rootU := find(u)
		rootV := find(v)

		if rootU == rootV {
			result = append(result, true)
			continue
		}

		canMerge := true

		for _, restriction := range restrictions {
			x := restriction[0]
			y := restriction[1]

			rootX := find(x)
			rootY := find(y)

			violates := (rootX == rootU && rootY == rootV) ||
				(rootX == rootV && rootY == rootU)

			if violates {
				canMerge = false
				break
			}
		}

		if canMerge {
			union(u, v)
			result = append(result, true)
		} else {
			result = append(result, false)
		}
	}

	return result
}

The Go implementation follows the same logic as the Python version. Slices are used for the parent, rank, and result arrays.

Go does not support nested named functions in the same way as Python, so find is declared as a function variable before assignment to allow recursion.

The implementation uses path compression and union by rank exactly as in Python. Since all values fit comfortably within standard integer ranges, overflow is not a concern.

Worked Examples

Example 1

Input:

n = 3
restrictions = [[0,1]]
requests = [[0,2],[2,1]]

Initial state:

Person Parent
0 0
1 1
2 2

Request 1: [0, 2]

Current components:

  • {0}
  • {1}
  • {2}

Restriction check:

  • Restriction [0,1]
  • Merging {0} and {2} does not connect 0 with 1

Accept request.

After union:

Component Members
A {0,2}
B {1}

Result so far:

[true]

Request 2: [2, 1]

Current components:

  • {0,2}
  • {1}

Restriction check:

  • Restriction [0,1]
  • 0 belongs to {0,2}
  • 1 belongs to {1}

Merging these components would connect restricted people.

Reject request.

Final result:

[true, false]

Example 2

Input:

n = 3
restrictions = [[0,1]]
requests = [[1,2],[0,2]]

Request 1: [1, 2]

Components before merge:

  • {0}
  • {1}
  • {2}

No restriction violated.

Accept.

Components after merge:

  • {0}
  • {1,2}

Result:

[true]

Request 2: [0, 2]

Current components:

  • {0}
  • {1,2}

Restriction [0,1] would become violated because 1 belongs to {1,2}.

Reject request.

Final result:

[true, false]

Example 3

Input:

n = 5
restrictions = [[0,1],[1,2],[2,3]]
requests = [[0,4],[1,2],[3,1],[3,4]]

Request 1: [0,4]

No restrictions violated.

Components:

  • {0,4}
  • {1}
  • {2}
  • {3}

Result:

[true]

Request 2: [1,2]

Direct restriction [1,2] exists.

Reject request.

Components unchanged.

Result:

[true, false]

Request 3: [3,1]

Restriction checks:

  • [0,1] does not apply
  • [1,2] does not apply
  • [2,3] does not apply

Accept request.

Components:

  • {0,4}
  • {1,3}
  • {2}

Result:

[true, false, true]

Request 4: [3,4]

Would merge:

  • {1,3}
  • {0,4}

Restriction [0,1] would become violated.

Reject request.

Final result:

[true, false, true, false]

Complexity Analysis

Measure Complexity Explanation
Time O(Q × R × α(N)) Each request scans all restrictions, Union-Find operations are nearly constant
Space O(N) Parent and rank arrays store one entry per node

The dominant cost comes from scanning every restriction for every request. Since each find operation is effectively constant due to path compression and union by rank, the overall complexity is very manageable for the given constraints.

Test Cases

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))
        rank = [0] * n

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x: int, y: int) -> None:
            root_x = find(x)
            root_y = find(y)

            if root_x == root_y:
                return

            if rank[root_x] < rank[root_y]:
                parent[root_x] = root_y
            elif rank[root_x] > rank[root_y]:
                parent[root_y] = root_x
            else:
                parent[root_y] = root_x
                rank[root_x] += 1

        result = []

        for u, v in requests:
            root_u = find(u)
            root_v = find(v)

            if root_u == root_v:
                result.append(True)
                continue

            can_merge = True

            for x, y in restrictions:
                root_x = find(x)
                root_y = find(y)

                violates = (
                    (root_x == root_u and root_y == root_v)
                    or
                    (root_x == root_v and root_y == root_u)
                )

                if violates:
                    can_merge = False
                    break

            if can_merge:
                union(u, v)
                result.append(True)
            else:
                result.append(False)

        return result

solution = Solution()

# Example 1
assert solution.friendRequests(
    3,
    [[0, 1]],
    [[0, 2], [2, 1]]
) == [True, False]  # indirect restriction violation

# Example 2
assert solution.friendRequests(
    3,
    [[0, 1]],
    [[1, 2], [0, 2]]
) == [True, False]  # another indirect restriction case

# Example 3
assert solution.friendRequests(
    5,
    [[0, 1], [1, 2], [2, 3]],
    [[0, 4], [1, 2], [3, 1], [3, 4]]
) == [True, False, True, False]  # multiple restrictions

# No restrictions at all
assert solution.friendRequests(
    4,
    [],
    [[0, 1], [1, 2], [2, 3]]
) == [True, True, True]  # all requests accepted

# Already connected request
assert solution.friendRequests(
    3,
    [[0, 2]],
    [[0, 1], [1, 0]]
) == [True, True]  # second request changes nothing

# Direct restriction
assert solution.friendRequests(
    2,
    [[0, 1]],
    [[0, 1]]
) == [False]  # immediate rejection

# Chain merge causing violation
assert solution.friendRequests(
    4,
    [[0, 3]],
    [[0, 1], [1, 2], [2, 3]]
) == [True, True, False]  # final merge violates restriction

# Multiple independent groups
assert solution.friendRequests(
    6,
    [[0, 5], [1, 4]],
    [[0, 1], [2, 3], [1, 2], [4, 5]]
) == [True, True, True, False]  # final merge invalid

# Minimal valid input
assert solution.friendRequests(
    2,
    [],
    [[0, 1]]
) == [True]  # smallest non-trivial case
Test Why
Example 1 Validates indirect restriction detection
Example 2 Confirms order-sensitive processing
Example 3 Tests multiple restrictions and merges
No restrictions Ensures all requests succeed when unrestricted
Already connected request Verifies repeated friendship requests remain valid
Direct restriction Tests immediate rejection
Chain merge causing violation Validates transitive connectivity handling
Multiple independent groups Tests complex component merging
Minimal valid input Confirms smallest valid configuration works

Edge Cases

One important edge case occurs when two people are already connected before the request arrives. A naive implementation might unnecessarily recheck restrictions or accidentally reject the request. In this problem, such a request must always succeed because it introduces no new connectivity. The implementation handles this by checking whether both users already share the same root before scanning restrictions.

Another critical edge case involves indirect restriction violations. Two restricted people may not be directly connected, but a sequence of accepted requests can eventually place them into the same component. A graph-based mental model helps illustrate this. For example, if 0 is connected to 2, and later 2 connects to 1, then 0 and 1 become indirectly connected. The Union-Find structure correctly captures this because all members of a connected component share the same root.

A third edge case involves rejected requests. When a request violates a restriction, the friendship network must remain unchanged. A buggy implementation might partially modify the Union-Find structure before realizing the request is invalid. This implementation avoids that issue by performing all restriction checks before calling union.

Another subtle case is multiple restrictions involving the same components. A single merge can simultaneously violate several restrictions. The implementation scans every restriction before merging, guaranteeing that any invalid merge is detected before the structure changes.