LeetCode 597: Friend Requests I: Overall Acceptance Rate Solution in Python – A Step-by-Step Guide

What Is LeetCode 597: Friend Requests I: Overall Acceptance Rate?

In LeetCode 597: Friend Requests I: Overall Acceptance Rate, you’re given two lists of tuples: friend_requests where each tuple (sender_id, send_to_id) represents a friend request sent from one user to another, and request_accepted where each tuple (requester_id, accepter_id) represents an accepted request. Your task is to return the acceptance rate as a float, calculated as the number of unique accepted requests divided by the number of unique friend requests, rounded to 2 decimal places. If no requests exist, return 0.00. For example, with friend_requests = [(1,2), (1,3), (2,3)] and request_accepted = [(1,2), (2,3)], the result is 0.67 (2/3). This problem builds on LeetCode 349: Intersection of Two Arrays for set operations but focuses on ratio computation from paired data.

Problem Statement

• Input:
• friend_requests (List[Tuple[int, int]])—list of (sender_id, send_to_id).
• request_accepted (List[Tuple[int, int]])—list of (requester_id, accepter_id).
• Output: Float—acceptance rate (accepted/requests), rounded to 2 decimals.
• Rules: Count unique requests and acceptances; return 0.00 if no requests.

Constraints

• 1 <= friend_requests.length <= 10³
• 1 <= request_accepted.length <= 10³
• 1 <= sender_id, send_to_id, requester_id, accepter_id <= 10⁴

Examples

• Input: friend_requests = [(1,2),(1,3),(2,3)], request_accepted = [(1,2),(2,3)]
• Output: 0.67
• Requests: 3 unique, Accepted: 2 unique, 2/3 ≈ 0.67.
• Input: friend_requests = [(1,2),(2,1)], request_accepted = [(1,2)]
• Output: 0.50
• Requests: 2 unique, Accepted: 1 unique, 1/2 = 0.50.
• Input: friend_requests = [], request_accepted = []
• Output: 0.00
• No requests, return 0.00.

Understanding the Problem: Calculating the Rate

To solve LeetCode 597: Friend Requests I: Overall Acceptance Rate in Python, we need to compute the ratio of unique accepted friend requests to unique total friend requests from two lists, handling up to 10³ records efficiently and returning a rounded float. A brute-force approach counting matches by scanning both lists repeatedly could work but is inefficient (O(n*m)). Instead, a set-based counting method processes each list in O(n) time, using sets to deduplicate requests and acceptances, then performs a simple division. We’ll explore:

• Best Solution (Set-Based Counting with Division): O(n) time, O(n) space—fast and optimal (n = total records).
• Alternative Solution (Brute-Force Traversal): O(n*m) time, O(n) space—thorough but slower (m = accepted records).

Let’s dive into the set solution with a friendly breakdown!

Best Solution: Set-Based Counting with Division

Why Sets Win

The set-based counting with division solution is the best for LeetCode 597 because it calculates the acceptance rate in O(n) time and O(n) space by converting both lists to sets to count unique requests and acceptances in a single pass, then dividing efficiently with a simple check for zero requests. It’s like tallying RSVPs and confirmations, counting each unique pair once, and figuring out the attendance rate—all in a quick, organized sweep!

How It Works

Think of this as a friend-request analyst:

• Step 1: Build Sets:
• Convert friend_requests to a set of tuples for unique requests.
• Convert request_accepted to a set for unique acceptances.
• Step 2: Count Uniques:
• Total requests = size of request set.
• Accepted requests = size of acceptance set.
• Step 3: Compute Rate:
• If total requests = 0, return 0.00.
• Else, rate = accepted / total, round to 2 decimals.
• Step 4: Return Result:
• Acceptance rate as float.
• Why It Works:
• Sets deduplicate naturally, ensuring unique counts.
• Single pass per list keeps it efficient.

It’s like an acceptance-rate calculating maestro!

Step-by-Step Example

Example: friend_requests = [(1,2),(1,3),(2,3)], request_accepted = [(1,2),(2,3)]

• Step 1: Build sets:
• Requests set: {(1,2), (1,3), (2,3)}.
• Accepted set: {(1,2), (2,3)}.
• Step 2: Count:
• Total requests = 3.
• Accepted = 2.
• Step 3: Compute rate:
• Rate = 2 / 3 ≈ 0.6667, round to 0.67.
• Step 4: Return 0.67.
• Result: 0.67.

Example: friend_requests = [(1,2),(2,1)], request_accepted = [(1,2)]

