Problem Description

You are given an array ages representing the ages of n people on a social media website. You need to determine the total number of friend requests that will be made based on specific rules.

A person x will send a friend request to person y (where x != y) only if ALL of the following conditions are false:

• age[y] <= 0.5 * age[x] + 7
• age[y] > age[x]
• age[y] > 100 && age[x] < 100

In other words, person x will send a request to person y if:

• age[y] > 0.5 * age[x] + 7 AND
• age[y] <= age[x] AND
• NOT (age[y] > 100 && age[x] < 100)

Important notes:

• Friend requests are one-directional. If x sends a request to y, it doesn't mean y will send a request back to x.
• A person cannot send a friend request to themselves.
• You need to count all possible friend requests that will be made across all people.

For example, if person A (age 16) and person B (age 15) exist:

• Person A checks if they can send to B: 15 > 0.5 * 16 + 7 = 15? No, so A won't send to B.
• Person B checks if they can send to A: 16 > 0.5 * 15 + 7 = 14.5? Yes. 16 <= 15? No, so B won't send to A.

The solution uses a counting approach where it tracks the frequency of each age (since ages are limited to 1-120), then checks all possible age pairs to calculate the total number of friend requests based on the given conditions.

Intuition

The key insight is that we don't need to check every individual person against every other person, which would be O(n²). Instead, we can group people by their ages since the friend request rules only depend on ages, not on individual identities.

Think about it this way: if there are 5 people aged 20 and 3 people aged 18, any person aged 20 will have the same relationship with any person aged 18 based on the rules. So instead of checking 5 × 3 = 15 individual pairs, we can check the age pair (20, 18) once and multiply by the counts.

Since ages are limited to a small range (1-120), we can use a frequency array cnt where cnt[age] represents how many people have that specific age. This transforms our problem from "checking n people" to "checking at most 121 distinct ages".

For each age pair (ax, ay):

• If the ages satisfy the friend request conditions, we know that every person of age ax will send a request to every person of age ay
• If ax == ay (same age group), each person sends requests to others in the same group, giving us cnt[ax] * (cnt[ax] - 1) requests (subtract 1 because you can't send to yourself)
• If ax != ay (different ages), we get cnt[ax] * cnt[ay] requests

This reduces the time complexity from O(n²) to O(121²), which is effectively O(1) since 121 is a constant. The space-time tradeoff of using a counting array makes the solution much more efficient when dealing with many people but limited age values.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The implementation uses a counting approach with enumeration to efficiently solve the problem.

Step 1: Count the frequency of each age

We create a frequency array cnt of size 121 (to cover ages 0-120):

cnt = [0] * 121
for x in ages:
    cnt[x] += 1

This allows us to group people by their ages, where cnt[i] represents the number of people with age i.

Step 2: Enumerate all possible age pairs

We iterate through all possible combinations of ages using nested loops:

for ax, x in enumerate(cnt):
    for ay, y in enumerate(cnt):

Here:

• ax and ay represent the ages being compared
• x and y represent the count of people with ages ax and ay respectively

Step 3: Check friend request conditions

For each age pair (ax, ay), we check if person of age ax can send a friend request to person of age ay. The condition for sending a request is the negation of the three blocking conditions:

if not (ay <= 0.5 * ax + 7 or ay > ax or (ay > 100 and ax < 100)):

Step 4: Calculate the number of friend requests

If the conditions are satisfied:

• When ax == ay (same age): Each person sends requests to all others in the same age group except themselves, contributing x * (x - 1) requests
• When ax != ay (different ages): Each person of age ax sends to each person of age ay, contributing x * y requests

This is handled by the formula:

ans += x * (y - int(ax == ay))

The expression (y - int(ax == ay)) elegantly handles both cases:

• If ax == ay, it becomes y - 1, accounting for not sending to oneself
• If ax != ay, it remains y

Time Complexity: O(121²) = O(1) since we iterate through a fixed range of ages
Space Complexity: O(121) = O(1) for the counting array

Example Walkthrough

Let's walk through a small example with ages = [16, 16, 16, 17, 19].

Step 1: Build frequency array First, we count how many people have each age:

• Age 16: 3 people
• Age 17: 1 person
• Age 19: 1 person
• All other ages: 0 people

So cnt[16] = 3, cnt[17] = 1, cnt[19] = 1, and all other entries are 0.

Step 2: Check all age pairs

Now we check each non-zero age pair to see if friend requests can be made:

Age 16 → Age 16:

• Check conditions: 16 > 0.5 * 16 + 7 = 15? Yes ✓
• 16 <= 16? Yes ✓
• Not (16 > 100 && 16 < 100)? Yes ✓
• All conditions pass! Each 16-year-old sends to other 16-year-olds
• Requests: 3 * (3 - 1) = 6 (each of 3 people sends to 2 others)

Age 16 → Age 17:

• Check: 17 > 0.5 * 16 + 7 = 15? Yes ✓
• 17 <= 16? No ✗
• Conditions fail, no requests

Age 17 → Age 16:

• Check: 16 > 0.5 * 17 + 7 = 15.5? Yes ✓
• 16 <= 17? Yes ✓
• Not (16 > 100 && 17 < 100)? Yes ✓
• All conditions pass!
• Requests: 1 * 3 = 3 (the one 17-year-old sends to all three 16-year-olds)

Age 19 → Age 16:

• Check: 16 > 0.5 * 19 + 7 = 16.5? No ✗
• Conditions fail, no requests

Age 19 → Age 17:

• Check: 17 > 0.5 * 19 + 7 = 16.5? Yes ✓
• 17 <= 19? Yes ✓
• Not (17 > 100 && 19 < 100)? Yes ✓
• All conditions pass!
• Requests: 1 * 1 = 1 (the 19-year-old sends to the 17-year-old)

Step 3: Sum up all requests Total friend requests = 6 + 3 + 1 = 10

The key insight is that instead of checking all 5 × 4 = 20 person-to-person combinations, we only checked the unique age pairs and multiplied by their frequencies, making the solution much more efficient.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m²), where n is the length of the array ages and m is the maximum possible age value (121 in this problem).

