825. Friends Of Appropriate Ages

1. Description

Some people will make friend requests. The list of their ages is given and ages[i] is the age of the ith person.
Person A will NOT friend request person B (B != A) if any of the following conditions are true:

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

Otherwise, A will friend request B.
Note that if A requests B, B does not necessarily request A. Also, people will not friend request themselves.
How many total friend requests are made?

2. Example

Example 1:
Input: [16,16]
Output: 2
Explanation: 2 people friend request each other.

Example 2:
Input: [16,17,18]
Output: 2
Explanation: Friend requests are made 17 -> 16, 18 -> 17.

Example 3:
Input: [20,30,100,110,120]
Output: 3
Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

3. Note

• 1 <= ages.length <= 20000.
• 1 <= ages[i] <= 120.

4. Solutions

My Accepted Solution

m = AGE_UPPER_BOUND, n = i_ages.size()
Time complexity: O($m^2 + n$)
Space complexity: O(m)

class Solution {
public:
    // int numFriendRequests(vector<int>& ages)
    int numFriendRequests(const vector<int>& i_ages) {
        vector<int> ageCount(AGE_UPPER_BOUND + 1);
        for (auto age : i_ages) {
            ++ageCount[age];
        }

        int count = 0;
        for (int age1 = AGE_LOWER_BOUND; age1 <= AGE_UPPER_BOUND; ++age1) {
            for (int age2 = AGE_LOWER_BOUND; age2 <= AGE_UPPER_BOUND; ++age2) {
                if (age2 <= age1 / 2 + 7 || age2 > age1 || age2 > 100 && age1 < 100) {
                    continue;
                }

                // if age1 == age2, we must decrease ageCount[age1] because we can't make friends with ourself
                count += ageCount[age1] * ageCount[age2] - (age1 == age2 ? ageCount[age1] : 0);
            }
        }

        return count;
    }

private:
    const int AGE_LOWER_BOUND = 1;
    const int AGE_UPPER_BOUND = 120;
};