Process Restricted Friend Requests Solution in C++

Problem Description

Ah, the classic dilemma of modern social life: how to navigate the treacherous waters of friend requests while adhering to the strictest of social restrictions. Imagine you’re at a party, and you want to befriend someone, but your best friend has a strict “no friends of friends” policy. What do you do? Well, that’s exactly what this problem is about!

In the LeetCode problem “Process Restricted Friend Requests,” you are given a number of people (let’s say n), a list of restrictions (because who doesn’t love a good rule?), and a list of friend requests. Your task is to determine whether each friend request can be accepted without violating any restrictions.

So, if you think you can just send friend requests willy-nilly, think again! You need to check if accepting a request would break any of the social rules laid out by the restrictions.

Code Solution


class UnionFind {
 public:
  UnionFind(int n) : id(n), rank(n) {
    iota(id.begin(), id.end(), 0);
  }

  void unionByRank(int u, int v) {
    const int i = find(u);
    const int j = find(v);
    if (i == j)
      return;
    if (rank[i] < rank[j]) {
      id[i] = j;
    } else if (rank[i] > rank[j]) {
      id[j] = i;
    } else {
      id[i] = j;
      ++rank[j];
    }
  }

  int find(int u) {
    return id[u] == u ? u : id[u] = find(id[u]);
  }

 private:
  vector id;
  vector rank;
};

class Solution {
 public:
  vector friendRequests(int n, vector>& restrictions,
                              vector>& requests) {
    vector ans;
    UnionFind uf(n);

    for (const vector& request : requests) {
      const int i = uf.find(request[0]);
      const int j = uf.find(request[1]);
      bool isValid = true;
      if (i != j)
        for (const vector& restriction : restrictions) {
          const int x = uf.find(restriction[0]);
          const int y = uf.find(restriction[1]);
          if (i == x && j == y || i == y && j == x) {
            isValid = false;
            break;
          }
        }
      ans.push_back(isValid);
      if (isValid)
        uf.unionByRank(i, j);
    }

    return ans;
  }
};

Approach

The solution employs a Union-Find (or Disjoint Set Union) data structure to efficiently manage and merge groups of friends. Each person starts as their own group, and as friend requests are processed, the groups are merged based on the requests, provided they don’t violate any restrictions.

Initialization: Each person is their own parent in the Union-Find structure.
Processing Requests: For each friend request, the algorithm checks if the two individuals belong to the same group. If they don’t, it checks against the restrictions.
Union Operation: If the request is valid, the two individuals are merged into the same group.

Time and Space Complexity

Time Complexity: The time complexity is approximately O(m * r), where m is the number of requests and r is the number of restrictions. This is due to the nested loops checking each request against all restrictions.

Space Complexity: The space complexity is O(n) for storing the parent and rank arrays in the Union-Find structure.

Real-World Example

Imagine you’re at a high school reunion. You want to reconnect with an old friend, but your other friend, who has a long-standing feud with them, has made it clear that they don’t want to see them. This is exactly the kind of situation the “Process Restricted Friend Requests” problem simulates. You have to navigate these social waters carefully, ensuring you don’t upset the delicate balance of friendships.