• Step 1: Sets:
• Requests: {(1,2), (2,1)}.
• Accepted: {(1,2)}.
• Step 2: Count:
• Total = 2, Accepted = 1.
• Step 3: Rate = 1 / 2 = 0.50.
• Result: 0.50.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

from typing import List, Tuple

class Solution:
    def findAcceptanceRate(self, friend_requests: List[Tuple[int, int]], request_accepted: List[Tuple[int, int]]) -> float:
        # Step 1: Convert lists to sets for unique counts
        total_requests = set(friend_requests)
        accepted_requests = set(request_accepted)

        # Step 2: Get sizes of unique requests and acceptances
        total_count = len(total_requests)
        accepted_count = len(accepted_requests)

        # Step 3: Compute acceptance rate
        if total_count == 0:
            return 0.00
        rate = accepted_count / total_count

        # Step 4: Return rounded result
        return round(rate, 2)

• Lines 6-7: Convert lists to sets to deduplicate requests and acceptances.
• Lines 10-11: Count unique elements in each set.
• Lines 14-17: Compute rate:
• Check for zero requests, return 0.00 if none.
• Divide accepted by total, round to 2 decimals.
• Time Complexity: O(n)—single pass per list to build sets.
• Space Complexity: O(n)—set storage.

It’s like a friend-request rate wizard!

Alternative Solution: Brute-Force Traversal

Why an Alternative Approach?

The brute-force traversal approach counts accepted requests by scanning the acceptance list for each request, running in O(n*m) time (n = requests, m = acceptances) and O(n) space for storing unique requests. It’s thorough but inefficient, making it a good baseline for understanding or when avoiding sets.

How It Works

Picture this as a request-matching seeker:

• Step 1: Get unique requests.
• Step 2: For each request, check if accepted by scanning acceptances.
• Step 3: Compute rate from counts.
• Step 4: Return rounded rate.

It’s like a manual acceptance checker!

Step-by-Step Example

Example: friend_requests = [(1,2),(1,3)], request_accepted = [(1,2)]

• Step 1: Unique requests: {(1,2), (1,3)}.
• Step 2: Check:
• (1,2): Found in acceptances, count = 1.
• (1,3): Not found, count remains 1.
• Step 3: Total = 2, Accepted = 1, Rate = 1/2 = 0.50.
• Result: 0.50.

Code for Brute-Force Approach

from typing import List, Tuple

class Solution:
    def findAcceptanceRate(self, friend_requests: List[Tuple[int, int]], request_accepted: List[Tuple[int, int]]) -> float:
        # Step 1: Get unique requests
        unique_requests = set(friend_requests)
        total_count = len(unique_requests)

        # Step 2: Count accepted requests
        accepted_count = 0
        for req in unique_requests:
            for acc in request_accepted:
                if req == acc:
                    accepted_count += 1
                    break

        # Step 3: Compute rate
        if total_count == 0:
            return 0.00
        rate = accepted_count / total_count

        # Step 4: Return rounded result
        return round(rate, 2)

• Lines 6-7: Deduplicate requests with set.
• Lines 10-15: Count accepted by scanning acceptances for each request.
• Lines 18-21: Compute and round rate.
• Time Complexity: O(n*m)—nested loops.
• Space Complexity: O(n)—set storage.

It’s a brute-force rate tallier!

Comparing the Two Solutions

• Set-Based (Best):
• Pros: O(n), O(n), fast and elegant.
• Cons: Extra space for sets.
• Brute-Force (Alternative):
• Pros: O(n*m), O(n), explicit matching.
• Cons: Slower, less efficient.

Set-based wins for speed!

Additional Examples and Edge Cases

• Empty requests: 0.00.
• All accepted: 1.00.
• No acceptances: 0.00.

Set-based handles them all!

Complexity Recap

• Set-Based: Time O(n), Space O(n).
• Brute-Force: Time O(n*m), Space O(n).

Set-based’s the efficiency champ!

Key Takeaways

• Set-Based: Rate finesse—learn at Python Basics!
• Brute-Force: Scan simplicity.
• Requests: Ratios are fun.
• Python: Sets or loops, your pick!

Final Thoughts: Calculate That Rate!

LeetCode 597: Friend Requests I: Overall Acceptance Rate in Python is a practical data challenge. Set-based counting with division is your fast track, while brute-force offers a thorough dive. Want more? Try LeetCode 349: Intersection of Two Arrays or LeetCode 560: Subarray Sum Equals K. Ready to tally? Head to Solve LeetCode 597 on LeetCode and compute that acceptance rate today!