Friends Of Appropriate Ages: Counting Valid Friend Requests

LeetCode Friends Of Appropriate Ages (problem 825) gives you an array of ages. Each person can send a friend request to another person, but there are restrictions. Person A will NOT send a request to person B if any of these conditions is true:

• age[B] <= 0.5 * age[A] + 7
• age[B] > age[A]
• age[B] > 100 && age[A] < 100

Your job: count the total number of friend requests made.

The brute force approach checks every pair of people, which is O(n^2). With up to 20,000 people in the input, that can be slow. The key insight is that ages are bounded between 1 and 120, so you can count frequencies and work with ages directly instead of individual people.

The counting approach

Since ages range from 1 to 120, you can build a frequency array of size 121 where count[a] is the number of people with age a. Then, instead of iterating over all pairs of people, you iterate over all pairs of ages. That is at most 120 * 120 = 14,400 iterations, which is constant time regardless of input size.

For a pair of ages (a, b), person A (age a) sends a request to person B (age b) when all of these hold:

• b > 0.5 * a + 7
• b <= a
• NOT (b > 100 AND a < 100)

The third condition is actually redundant. If b > 100 and a < 100, then b > a, which already violates the second condition. So you only need to check two things: b > 0.5 * a + 7 and b <= a.

Solution

def num_friend_requests(ages: list[int]) -> int:
    count = [0] * 121
    for age in ages:
        count[age] += 1

    requests = 0
    for a in range(15, 121):
        for b in range(15, 121):
            if b <= 0.5 * a + 7:
                continue
            if b > a:
                continue
            if a == b:
                requests += count[a] * (count[a] - 1)
            else:
                requests += count[a] * count[b]

    return requests

The outer loop starts at 15 because no one aged 14 or below can send a request. For each valid pair (a, b), you multiply the counts. When a == b, you use count[a] * (count[a] - 1) because a person cannot send a request to themselves.

Visual walkthrough

Let's trace through the counting approach step by step.

The entire inner loop is checking: for age a, which ages b fall in the range (0.5 * a + 7, a]? If b is in that range, every person of age a sends a request to every person of age b (minus one if they are the same age, to avoid self-requests).

Complexity

Here A = 120 (the age range), so O(A^2) is O(14,400), which is effectively constant. The frequency counting approach is O(n) in practice because the age-pair loop is bounded.

The building blocks

This problem combines two reusable ideas that show up in many counting and frequency problems.

Frequency array reduction

When the values in your input are bounded to a small range, you can replace the input array with a frequency count. Instead of working with individual elements, you work with (value, count) pairs. This reduces the problem size from n (number of elements) to k (number of distinct values). You will see this same technique in problems like Sort Colors, H-Index, and counting sort variants.

Pair counting with multiplicative logic

Once you have frequencies, counting valid pairs becomes a multiplication problem. If there are 3 people of age 20 and 4 people of age 18, and age 20 can send to age 18, that is 3 * 4 = 12 requests. The same-age case requires subtracting self-pairs: count * (count - 1). This multiplicative pattern appears in problems like Two Sum II, 3Sum, and any problem that asks you to count pairs satisfying some condition.

Edge cases

All same age. If everyone is the same age (say 20), the answer is n * (n - 1) because each person sends to every other person of the same age. The formula count[a] * (count[a] - 1) handles this correctly.

All ages 14 or below. No friend requests are possible because the valid range (0.5 * a + 7, a] is empty for a <= 14. The answer is 0.

Ages near the boundary. For age 15, the valid range is (14.5, 15], which only includes age 15 itself. So people aged 15 can only friend other people aged 15.

Mixed ages with the third condition. The condition age[B] > 100 && age[A] < 100 is automatically handled by b <= a. You do not need to check it separately.

From understanding to recall

The counting approach here is not difficult to understand once you see it. The challenge is recalling the technique under pressure. When you see an array of bounded values and a pairwise condition, the frequency array reduction should fire immediately: replace the array with counts, then iterate over the value space instead of the element space.

That pattern does not stick from reading alone. You need to write the frequency array from scratch, set up the double loop, handle the same-value edge case, and verify the boundary conditions. Doing that once is a start. Doing it again three days later, then a week later, is what moves it from "I remember reading about this" to "I can write this in two minutes."

Related posts

• Two Sum - Another problem where a hash-based lookup replaces brute force pair checking
• Contains Duplicate - The simplest frequency and set-based pattern, which is the foundation for counting approaches
• Sort Colors - Uses counting as a first approach before optimizing to a single-pass partition

The frequency counting technique turns a quadratic problem into a linear one by exploiting the bounded value range. That is the core takeaway. Whenever you see small value ranges with large input sizes, ask yourself: can I count frequencies and work with the value space instead of the element space?