• The first loop iterates through all n elements in the ages array to count the frequency of each age, contributing O(n).
• The nested loops iterate through all possible age pairs, where both loops run from 0 to 120 (inclusive), resulting in O(m²) = O(121²) iterations.
• Inside the nested loops, all operations (condition checking and arithmetic) are O(1).
• Therefore, the total time complexity is O(n + m²).

Space Complexity: O(m), where m is the maximum possible age value (121).

• The cnt array has a fixed size of 121 elements regardless of the input size, requiring O(121) = O(m) space.
• All other variables (ans, ax, ay, x, y) use constant space O(1).
• Therefore, the total space complexity is O(m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Friend Request Logic

Pitfall: The most common mistake is misinterpreting the condition logic. The problem states that person x will send a request if ALL three conditions are FALSE. Many developers incorrectly implement this as checking if ANY condition is true to block the request.

Incorrect Implementation:

# Wrong: Using OR logic when we need AND logic for blocking
if ay <= 0.5 * ax + 7 or ay > ax or (ay > 100 and ax < 100):
    continue  # Skip if ANY condition blocks the request

Correct Understanding: The request is sent when ALL blocking conditions are false, which means we need to check the negation of each condition. The request happens when:

• age_y > 0.5 * age_x + 7 (NOT less than or equal)
• age_y <= age_x (NOT greater than)
• NOT (age_y > 100 AND age_x < 100)

2. Handling Same-Age Friend Requests Incorrectly

Pitfall: When two people have the same age, forgetting that a person cannot send a friend request to themselves leads to overcounting.

Incorrect Implementation:

if age_x == age_y:
    # Wrong: This counts self-requests
    total_requests += age_count[age_x] * age_count[age_y]

Correct Implementation:

if age_x == age_y:
    # Correct: Subtract 1 to exclude self-requests
    total_requests += age_count[age_x] * (age_count[age_y] - 1)

3. Double-Counting Friend Requests

Pitfall: Some developers mistakenly think they need to divide the result by 2, assuming bidirectional counting.

Why This is Wrong: Friend requests are directional. If person A can send to person B, it doesn't mean B can send to A. Each valid request should be counted exactly once. The algorithm already handles this correctly by checking each ordered pair (x, y) separately.

4. Inefficient Brute Force Implementation

Pitfall: Implementing a naive O(n²) solution that compares every person with every other person directly.

Inefficient Approach:

def numFriendRequests(self, ages: List[int]) -> int:
    n = len(ages)
    total = 0
    for i in range(n):
        for j in range(n):
            if i != j:
                # Check conditions for ages[i] sending to ages[j]
                if ages[j] > 0.5 * ages[i] + 7 and ages[j] <= ages[i]:
                    if not (ages[j] > 100 and ages[i] < 100):
                        total += 1
    return total

Better Solution: Use the counting approach shown in the original solution, which groups people by age and processes age pairs rather than individual pairs, reducing time complexity when many people share the same age.

5. Edge Case: Very Young Ages

Pitfall: Not recognizing that very young ages (typically under 15) cannot send friend requests to anyone due to the 0.5 * age + 7 condition.

Example: For age 14: 0.5 * 14 + 7 = 14, meaning they can only send requests to people older than 14, but the second condition requires age_y <= 14. These constraints are contradictory, so age 14 cannot send any requests.

Solution: The algorithm handles this naturally, but understanding this helps with debugging and test case creation. You can add an optimization to skip processing ages below 15 as senders:

for age_x in range(15, 121):  # Start from 15 instead of 0
    if age_count[age_x] == 0:
        continue