Friends Of Appropriate Ages
MedPrompt
There are n persons on a social media website. You are given an integer array ages where ages[i] is the age of the ith person.
A Person x will not send a friend request to a person y (x != y) if any of the following conditions is true:
age[y] <= 0.5 * age[x] + 7age[y] > age[x]age[y] > 100 && age[x] < 100
Otherwise, x will send a friend request to y.
Note that if x sends a request to y, y will not necessarily send a request to x. Also, a person will not send a friend request to themself.
Return the total number of friend requests made.
Example 1:
Input: ages = [16,16]
Output: 2
Explanation: 2 people friend request each other.Example 2:
Input: ages = [16,17,18]
Output: 2
Explanation: Friend requests are made 17 -> 16, 18 -> 17.Example 3:
Input: ages = [20,30,100,110,120]
Output: 3
Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.
Constraints:
n == ages.length1 <= n <= 2 * 1041 <= ages[i] <= 120
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to simulate the process directly. We can consider every possible pair of people (x, y) where x is the sender and y is the potential recipient. For each pair, we check if the three conditions for sending a friend request are satisfied. If they are, we increment a counter. This involves a nested loop over the ages array.
Algorithm
- Initialize a variable
totalRequeststo 0. - Use a nested loop to iterate through every possible pair of distinct people,
x(outer loop, indexi) andy(inner loop, indexj). - For each pair, let
ageX = ages[i]andageY = ages[j]. - Check if person
xwill send a friend request to personyby verifying that none of the blocking conditions are met:ageY > 0.5 * ageX + 7ageY <= ageX!(ageY > 100 && ageX < 100)(This condition is actually redundant given the second one).
- If all conditions for sending a request are true, increment
totalRequests. - After iterating through all pairs, return
totalRequests.
Walkthrough
This method iterates through each person x and, for each x, iterates through all other people y. For every pair (x, y) where x and y are not the same person, it evaluates the conditions given in the problem statement. A request is sent from x to y if age[y] is not too young (> 0.5 * age[x] + 7) and not older (<= age[x]). The third condition (age[y] > 100 && age[x] < 100) is implicitly handled by the second condition, but we can check it for completeness. If the conditions hold, we count it as one request.
class Solution { public int numFriendRequests(int[] ages) { int n = ages.length; int totalRequests = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) { continue; } if (isRequestSent(ages[i], ages[j])) { totalRequests++; } } } return totalRequests; } private boolean isRequestSent(int ageX, int ageY) { // A request is NOT sent if any of these are true. if (ageY <= 0.5 * ageX + 7) return false; if (ageY > ageX) return false; if (ageY > 100 && ageX < 100) return false; // Otherwise, a request is sent. return true; }}Complexity
Time
O(N^2), where N is the number of people. We have two nested loops, each iterating up to N times.
Space
O(1), as we only use a few variables to store the counts and loop indices.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space besides a counter variable.
Cons
Highly inefficient due to its quadratic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints (N up to 2 * 10^4).
The brute-force approach is slow because for each person, we scan the entire array. We can optimize this by sorting the ages array first. Once sorted, for each person x with ageX, we can efficiently find the number of people y whose age ageY falls into the valid range (0.5 * ageX + 7, ageX]. This can be done using binary search or a two-pointer approach. A two-pointer approach is particularly efficient here.
Algorithm
- Sort the
agesarray in non-decreasing order. - Initialize
totalRequests = 0, and two pointersleft = 0,right = 0. - Iterate through the sorted
agesarray with indexifrom0ton-1. LetageA = ages[i]. - For each
ageA, we need to find the number of peopleageBsuch that0.5 * ageA + 7 < ageB <= ageA. - Advance the
leftpointer to the first index whereages[left] > 0.5 * ageA + 7. - Advance the
rightpointer to the first index whereages[right] > ageA. - The indices from
lefttoright - 1represent all people with a valid age to receive a request from personi. - The total number of such people is
right - left. Since personicannot send a request to themselves, we subtract 1. - Add
right - left - 1tototalRequests, ensuring the count is positive. - The
leftandrightpointers only move forward, so their total movement across all iterations ofiis O(N).
Walkthrough
After sorting the ages array, we can iterate through each person i. For each person i with age ageA = ages[i], we need to count how many other people j have an age ageB in the valid range. We can maintain two pointers, left and right, to define a window of valid ages. As we iterate i through the sorted array, ageA increases, and the valid window (0.5 * ageA + 7, ageA] also slides. The left and right pointers will only ever move forward, making the search for the window bounds very efficient (amortized O(1) for each i). The total number of requests from person i is the size of this window, minus one (for person i themselves).
import java.util.Arrays; class Solution { public int numFriendRequests(int[] ages) { Arrays.sort(ages); int n = ages.length; int totalRequests = 0; int left = 0, right = 0; for (int i = 0; i < n; i++) { int ageA = ages[i]; // People aged 14 or younger cannot send requests if (ageA <= 14) { continue; } // Find the lower bound for recipient's age // ages[left] must be > 0.5 * ageA + 7 while (ages[left] <= 0.5 * ageA + 7) { left++; } // Find the upper bound for recipient's age // ages[right] must be <= ageA while (right < n && ages[right] <= ageA) { right++; } // All people in window [left, right) are valid targets. // The count is (right - 1) - left + 1 = right - left. // We subtract 1 because person i cannot request themselves. if (right > left) { totalRequests += (right - left - 1); } } return totalRequests; }}Complexity
Time
O(N log N). The sorting step takes O(N log N). The subsequent two-pointer scan takes O(N). Thus, the overall complexity is dominated by sorting.
Space
O(log N) or O(N), depending on the implementation of the sorting algorithm used. For example, Java's `Arrays.sort()` for primitives uses a dual-pivot quicksort which has an average space complexity of O(log N).
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Passes the time constraints of the problem.
Cons
The time complexity is dominated by the sorting step.
It can be slightly more complex to implement correctly compared to the brute-force approach, especially handling duplicates.
The most efficient approach leverages the constraint that ages are in a small, fixed range [1, 120]. Instead of considering each person individually, we can group them by age. We first count the number of people of each age. Then, for each pair of ages (ageA, ageB), we can calculate how many requests are sent from the group with ageA to the group with ageB. To make this even faster, we can use a prefix sum array on the age counts to find the number of people in a valid age range in O(1) time.
Algorithm
- Notice that the ages are limited to the range
[1, 120]. Create a frequency arrayageCountsof size 121 to store the count of people for each age. - Populate
ageCountsby iterating through the inputagesarray. This takes O(N) time. - Create a prefix sum array
prefixSumof size 121 fromageCounts.prefixSum[i]will store the total number of people with an age less than or equal toi. This takes O(A) time, where A=120. - Initialize
totalRequests = 0. - Iterate through each possible sender age,
ageA, from 1 to 120. - If
ageCounts[ageA]is 0, there are no senders of this age, so continue. - For each
ageA, calculate the valid range for a recipient's age,ageB. The lower bound islowerBoundAge = 0.5 * ageA + 7and the upper bound isageA. - Use the
prefixSumarray to find the total number of people whose age falls in the range(lowerBoundAge, ageA]. This count isnumTargets = prefixSum[ageA] - prefixSum[lowerBoundAge]. - Each of the
ageCounts[ageA]people will send a request to thesenumTargetspeople, but not to themselves. So, each person sendsnumTargets - 1requests. - Add
ageCounts[ageA] * (numTargets - 1)tototalRequests. - Return
totalRequests.
Walkthrough
This approach avoids sorting and pairwise comparisons of all N people. First, we create a frequency map (an array ageCounts of size 121) to count how many people exist for each age from 1 to 120. Then, we build a prefix sum array prefixSum on top of ageCounts. prefixSum[i] will store the total number of people with age up to i.
With these data structures, we can iterate through each possible age ageA from 1 to 120. For each ageA that exists in our input (ageCounts[ageA] > 0), we determine the valid age range for recipients: (0.5 * ageA + 7, ageA]. Using the prefix sum array, we can find the number of people in this range in constant time. Let this be numTargets. Each of the ageCounts[ageA] people of age ageA will send a request to these numTargets people, excluding themselves. Therefore, the total number of requests from this age group is ageCounts[ageA] * (numTargets - 1). We sum this value over all possible ageA to get the final answer.
class Solution { public int numFriendRequests(int[] ages) { int[] ageCounts = new int[121]; for (int age : ages) { ageCounts[age]++; } int[] prefixSum = new int[121]; prefixSum[0] = ageCounts[0]; for (int i = 1; i <= 120; i++) { prefixSum[i] = prefixSum[i - 1] + ageCounts[i]; } int totalRequests = 0; // People aged 14 or younger cannot send requests. for (int ageA = 15; ageA <= 120; ageA++) { if (ageCounts[ageA] == 0) { continue; } int lowerBoundAge = (int) (0.5 * ageA + 7); // Count of people with age in (lowerBoundAge, ageA] int numTargets = prefixSum[ageA] - prefixSum[lowerBoundAge]; // Each of the ageCounts[ageA] people sends a request to numTargets people. // They don't send to themselves, so they send to (numTargets - 1) people. if (numTargets > 0) { totalRequests += ageCounts[ageA] * (numTargets - 1); } } return totalRequests; }}Complexity
Time
O(N + A), where N is the number of people and A is the range of ages (121). This is the most optimal solution as it's linear in the size of the input.
Space
O(A), where A is the maximum possible age (121). Since A is a constant, this is considered O(1) constant space.
Trade-offs
Pros
Extremely efficient, with a time complexity that is linear in the number of people.
The complexity is independent of N after the initial count, making it very fast for large inputs.
Cons
Requires extra space for the counting and prefix sum arrays.
The logic can be slightly more complex to devise than simpler approaches.
Solutions
Solution
class Solution {public int numFriendRequests(int[] ages) { int[] counter = new int[121]; for (int age : ages) { ++counter[age]; } int ans = 0; for (int i = 1; i < 121; ++i) { int n1 = counter[i]; for (int j = 1; j < 121; ++j) { int n2 = counter[j]; if (!(j <= 0.5 * i + 7 || j > i || (j > 100 && i < 100))) { ans += n1 * n2; if (i == j) { ans -= n2; } } } } return ans; }}class Solution {public: int numFriendRequests(vector<int> &ages) { vector<int> counter(121); for (int age : ages) ++counter[age]; int ans = 0; for (int i = 1; i < 121; ++i) { int n1 = counter[i]; for (int j = 1; j < 121; ++j) { int n2 = counter[j]; if (!(j <= 0.5 * i + 7 || j > i || (j > 100 && i < 100))) { ans += n1 * n2; if (i == j) ans -= n2; } } } return ans; }};class Solution: def numFriendRequests(self, ages: List[int]) -> int: counter = Counter(ages) ans = 0 for i in range(1, 121): n1 = counter[i] for j in range(1, 121): n2 = counter[j] if not (j <= 0.5 * i + 7 or j > i or (j > 100 and i < 100)): ans += n1 * n2 if i == j: ans -= n2 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.