LeetCode 825: Friends Of Appropriate Ages

Problem Restatement

We are given an array ages, where ages[i] is the age of the ith person.

A person x will not send a friend request to person y if x == y, or if any of these conditions is true:

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

Otherwise, x sends a friend request to y.

Requests are directed. If x sends a request to y, that does not mean y sends one back.

Return the total number of friend requests. The constraints are 1 <= ages.length <= 2 * 10^4 and 1 <= ages[i] <= 120.

Input and Output

Examples

Example 1:

ages = [16, 16]

Each person can send a request to the other person.

The answer is:

2

Example 2:

ages = [16, 17, 18]

Valid requests are:

17 -> 16
18 -> 17

The answer is:

2

Example 3:

ages = [20, 30, 100, 110, 120]

Valid requests are:

110 -> 100
120 -> 110
120 -> 100

The answer is:

3

First Thought: Check Every Pair

A direct approach is to check every ordered pair of people.

For each pair (x, y):

1. Skip if x == y.
2. Apply the three blocking rules.
3. Count the request if none of the rules blocks it.

This is correct, but it costs:

O(n^2)

With up to 2 * 10^4 people, this can be too slow.

Key Insight

Ages are small. Every age is between 1 and 120.

So instead of comparing people one by one, we can count how many people have each age.

For a sender age x, the receiver age y must satisfy:

y > 0.5 * x + 7
y <= x

The third rule:

y > 100 and x < 100

is already covered by y > x, because if x < 100 and y > 100, then y > x.

So for each sender age x, all valid receiver ages are in this range:

floor(0.5 * x + 7) + 1 <= y <= x

We can use prefix sums over age counts to count how many possible receivers are in that range.

Algorithm

Build a count array:

count[age] = number of people with this age

Build a prefix sum array:

prefix[age] = number of people with age <= age

For each possible sender age x from 1 to 120:

1. If count[x] == 0, skip it.
2. Compute the smallest blocked boundary:

low = x // 2 + 7

3. The number of people with valid receiver ages is:

prefix[x] - prefix[low]

4. Each sender of age x cannot send to themself, so subtract 1 for each sender:

count[x] * (valid_receivers - 1)

Add this to the answer.

Correctness

For a person of age x, the first blocking rule excludes every receiver age y where:

y <= 0.5 * x + 7

Since ages are integers, this means valid receiver ages must be greater than:

x // 2 + 7

The second blocking rule excludes every receiver older than x, so valid receiver ages must be at most x.

Therefore, the valid receiver age range for a sender age x is exactly:

x // 2 + 8 through x

The prefix sum expression prefix[x] - prefix[x // 2 + 7] counts all people whose ages are in that range.

This count includes the sender themself, because their own age x is in the valid range whenever the range is non-empty. Since a person cannot send a request to themself, each sender has valid_receivers - 1 possible receivers.

There are count[x] senders of age x, so the contribution from age x is:

count[x] * (valid_receivers - 1)

Summing this over all sender ages counts every valid directed friend request exactly once.

Complexity

Since 120 is constant, this is effectively linear in the input size.

Implementation

class Solution:
    def numFriendRequests(self, ages: list[int]) -> int:
        count = [0] * 121

        for age in ages:
            count[age] += 1

        prefix = [0] * 121

        for age in range(1, 121):
            prefix[age] = prefix[age - 1] + count[age]

        answer = 0

        for age in range(1, 121):
            if count[age] == 0:
                continue

            low = age // 2 + 7
            valid_receivers = prefix[age] - prefix[low]

            if valid_receivers <= 1:
                continue

            answer += count[age] * (valid_receivers - 1)

        return answer

Code Explanation

The count array stores how many people have each age:

count = [0] * 121

The maximum age is 120, so indices 0 through 120 are enough.

We fill the count array:

for age in ages:
    count[age] += 1

Then we build prefix sums:

prefix[age] = prefix[age - 1] + count[age]

This lets us count people in an age interval quickly.

For each sender age, compute the lower blocked boundary:

low = age // 2 + 7

Valid receiver ages are greater than low and at most age, so:

valid_receivers = prefix[age] - prefix[low]

Each sender must exclude themself:

answer += count[age] * (valid_receivers - 1)

Testing

def run_tests():
    s = Solution()

    assert s.numFriendRequests([16, 16]) == 2
    assert s.numFriendRequests([16, 17, 18]) == 2
    assert s.numFriendRequests([20, 30, 100, 110, 120]) == 3
    assert s.numFriendRequests([14, 14, 14]) == 0
    assert s.numFriendRequests([101, 101, 102]) == 2
    assert s.numFriendRequests([120, 120, 120]) == 6

    print("all tests passed")

run_tests()