# LeetCode 825: Friends Of Appropriate Ages ## Problem Restatement We are given an array `ages`, where `ages[i]` is the age of the `i`th person. A person `x` will not send a friend request to person `y` if `x == y`, or if any of these conditions is true: ```python 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: ```python ages = [16, 16] ``` Each person can send a request to the other person. The answer is: ```python 2 ``` Example 2: ```python ages = [16, 17, 18] ``` Valid requests are: ```python 17 -> 16 18 -> 17 ``` The answer is: ```python 2 ``` Example 3: ```python ages = [20, 30, 100, 110, 120] ``` Valid requests are: ```python 110 -> 100 120 -> 110 120 -> 100 ``` The answer is: ```python 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: ```python 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: ```python y > 0.5 * x + 7 y <= x ``` The third rule: ```python 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: ```python 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: ```python count[age] = number of people with this age ``` Build a prefix sum array: ```python 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: ```python low = x // 2 + 7 ``` 3. The number of people with valid receiver ages is: ```python prefix[x] - prefix[low] ``` 4. Each sender of age `x` cannot send to themself, so subtract `1` for each sender: ```python 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: ```python y <= 0.5 * x + 7 ``` Since ages are integers, this means valid receiver ages must be greater than: ```python 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: ```python 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: ```python 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 ```python 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: ```python count = [0] * 121 ``` The maximum age is `120`, so indices `0` through `120` are enough. We fill the count array: ```python for age in ages: count[age] += 1 ``` Then we build prefix sums: ```python 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: ```python low = age // 2 + 7 ``` Valid receiver ages are greater than `low` and at most `age`, so: ```python valid_receivers = prefix[age] - prefix[low] ``` Each sender must exclude themself: ```python answer += count[age] * (valid_receivers - 1) ``` ## Testing ```python 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 |