Code Implementation

class Solution:
    def numFriendRequests(self, ages):
        count = [0] * 121
        for age in ages:
            count[age] += 1

        res = 0
        for ageA in range(1, 121):
            if count[ageA] == 0:
                continue
            for ageB in range(1, 121):
                if count[ageB] == 0:
                    continue
                if ageB > ageA:
                    continue
                if ageB <= 0.5 * ageA + 7:
                    continue
                if ageB > 100 and ageA < 100:
                    continue
                res += count[ageA] * count[ageB]
                if ageA == ageB:
                    res -= count[ageA]
        return res
      

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        vector<int> count(121, 0);
        for (int age : ages) count[age]++;
        int res = 0;
        for (int ageA = 1; ageA <= 120; ++ageA) {
            if (count[ageA] == 0) continue;
            for (int ageB = 1; ageB <= 120; ++ageB) {
                if (count[ageB] == 0) continue;
                if (ageB > ageA) continue;
                if (ageB <= 0.5 * ageA + 7) continue;
                if (ageB > 100 && ageA < 100) continue;
                res += count[ageA] * count[ageB];
                if (ageA == ageB) res -= count[ageA];
            }
        }
        return res;
    }
};
      

class Solution {
    public int numFriendRequests(int[] ages) {
        int[] count = new int[121];
        for (int age : ages) count[age]++;
        int res = 0;
        for (int ageA = 1; ageA <= 120; ageA++) {
            if (count[ageA] == 0) continue;
            for (int ageB = 1; ageB <= 120; ageB++) {
                if (count[ageB] == 0) continue;
                if (ageB > ageA) continue;
                if (ageB <= 0.5 * ageA + 7) continue;
                if (ageB > 100 && ageA < 100) continue;
                res += count[ageA] * count[ageB];
                if (ageA == ageB) res -= count[ageA];
            }
        }
        return res;
    }
}
      

var numFriendRequests = function(ages) {
    let count = new Array(121).fill(0);
    for (let age of ages) count[age]++;
    let res = 0;
    for (let ageA = 1; ageA <= 120; ageA++) {
        if (count[ageA] === 0) continue;
        for (let ageB = 1; ageB <= 120; ageB++) {
            if (count[ageB] === 0) continue;
            if (ageB > ageA) continue;
            if (ageB <= 0.5 * ageA + 7) continue;
            if (ageB > 100 && ageA < 100) continue;
            res += count[ageA] * count[ageB];
            if (ageA === ageB) res -= count[ageA];
        }
    }
    return res;
};
      

Problem Description

You are given an array ages where each element represents the age of a person in a social network. A person A can send a friend request to person B if and only if all these conditions are met:

• age[B] > 0.5 * age[A] + 7
• age[B] <= age[A]
• age[B] <= 100 or age[A] >= 100

Note that a person cannot send a friend request to themselves. Your task is to return the total number of friend requests made among all people in the list, given the above rules.

Key constraints:

• Each person can send multiple requests, but not to themselves.
• Do not reuse elements for self-requests.
• There is only one valid solution for each input.

Thought Process

At first glance, the problem seems to ask for checking every possible pair of people (A, B) to see if A can send a friend request to B. This brute-force approach would involve two nested loops, which could be slow for large input arrays.

However, we notice that the constraints depend only on the ages of A and B, not on their positions in the array. This suggests that we can group people by age, count how many people are at each age, and then count valid pairs more efficiently.

By shifting from comparing every pair to comparing groups of people with the same age, we can reduce redundant calculations and improve performance.

Solution Approach

Let's break down the optimized solution step by step:

1. Count the number of people at each age:
   • Create a count array where count[age] is the number of people with that age.
   • Since ages are between 1 and 120, we can use a fixed-size array for this.
2. Iterate over all possible pairs of ages (ageA, ageB):
   • For each possible ageA and ageB, check if both counts are nonzero.
   • Apply the friend request rules:
     • ageB <= 0.5 * ageA + 7: skip, not valid.
     • ageB > ageA: skip, as per constraints.
     • ageB > 100 && ageA < 100: skip, as per constraints.
   • If valid, add count[ageA] * count[ageB] to the result.
   • If ageA == ageB, subtract count[ageA] to avoid self-requests.
3. Return the total count as the answer.

This approach leverages the fact that people of the same age are interchangeable for counting, and avoids redundant checks.

Example Walkthrough

Let's say ages = [16, 16, 17, 18].

• Count array:
  • count[16] = 2
  • count[17] = 1
  • count[18] = 1
• Now, we check all pairs (ageA, ageB):
  • For ageA = 16, ageB = 16:
    • 16 > 0.5*16 + 7 = 15 (valid)
    • 16 <= 16 (valid)
    • count[16] * count[16] = 4, but subtract 2 for self-requests, so +2
  • For ageA = 16, ageB = 17:
    • 17 > 16 (invalid, skip)
  • For ageA = 17, ageB = 16:
    • 16 > 0.5*17 + 7 = 15.5 (valid)
    • 16 <= 17 (valid)
    • count[17] * count[16] = 1*2 = 2
  • Continue for all other combinations.
• After summing all valid pairs, we get the total number of friend requests.

Time and Space Complexity

• Brute-force approach:
  • Time complexity: O(N^2), where N is the length of ages, since we check every pair.
  • Space complexity: O(1), aside from input storage.
• Optimized approach:
  • Time complexity: O(A^2), where A is the range of possible ages (here, up to 120), since we check all age pairs.
  • Space complexity: O(A), for the count array.
  • This is much faster for large N, since A is small and fixed.

Summary

By grouping people by age and counting valid age pairs, we transform a potentially slow brute-force solution into an efficient one. The key insight is that the rules depend only on ages, not positions, so we can use counting and avoid unnecessary comparisons. This makes the solution both elegant and efficient, especially for large input sizes.