Friends Of Appropriate Ages - Solution & Explanation

Problem Overview: You receive an array where ages[i] represents a person's age. A person A can send a friend request to B only if specific age constraints are satisfied. The task is to count how many valid friend requests are sent across the entire group. The challenge is avoiding unnecessary pair checks when the input size grows.

Approach 1: Brute Force Pair Checking (Time: O(n²), Space: O(1))

Iterate through every pair of people using two nested loops. For each pair (i, j), verify the three rules: age[j] > 0.5 * age[i] + 7, age[j] <= age[i], and the special constraint involving ages above 100. If the conditions pass, count the request. This approach directly models the problem logic and is easy to implement, but it performs a comparison for every pair. With up to thousands of people, the O(n²) time complexity becomes expensive. It works well only for small inputs or when validating the rules during initial problem exploration using basic array traversal.

Approach 2: Optimized Counting with Age Frequency (Time: O(n + A²), Space: O(A))

Instead of checking every pair of individuals, count how many people have each age. Since ages range only from 1 to 120, build a frequency array where count[a] stores how many people are age a. Then iterate over all age pairs (ageA, ageB). If the friend request rules allow someone of age ageA to send a request to ageB, add count[ageA] * count[ageB] to the result. When ageA == ageB, subtract self-requests because a person cannot send a request to themselves.

This optimization dramatically reduces work because you evaluate at most 120 × 120 age combinations instead of n² people combinations. The idea relies on grouping values and applying conditions to aggregated counts. You can also improve the constant factor by sorting the ages and using two pointers or binary search to locate valid ranges for each age. All these variants rely on the same insight: friend requests depend only on age ranges, not individual identities.

Recommended for interviews: Interviewers expect you to move beyond the brute force check quickly. Starting with the O(n²) approach shows you understand the request rules. The optimized counting or sorted two-pointer method demonstrates algorithmic thinking and reduces the complexity to roughly O(n + A²) (with A = 120) or near-linear time after sorting. That improvement is the key signal of strong problem-solving skill.