LeetCode 825 - Friends Of Appropriate Ages

The problem gives us an array ages, where each value represents the age of a person on a social media platform. We must determine how many friend requests are sent between people according to a specific set of rules.

leetcodemediumarraytwo-pointersbinary-searchsorting

LeetCode Problem 825

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Binary Search, Sorting

Solution

Problem Understanding

The problem gives us an array ages, where each value represents the age of a person on a social media platform. We must determine how many friend requests are sent between people according to a specific set of rules.

A person x can send a friend request to person y only if all invalid conditions are false. The request is rejected if any of the following are true:

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

If none of these conditions hold, then x sends a request to y.

The important detail is that friendship requests are directional. If person A can send a request to person B, that does not automatically mean B can send one back. We must count every valid directed request separately.

We are also told that a person cannot send a request to themselves.

The input size is at most 2 * 10^4, which is large enough that checking every pair directly with nested loops becomes expensive. Since the ages are limited to the range 1 to 120, this constraint strongly hints that counting or sorting based optimizations may be useful.

There are several important edge cases to keep in mind:

  • Ages less than 15 can never send requests because 0.5 * age + 7 becomes too restrictive.
  • Multiple people may have the same age, and they can often send requests to each other.
  • Requests are directional, so valid pairs must be counted carefully.
  • The >100 rule looks special, but it is actually already implied by the age[y] > age[x] condition in most cases. Still, it must be respected logically.
  • Duplicate ages can create many valid requests, so counting frequencies efficiently matters.

Approaches

Brute Force Approach

The most straightforward solution is to examine every ordered pair (x, y) where x != y.

For each pair, we directly evaluate the three conditions. If none are true, we increment the answer.

This approach is correct because it literally simulates the problem definition exactly. Every possible directed request is checked individually.

However, the time complexity is too high for larger inputs. With n = 20,000, checking every pair requires approximately 400 million comparisons in the worst case, which is inefficient.

Key Insight for an Optimal Solution

The important observation is that the validity of a request depends only on ages, not on person identities.

Since ages are bounded between 1 and 120, we can sort the array and use binary search or two pointers to efficiently count valid ranges.

For a fixed sender age a, valid recipients must satisfy:

  • recipient_age > 0.5 * a + 7
  • recipient_age <= a

This forms a continuous valid interval after sorting.

Instead of checking every person individually, we can determine how many people fall into the valid range using binary search.

This reduces the complexity dramatically.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Checks every ordered pair directly
Optimal O(n log n) O(1) or O(log n) Sorts ages and uses binary search to count valid ranges efficiently

Algorithm Walkthrough

Optimal Sorting + Binary Search Algorithm

  1. Sort the ages array.

Sorting allows us to efficiently find contiguous valid age ranges for each person. Once sorted, all valid recipients for a sender appear in a continuous segment. 2. Iterate through each person as the sender.

Suppose the current sender age is age. 3. Compute the minimum valid recipient age.

The invalid condition is:

$age_y \leq 0.5 \cdot age_x + 7$

Therefore, valid recipients must satisfy:

$age_y > 0.5 \cdot age_x + 7$

We compute:

lower = 0.5 * age + 7
  1. Use binary search to find the first valid recipient.

Since the array is sorted, we can find the first index whose value is greater than lower. 5. Use binary search to find the last valid recipient.

Valid recipients must also satisfy:

$age_y \leq age_x$

We find the first index greater than age, which gives us the exclusive upper boundary. 6. Count how many people are in the valid interval.

If:

left = first valid index
right = first index greater than age

then:

valid_people = right - left
  1. Exclude the sender themselves.

Since a person cannot send a request to themselves, subtract one:

valid_people - 1
  1. Add the result to the total answer.

Repeat this process for every sender.

Why it works

After sorting, every valid recipient for a sender forms a contiguous range of ages. Binary search correctly finds the boundaries of this range. Because every sender is processed independently and self requests are excluded, every valid directed request is counted exactly once.

Python Solution

from bisect import bisect_right
from typing import List

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        ages.sort()

        total_requests = 0

        for age in ages:
            if age < 15:
                continue

            lower_bound = 0.5 * age + 7

            left = bisect_right(ages, lower_bound)
            right = bisect_right(ages, age)

            total_requests += right - left - 1

        return total_requests

The implementation begins by sorting the ages array. This is essential because binary search only works on sorted data.

For each age, we first skip people younger than 15. Such people can never send valid requests because the lower bound condition becomes impossible to satisfy.

We then compute the minimum acceptable recipient age. Using bisect_right, we locate the first index strictly greater than that threshold.

Another binary search finds the first index greater than the sender's age. This defines the upper boundary of valid recipients.

The number of valid recipients is simply the size of this interval. We subtract one to exclude the sender themselves.

Finally, all valid request counts are accumulated into the result.

