Scale Engineer

Friends Of Appropriate Ages

Med
#0779Time: 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.
Patterns
Two Pointers
Algorithms
Binary SearchSorting
Data structures
Array

Prompt

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] + 7
  • age[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.length
  • 1 <= n <= 2 * 104
  • 1 <= 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

  1. Initialize a variable totalRequests to 0.
  2. Use a nested loop to iterate through every possible pair of distinct people, x (outer loop, index i) and y (inner loop, index j).
  3. For each pair, let ageX = ages[i] and ageY = ages[j].
  4. Check if person x will send a friend request to person y by verifying that none of the blocking conditions are met:
    • ageY > 0.5 * ageX + 7
    • ageY <= ageX
    • !(ageY > 100 && ageX < 100) (This condition is actually redundant given the second one).
  5. If all conditions for sending a request are true, increment totalRequests.
  6. 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).

Solutions

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;  }}

Video 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.

← Previous

Previous problem

Next →

Next problem