Friends Of Appropriate Ages - Leetcode Solution

Problem:

Given an array of ages, find a group of people, consisting of at least two people and with a maximum age difference of 2 years, where the ages must be at least 18 years old. Return the total number of such groups.

Example:

Input: [16,16,16,17,18,18,20,22,25] Output: 6 Explanation: The groups that meet the criteria are [16,16], [16,16,16], [17,18], [18,18], [20,22], [22,25].

Solution:

The brute-force solution to this problem is to consider all pairs of ages, check whether they form a valid group, and increment the count accordingly. However, this approach has a time complexity of O(n^2), where n is the number of elements in the array, which is inefficient.

A better approach is to use a hash table to keep track of the frequency of ages, and then loop over the keys of the hash table to find valid groups. Here are the detailed steps:

1. Initialize a hash table age_map, where the keys are the ages and the values are the frequency of the respective age.
2. Loop over the keys of the age_map and check whether the age is at least 18 years old. If not, continue.
3. If the age is at least 18 years old, check whether there are at least two people with that age. If not, continue.
4. If there are at least two people with the age, compute the lower and upper bounds of the valid age range using the formula age - 2 and age + 2.
5. Loop over the keys of the age_map again and check whether the age is within the valid age range. If so, add the product of the frequencies of the two ages to the count of valid groups. Note that the product is used because we are interested in all combinations of pairs.
6. Return the count of valid groups.

Here's the Python code that implements the above algorithm:

def numFriendRequests(ages): age_map = {} for age in ages: age_map[age] = age_map.get(age, 0) + 1

count = 0
for age1 in age_map.keys():
    if age1 < 18:
        continue
    
    freq1 = age_map[age1]
    if freq1 < 2:
        continue
    
    lower = age1 - 2
    upper = age1
    
    for age2 in age_map.keys():
        if lower <= age2 <= upper:
            freq2 = age_map[age2]
            count += freq1 * freq2
            
            if age1 == age2:
                count -= freq1
            
return count

The time complexity of this solution is O(n), where n is the number of elements in the array. The space complexity is also O(n) due to the use of the hash table.

1