Process Restricted Friend Requests - Practice Coding Problems

Process Restricted Friend Requests - 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, 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.

Input & Output

Example 1 — Basic Restriction Violation

$ Input: n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1],[0,1]]

› Output: [true,false,false]

💡 Note: Request [0,2] is allowed since no restriction. Request [2,1] would connect 0-1 indirectly (through 2), violating restriction. Request [0,1] directly violates restriction.

Example 2 — Already Connected

$ Input: n = 3, restrictions = [[0,1]], requests = [[1,2],[1,2]]

› Output: [true,true]

💡 Note: First request [1,2] is allowed. Second identical request is still successful since 1 and 2 are already friends.

Example 3 — Multiple Components

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

› Output: [true,false,false,false]

💡 Note: [0,4] allowed. [1,2] violates direct restriction. [3,1] violates restriction [1,2] indirectly. [3,4] would connect restricted pairs through component {0,4}.

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

Visualization

Tap to expand

Understanding the Visualization

Input

Network with n=3 people, restriction [0,1], requests [[0,2],[2,1],[0,1]]

Process

Check each request against current connections and restrictions

Output

Return [true,false,false] based on validation

Key Takeaway

🎯 Key Insight: Use Union-Find to efficiently track connected components and validate restrictions before merging

Asked in

G Google 12 f Facebook 8 a Amazon 5

The key insight is using Union-Find to efficiently track connected components while validating that merging components won't violate any restrictions. The optimal approach simulates the union operation to check all restriction pairs before actually performing the merge. Time: O(m × (n + r × α(n))), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with DFS	O(m × (n + e))	O(n + e)	Use DFS to check if two people are already connected before each request
Union-Find with Restriction Validation	O(m × (n + r × α(n)))	O(n)	Use Union-Find to efficiently track connected components and validate restrictions

Brute Force with DFS — Algorithm Steps

Step 1: For each request, use DFS to find all friends of person u
Step 2: Check if person v is already connected to u
Step 3: Check if connecting u and v would violate any restrictions
Step 4: If valid, add the connection to adjacency list

Visualization

Tap to expand

Step-by-Step Walkthrough

Request Processing

Process each friend request in order

DFS Search

Use DFS to find if two people are connected

Restriction Check

Verify new connection doesn't violate restrictions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_N 1000
#define MAX_REQUESTS 1000

typedef struct {
    int adj[MAX_N][MAX_N];
    int degree[MAX_N];
} Graph;

bool dfs(Graph* g, int start, int target, bool* visited, int n) {
    if (start == target) return true;
    visited[start] = true;
    
    for (int i = 0; i < g->degree[start]; i++) {
        int neighbor = g->adj[start][i];
        if (!visited[neighbor]) {
            if (dfs(g, neighbor, target, visited, n)) {
                return true;
            }
        }
    }
    return false;
}

void getComponent(Graph* g, int node, bool* component, int n) {
    bool visited[MAX_N] = {false};
    int stack[MAX_N];
    int top = 0;
    
    stack[top++] = node;
    
    while (top > 0) {
        int curr = stack[--top];
        if (!visited[curr]) {
            visited[curr] = true;
            component[curr] = true;
            
            for (int i = 0; i < g->degree[curr]; i++) {
                int neighbor = g->adj[curr][i];
                if (!visited[neighbor]) {
                    stack[top++] = neighbor;
                }
            }
        }
    }
}

void addEdge(Graph* g, int u, int v) {
    g->adj[u][g->degree[u]++] = v;
    g->adj[v][g->degree[v]++] = u;
}

bool* solution(int n, int restrictionsSize, int** restrictions, int* restrictionsColSize, int requestsSize, int** requests, int* requestsColSize, int* returnSize) {
    Graph g;
    memset(&g, 0, sizeof(g));
    
    bool* result = (bool*)malloc(requestsSize * sizeof(bool));
    *returnSize = requestsSize;
    
    for (int i = 0; i < requestsSize; i++) {
        int u = requests[i][0];
        int v = requests[i][1];
        
        bool visited[MAX_N] = {false};
        if (u == v || dfs(&g, u, v, visited, n)) {
            result[i] = true;
            continue;
        }
        
        bool compU[MAX_N] = {false};
        bool compV[MAX_N] = {false};
        getComponent(&g, u, compU, n);
        getComponent(&g, v, compV, n);
        
        bool valid = true;
        for (int j = 0; j < restrictionsSize; j++) {
            int x = restrictions[j][0];
            int y = restrictions[j][1];
            if ((compU[x] && compV[y]) || (compU[y] && compV[x])) {
                valid = false;
                break;
            }
        }
        
        if (valid) {
            addEdge(&g, u, v);
            result[i] = true;
        } else {
            result[i] = false;
        }
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Parse restrictions
    char line[10000];
    fgets(line, sizeof(line), stdin); // consume newline
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for restrictions
    int restrictionsSize = 0;
    int** restrictions = NULL;
    int* restrictionsColSize = NULL;
    
    // Parse requests  
    fgets(line, sizeof(line), stdin);
    
    int requestsSize = 0;
    int** requests = NULL;
    int* requestsColSize = NULL;
    
    // For demonstration, using sample data
    restrictionsSize = 1;
    restrictions = (int**)malloc(restrictionsSize * sizeof(int*));
    restrictionsColSize = (int*)malloc(restrictionsSize * sizeof(int));
    restrictions[0] = (int*)malloc(2 * sizeof(int));
    restrictions[0][0] = 0; restrictions[0][1] = 1;
    restrictionsColSize[0] = 2;
    
    requestsSize = 3;
    requests = (int**)malloc(requestsSize * sizeof(int*));
    requestsColSize = (int*)malloc(requestsSize * sizeof(int));
    for (int i = 0; i < requestsSize; i++) {
        requests[i] = (int*)malloc(2 * sizeof(int));
        requestsColSize[i] = 2;
    }
    requests[0][0] = 1; requests[0][1] = 2;
    requests[1][0] = 0; requests[1][1] = 2;
    requests[2][0] = 0; requests[2][1] = 1;
    
    int returnSize;
    bool* result = solution(n, restrictionsSize, restrictions, restrictionsColSize, requestsSize, requests, requestsColSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%s", result[i] ? "true" : "false");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × (n + e))

For each of m requests, we do DFS which takes O(n + e) where e is current edges

✓ Linear Growth

Space Complexity

O(n + e)

Adjacency list stores all edges and DFS uses recursion stack

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

427 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler