Friends Of Appropriate Ages

MEDIUM

Description

There are n persons on a social media website. You are given an integer array ages where ages[i] is the age of the i^th 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 * 10⁴
1 <= ages[i] <= 120

Approaches

Checkout 3 different approaches to solve Friends Of Appropriate Ages. Click on different approaches to view the approach and algorithm in detail.

Brute Force

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 totalRequests to 0.
Use a nested loop to iterate through every possible pair of distinct people, x (outer loop, index i) and y (inner loop, index j).
For each pair, let ageX = ages[i] and ageY = ages[j].
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).
If all conditions for sending a request are true, increment totalRequests.
After iterating through all pairs, return totalRequests.

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 Analysis

Time Complexity: O(N^2), where N is the number of people. We have two nested loops, each iterating up to N times.Space Complexity: O(1), as we only use a few variables to store the counts and loop indices.

Pros and Cons

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

Code Solutions

Checking out 3 solutions in different languages for Friends Of Appropriate Ages. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Friends Of Appropriate Ages

Algorithms:

Binary SearchSorting

Patterns:

Two Pointers

Data Structures:

Array