LeetCode 825: Friends Of Appropriate Ages

A counting solution for computing how many directed friend requests are allowed by age rules.

leetcodearraycountingprefix-sum

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

Item Meaning
Input An integer array ages
Output Total number of directed friend requests
Age range 1 to 120
Self request Not allowed
Direction x -> y and y -> x are counted separately

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
  1. The number of people with valid receiver ages is:
prefix[x] - prefix[low]
  1. 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

Metric Value Why
Time O(n + 120) Count ages, build prefix sums, scan possible ages
Space O(120) Store age counts and prefix sums

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()
Test Why
[16,16] Same-age people can request each other
[16,17,18] Official directed example
[20,30,100,110,120] Official older-age example
[14,14,14] Age too young to pass lower bound
[101,101,102] Checks older ages and self exclusion
[120,120,120] Counts all directed requests among same age