Abstract / Summary

Given a list of ages, count how many pairs are friends based on specific age difference and ratio rules.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 50% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Sorting
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes the total number of possible friend requests in a social-network scenario where each user’s age influences who they can send a request to. The algorithm first aggregates the frequency of each distinct age, then iterates through the original age list, temporarily removing the current user from the frequency map to avoid self-requests. For each user it determines the permissible age interval for a recipient and sums the counts of all ages that fall inside that interval. The final sum is returned as the answer.

Counting Ages

The first phase builds a histogram of ages using a dictionary that defaults missing keys to zero. This allows constant-time updates for each element in the input list.

all = defaultdict(int)
for x in ages:
    all[x] += 1

By storing only the distinct ages and their multiplicities, the algorithm reduces the amount of work needed in later stages, especially when many users share the same age.

Iterating Over Each Person

The main loop walks through the original list so that the order of processing matches the original data. Before evaluating possible recipients, the current user’s count is decremented, effectively removing them from the pool of candidates.

for x in ages:
    all[x] -= 1  # exclude yourself
    ...
    all[x] += 1  # restore count after processing

This temporary exclusion guarantees that a user never sends a request to themselves, while preserving the original frequency distribution for subsequent iterations.

Computing Acceptable Age Range

For a given age x, the algorithm derives the lower bound of acceptable recipient ages using the problem’s rule age[y] > 0.5 * age[x] + 7. The upper bound is simply age[x], because a user cannot send a request to someone older than themselves. The lower bound is stored in a variable named low.

low = 0.5 * x + 7

The comment in the code notes that the third rule of the original problem (which excludes requests from users under 100 to users over 100) is implicitly satisfied by the second rule, so no extra check is required.

Accumulating Results

Within the same iteration, the algorithm scans the keys of the frequency dictionary. For each distinct age y, it checks whether y lies strictly above the computed lower bound and does not exceed x. If the condition holds, the count of users with age y is added to the running total.

for y in all:
    if low < y <= x:
        result += all[y]

Because the dictionary holds aggregated counts, a single addition accounts for all possible recipients of that age, eliminating the need for pairwise comparisons between individual users.

Edge Cases Handled

The code naturally accommodates several boundary situations:

• Ages that are too low to satisfy low < y are ignored, preventing requests from being counted when the lower bound exceeds the candidate’s age.
• When y equals x, the condition y <= x still permits a request, which aligns with the rule that users of the same age may exchange requests as long as the lower bound is satisfied.
• Duplicate ages are correctly managed because the frequency map aggregates them; the decrement-increment pattern ensures that a user does not count themselves but still counts other users of the same age.
• Ages that fall outside the range of any other user’s acceptable interval contribute zero to the result, as the inner loop’s condition filters them out.

Performance Optimizations Observed

The implementation avoids the naïve O(n²) pairwise comparison by leveraging a frequency dictionary. By iterating over distinct ages rather than every individual pair, the inner loop’s work depends on the number of unique ages, which is typically far smaller than the total number of users. The temporary removal of the current user’s count prevents the need for an explicit self-check inside the inner loop, simplifying the condition and reducing overhead. Additionally, the arithmetic calculation of the lower bound is performed once per outer iteration, and the same bound is reused for all inner checks, minimizing redundant computation. The use of defaultdict eliminates explicit existence checks when updating counts, streamlining the histogram construction.

Imagine there is a big party filled with children of all different ages. The goal is to figure out who can send friend requests to whom based on some rules.

First, the code makes a list to count how many children of each age are at the party. It is like having a chart where you write down the number of five year olds, six year olds, and so on.

Next, it looks at each child one by one to see how many friends they can send a request to. It temporarily hides the child currently being looked at so they don't try to send a request to themselves.

The code then uses two special rules to decide if a friend request is okay. The first rule is about age, which says you cannot be friends with someone who is too much younger than you. The rule is that the other person must be older than half of your age plus seven. The second rule is that you cannot be friends with someone who is older than you.

The code checks every other age group against these two rules. If the other age group fits the rules, it adds the number of children in that group to the total count of friend requests. After checking, the child is once again included in the chart so the next child can be checked properly. All these counts are added up until every child has had a turn to be looked at.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java					TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java			Go		TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	black-shadows	C++
	charles-wangkai			Java
	halfrost						Go
	JoshCrozier					JS
	lkwq007		Python
	lzl124631x	C++
	ruoru				Rust
	suxrobGM							C#
	trung-hn		Python
	varunu28			Java
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
lzl124631x	C++
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality