Friends Of Appropriate Ages

Medium

Asked by:

14 views

Topics:

Arrays

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the acceptable age range for people in the input array? Are there any minimum or maximum age constraints?
Can the input array `ages` be empty, and if so, what should the return value be?
Are there any constraints on the number of friends each person can have? Are we only counting direct friend requests?
Is the input array guaranteed to contain only positive integers, or could there be other data types or invalid values?
How should I handle the case where someone tries to send a friend request to themselves (age[i] == age[j])?

Brute Force Solution

Approach

The brute force strategy involves checking every single possible pairing of people to see if a friend request would be sent. We consider each person individually and then, for each person, check all other people to determine if a request would be sent according to the age rules.

Here's how the algorithm would work step-by-step:

Take the first person on the list.
Now, consider every other person, one at a time.
For each of these other people, check if the first person would send them a friend request based on the given age conditions.
If a friend request would be sent, count it.
Move on to the next person on the list and repeat the process of checking every other person to see if they would receive a friend request.
Continue this until you have considered every person on the list as the potential sender of friend requests.
Add up all the friend requests that would be sent to get the final total count.

Code Implementation

def friends_of_appropriate_ages(ages):
    total_friend_requests = 0
    number_of_people = len(ages)

    for age_of_person_a in ages:
        for age_of_person_b in ages:
            # Do not allow someone to friend themselves
            if age_of_person_a == age_of_person_b:
                continue

            # Rule: age[B] <= 0.5 * age[A] + 7
            if age_of_person_b <= 0.5 * age_of_person_a + 7:
                continue

            # Rule: age[B] > age[A]
            if age_of_person_b > age_of_person_a:
                continue

            # Rule: age[B] > 100 and age[A] < 100
            if age_of_person_b > 100 and age_of_person_a < 100:
                continue

            # If all conditions are met, increment the friend request count
            total_friend_requests += 1

    return total_friend_requests

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each person in the list of ages, which takes n steps. For each person, it iterates through the rest of the people in the list to determine if a friend request would be sent, resulting in another n steps in the worst case. Therefore, the nested loops lead to approximately n * n operations to check all possible pairs. This gives us a time complexity of O(n²).

Space Complexity

O(1) – The brute force algorithm described iterates through the input list of ages using nested loops. The outer loop iterates through each person, and the inner loop considers every other person. There are no additional data structures, such as arrays, hash maps, or stacks, created to store intermediate results or track visited elements. Only a few constant space variables are used for loop indices and temporary calculations. Therefore, the space complexity is constant, O(1), as the auxiliary space used does not depend on the input size, N, which represents the number of people.

Optimal Solution

Approach

The key is to count how many people there are of each age. Then, for each age, figure out how many people of that age can send friend requests to others, including themselves, based on the age rules. This avoids checking every possible pair of people.

Here's how the algorithm would work step-by-step:

First, count how many people there are of each age. For instance, you might find there are 5 people who are 20 years old, 3 people who are 30 years old, and so on.
Next, go through each age, one at a time. For each age, check the age rules to figure out which other ages can receive friend requests from people of that age.
Remember that a person can send a friend request to someone of their own age too, if the age rules allow it.
For each age, multiply the number of people of that age by the number of people (of any age) that they *can* send friend requests to. This gives you the total number of possible friend requests for that age.
Add up the total number of possible friend requests from all ages. This is the final answer.

Code Implementation

def friends_of_appropriate_ages(ages):
    age_counts = [0] * 121
    for age in ages:
        age_counts[age] += 1

    total_requests = 0

    for age_a in range(1, 121):
        count_a = age_counts[age_a]
        if count_a == 0:
            continue

        # Iterate through all possible ages to consider
        for age_b in range(1, 121):
            count_b = age_counts[age_b]
            if count_b == 0:
                continue

            # Rule condition check
            if age_b <= 0.5 * age_a + 7:
                continue

            if age_b > age_a:
                continue

            if age_b > 100 and age_a < 100:
                continue

            # Accumulate number of requests
            if age_a == age_b:
                total_requests += count_a * (count_b - 1)

            # Avoiding double counting if same person
            else:
                total_requests += count_a * count_b

    return total_requests

Big(O) Analysis

Time Complexity

O(A + N) – The algorithm first counts the number of people of each age, where A is the range of possible ages (1 to 120). This is O(A). Then, the algorithm iterates through each possible age and checks which other ages can receive friend requests. For each age, we perform a constant time check to determine the possible friends, and multiply counts of ages that can be friends, which takes constant time. The outer loop runs for all possible ages and inner loop will be the count of all the people N, yielding time complexity O(N). Therefore the overall time complexity is O(A + N).

Space Complexity

O(1) – The algorithm uses a frequency count of ages. Since ages are bounded (presumably between 1 and 120), this count uses a fixed amount of space, regardless of the number of input ages (N). No other data structures that scale with the input size are used. Therefore, the auxiliary space used is constant.

Edge Cases

Case	How to Handle
Empty or null ages array	Return 0 immediately, as no requests can be made.
Ages array with only one element	Return 0 immediately since a single person cannot send a request to themselves.
All ages are identical	The count of requests will be n * (n - 1) if all people are of valid age to send requests to each other.
Ages array with very large numbers	Ensure that calculations, particularly comparisons, do not overflow integer limits by using 32 or 64 bit integers
Ages array is sorted in ascending order	The algorithm should still correctly compute the number of valid friend requests despite the order.
Ages array is sorted in descending order	The algorithm should still correctly compute the number of valid friend requests despite the order.
Ages array contains ages near the lower boundary (e.g., 14, 15)	Ensure the age check 'age[y] <= 0.5 * age[x] + 7' correctly handles ages at the lower limit
Maximum array size for a large number of ages	Consider using a counting sort approach if the range of ages is relatively small compared to the number of ages, to improve performance to linear time.

Empty or null ages array

How to Handle:

Return 0 immediately, as no requests can be made.

Ages array with only one element

How to Handle:

Return 0 immediately since a single person cannot send a request to themselves.

All ages are identical

How to Handle:

The count of requests will be n * (n - 1) if all people are of valid age to send requests to each other.

Ages array with very large numbers

How to Handle:

Ensure that calculations, particularly comparisons, do not overflow integer limits by using 32 or 64 bit integers

Ages array is sorted in ascending order

How to Handle:

The algorithm should still correctly compute the number of valid friend requests despite the order.

Ages array is sorted in descending order

How to Handle:

The algorithm should still correctly compute the number of valid friend requests despite the order.

Ages array contains ages near the lower boundary (e.g., 14, 15)

How to Handle:

Ensure the age check 'age[y] <= 0.5 * age[x] + 7' correctly handles ages at the lower limit

Maximum array size for a large number of ages

How to Handle:

Consider using a counting sort approach if the range of ages is relatively small compared to the number of ages, to improve performance to linear time.