Friend Requests

XXX. Friend Requests

Counting

HashMap

Problem Statement:

Calculate the number of friend requests made based on age rules:

• Person A won't send request if age[B] ≤ 0.5 * age[A] + 7
• Person A won't send request if age[B] > age[A]
• Person A won't send request if age[B] > 100 && age[A] < 100
• A person can't send request to themselves

Implementation:

public int numFriendRequests(int[] ages) {
    // Count frequency of each age
    Map count = new HashMap<>();
    for (int age : ages) 
        count.put(age, count.getOrDefault(age, 0) + 1);
    
    int res = 0;
    // Check all possible age pairs
    for (Integer a : count.keySet())
        for (Integer b : count.keySet())
            if (request(a, b))
                // For same age, subtract 1 from count (can't request self)
                res += count.get(a) * (count.get(b) - (a == b ? 1 : 0));
    
    return res;
}

// Check if age 'a' can send request to age 'b'
private boolean request(int a, int b) {
    return !(b <= 0.5 * a + 7 ||    // Too young
            b > a ||                 // Too old
            (b > 100 && a < 100));   // Age restriction
}

Complexity:

Time Complexity: O(A²) where A is number of unique ages
Space Complexity: O(A) for HashMap

Key Points:

• **Optimization Technique**:
  • Count frequencies instead of checking all pairs
  • Only process unique ages
  • Handle same-age case separately
• **Age Rules**:
  • Younger limit: b > 0.5a + 7
  • Older limit: b ≤ a
  • Special case for age > 100
• **Edge Cases**:
  • Same age requests (subtract 1)
  • Empty age array
  • Single person age groups

Example:

For ages [16,16,20,20]:

• Count: {16→2, 20→2}
• Check pairs:
  • 16→16: 2 * (2-1) = 2 requests
  • 16→20: Not valid (too old)
  • 20→16: Not valid (too young)
  • 20→20: 2 * (2-1) = 2 requests
• Total: 4 requests