825. Friends Of Appropriate Ages - Detailed Explanation

Problem Statement

You’re given an integer array ages where ages[i] is the age of the iᵗʰ person on a social media site. Person A will not send a friend request to person B (A != B) if any of these holds:

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

Otherwise, A will send a request to B. No one requests themselves, and requests are directed (A→B is different from B→A). Return the total number of requests made.

Example 1
Input: ages = [16,16]
Output: 2
Explanation: Both 16→16.

Example 2
Input: ages = [16,17,18]
Output: 2
Explanation: 17→16, 18→17.

Example 3
Input: ages = [20,30,100,110,120]
Output: 3
Explanation: 110→100, 120→110, 120→100.

Constraints

• 1 ≤ ages.length ≤ 2·10⁴
• 1 ≤ ages[i] ≤ 120

Approach 1: Counting by Age Buckets (O(1) time)

Since ages range only 1…120, we can build a frequency array cnt[121]. Then for each possible age A (1…120) and each possible age B (1…120), if cnt[A]>0 and cnt[B]>0 and the rules allow A→B, we add

• cnt[A] * (cnt[A] − 1) when A==B (everyone of age A can request everyone else of age A)
• cnt[A] * cnt[B] when A≠B.

Why it works

• We consider every age pair exactly once.
• The double loop is fixed 120×120 = 14,400 iterations → O(1) for our constraints.

Approach 2: Sort + Two Pointers (O(n log n))

Sort the ages array. For each index i, let age = ages[i]. We want to count the number of j > i with

ages[j] > 0.5*age + 7
and ages[j] ≤ age

Since sorted, the valid j form a contiguous block [L…R]. We can maintain two pointers:

• L moves right until ages[L] > 0.5*age + 7
• R moves right until ages[R] > age

Then for each i, the number of valid j is max(0, R−L). Sum over all i.

Why it works

• Sorting ensures valid recipients form a window.
• Two pointers over the sorted list yields overall O(n) after the O(n log n) sort.

Complexity Analysis

Python Code