Friend Requests I Overall Acceptance Rate - Leetcode Solution

Problem Statement

You have received friend requests from some people. For each request i, the first element of requests[i] represents the ID of the requester, and the second element represents the ID of the requested person.

Given the total number of people n and the list of requests, return the overall acceptance rate.

The overall acceptance rate is the number of approved friend requests divided by the total number of friend requests. If a request is approved, both the sender and receiver of the request become friends. A person will not approve a friend request if they have reached the maximum number of friends, or if they know the request sender already.

Example:

Input: n = 5, requests = [[0,1],[1,0],[0,2],[2,0],[3,4]] Output: 0.80000 Explanation: 2 out of 5 requests are approved:

• Request 0 -> 1
• Request 1 -> 0 The requests 0 -> 2, 2 -> 0 and 3 -> 4 are not approved.

Solution

The overall acceptance rate is the number of approved friend requests divided by the total number of friend requests. In order to determine the number of approved friend requests, we need to simulate the approval process.

We can start by initializing a 2D array called friends, with n rows and n columns. Each cell (i, j) in this array represents the friendship status between persons i and j. We will set this cell to -1 to indicate that there is no friendship between i and j.

Next, we can iterate over the requests array and update the friendship status for each request. For each request (p1, p2), we will only update the friendship status if both p1 and p2 have not reached their maximum number of friends, and if they are not already friends. If both conditions are met, we will set the friends[p1][p2] = 1 and friends[p2][p1] = 1, indicating that p1 and p2 are now friends.

After processing all the requests, we can calculate the number of approved friend requests by iterating over the friends array and counting the number of cells with a value of 1. Similarly, we can calculate the total number of friend requests by counting the number of cells with a value of -1.

Finally, we can calculate the overall acceptance rate by dividing the number of approved friend requests by the total number of friend requests.

Here is the Python code that implements this solution:

class Solution: def acceptRate(self, n: int, requests: List[List[int]]) -> float: # Initialize friends array friends = [[-1 for _ in range(n)] for _ in range(n)]

    # Process requests
    for p1, p2 in requests:
        if friends[p1][p2] == -1 and p1 != p2:
            if len([f for f in friends[p1] if f == 1]) < 3 and len([f for f in friends[p2] if f == 1]) < 3:
                # Approve request
                friends[p1][p2] = 1
                friends[p2][p1] = 1
    
    # Calculate overall acceptance rate
    approved = sum([sum([1 if f == 1 else 0 for f in row]) for row in friends]) // 2
    total = sum([sum([1 if f == -1 else 0 for f in row]) for row in friends]) // 2
    return approved / total

Time Complexity

The time complexity of this solution is O(n^2), where n is the total number of people. The worst-case scenario is when all pairs of people send friend requests to each other. In this case, we need to process n^2 requests and iterate over the n^2 cells of the friends array.

Space Complexity

The space complexity of this solution is O(n^2), where n is the total number of people. We need to create a 2D array with n rows and n columns to keep track of the friendship status between people.

1