Go Solution

package main

import (
	"sort"
)

func numFriendRequests(ages []int) int {
	sort.Ints(ages)

	totalRequests := 0

	for _, age := range ages {
		if age < 15 {
			continue
		}

		lowerBound := float64(age)/2.0 + 7

		left := sort.Search(len(ages), func(i int) bool {
			return float64(ages[i]) > lowerBound
		})

		right := sort.Search(len(ages), func(i int) bool {
			return ages[i] > age
		})

		totalRequests += right - left - 1
	}

	return totalRequests
}

The Go implementation follows the same logic as the Python solution.

Instead of Python's bisect_right, Go uses sort.Search with custom predicates. The first search locates the first valid recipient age greater than the lower bound, while the second search finds the first age strictly greater than the sender age.

Go slices are dynamic views over arrays, so no additional memory allocation is needed beyond sorting.

Integer overflow is not a concern because the maximum possible number of requests is well within Go's integer range.

Worked Examples

Example 1

ages = [16, 16]

After sorting:

[16, 16]
Sender Age Lower Bound Left Index Right Index Valid Count Requests Added
16 15 0 2 2 1
16 15 0 2 2 1

Total requests:

1 + 1 = 2

Example 2

ages = [16, 17, 18]

Sorted array:

[16, 17, 18]
Sender Age Lower Bound Valid Recipients Requests Added
16 15 [16] 0
17 15.5 [16,17] 1
18 16 [17,18] 1

Total:

2

The valid requests are:

17 -> 16
18 -> 17

Example 3

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

Sorted array:

[20,30,100,110,120]
Sender Age Lower Bound Valid Recipients Requests Added
20 17 [20] 0
30 22 [30] 0
100 57 [100] 0
110 62 [100,110] 1
120 67 [100,110,120] 2

Total:

3

Valid requests:

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

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates, each iteration performs binary searches
Space O(1) or O(log n) Depends on sorting implementation details

The sorting step requires O(n log n) time. After sorting, each person performs two binary searches, each costing O(log n). Since this happens for all n people, the total remains O(n log n).

The algorithm uses only a few extra variables beyond the input array. Some sorting implementations use recursive stack space, which may contribute O(log n) auxiliary space.

Test Cases

from typing import List

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        from bisect import bisect_right

        ages.sort()

        total_requests = 0

        for age in ages:
            if age < 15:
                continue

            lower_bound = 0.5 * age + 7

            left = bisect_right(ages, lower_bound)
            right = bisect_right(ages, age)

            total_requests += right - left - 1

        return total_requests

solution = Solution()

assert solution.numFriendRequests([16, 16]) == 2  # identical valid ages
assert solution.numFriendRequests([16, 17, 18]) == 2  # directional requests
assert solution.numFriendRequests([20, 30, 100, 110, 120]) == 3  # mixed ages
assert solution.numFriendRequests([14, 14, 14]) == 0  # nobody under 15 can send requests
assert solution.numFriendRequests([15, 15]) == 2  # smallest valid sending age
assert solution.numFriendRequests([101, 102]) == 1  # older users can request slightly younger users
assert solution.numFriendRequests([120]) == 0  # single person
assert solution.numFriendRequests([16, 16, 16]) == 6  # all pairwise directed requests
assert solution.numFriendRequests([10, 20, 30, 40]) == 1  # only 40 -> 30 works
assert solution.numFriendRequests([99, 100, 101]) == 3  # requests across 100 boundary
Test Why
[16,16] Basic mutual friendship case
[16,17,18] Demonstrates directional behavior
[20,30,100,110,120] Validates larger age gaps
[14,14,14] Ensures under-15 users send no requests
[15,15] Smallest age that can send valid requests
[101,102] Tests ages above 100
[120] Single element edge case
[16,16,16] Large duplicate group
[10,20,30,40] Sparse valid relationships
[99,100,101] Boundary behavior around age 100

Edge Cases

One important edge case is when all users are younger than 15. For example, [14, 14, 14]. A naive implementation might incorrectly count requests between equal ages. However, the condition age[y] <= 0.5 * age[x] + 7 prevents any valid requests from being sent. The implementation handles this efficiently by immediately skipping ages below 15.

Another important case involves many duplicate ages, such as [16, 16, 16]. Every person can send requests to every other person except themselves. Since there are three people, each sends requests to two others, producing 6 total requests. Incorrect handling of duplicates or self counting could easily produce wrong answers. The binary search interval combined with subtracting one correctly handles this situation.

A third edge case occurs around the age 100 boundary. For example, [99, 100, 101]. The special condition about ages above 100 can be confusing. The implementation naturally handles this because recipients must already satisfy recipient_age <= sender_age. Thus, 101 may send to 100, but 99 cannot send to 101. The sorted range logic enforces these rules automatically.