825. Friends Of Appropriate Ages

MediumArrayTwo PointersBinary SearchSorting

Problem Description

In this problem, we're modeling a simplified version of friend requests on a social media platform. Every user has an age, and there is an array called ages where ages[i] represents the age of the i-th person.

The task is to count the number of friend requests made on the platform under certain rules. Person x can send a friend request to person y only if they meet the following three conditions:

Person y's age is not less than or equal to 0.5 times the age of person x plus 7.
Person y's age is less than or equal to the age of person x.
If person y is over 100 years old, then person x must also be over 100 (no one under 100 can send a friend request to someone over 100).

It's important to note that friend requests aren't reciprocal (if x requests y, y does not automatically request x), and no one can send a friend request to themselves. The goal is to figure out the total number of these possible friend requests.

Intuition

To solve the problem, we analyze the conditions under which one person will send a friend request to another and apply these to all possible pairs of ages. We need to consider the age limitations and the fact that there could be multiple people with the same age.

Since the problem limits ages to be between 1 and 120, we can iterate over each possible age for both x and y (the sender and the receiver of the friend request). For each age pair, we calculate the number of possible friend requests based on the number of people who have those ages.

The solution uses a Counter to tally the number of people at each age which allows efficient lookups. For each pair of ages (i, j), if i can send a request to j according to the rules above, we increase our friend request count by n1 * n2 where n1 is the number of people with age i and n2 is the number of people with age j. We need to account for the fact that people cannot friend request themselves, so if i equals j, we subtract the number of people who would have otherwise friend-requested themselves (which is n2).

This approach uses two nested loops to check all possible age pairs and applies the given conditions to calculate the number of friend requests.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The solution provided proceeds through a process that we can break down step by step:

Import the Counter Class: The Counter class from the collections module is used, which provides a way to count the number of occurrences of each unique element in an iterable. In this case, it's used to keep track of how many people are of each age.
Initialize the Answer: A variable ans is initialized to 0. This variable keeps a running total of all valid friend requests.
Double Loop Through Each Age: Two nested loops iterate over all possible ages from 1 to 120. The first loop uses i to represent the age of the person sending the request (person x), and the second loop uses j to represent the age of the potential recipient (person y).
Getting Count of Each Age Group: Using the Counter created, we retrieve n1, the count of people with age i and n2, the count of people with age j.
Apply the Conditions: Within the nested loop, for each (i, j) pair, the code checks whether the three conditions mentioned in the problem statement are not met. If all three conditions are false, it means that a person with age i can send a friend request to the person with age j.
Update the Answer: If the conditions are satisfied (meaning that i can send a friend request to j), the number of friend requests is updated by adding n1 * n2 to the total. This accounts for all possible friend requests that can be made by n1 people of age i to n2 people of age j.
Self-request Adjustment: Since no one can send a friend request to themselves, if i equals j, the code subtracts the number of self requests, which is n2. This is because when the ages are equal, each person has been counted as sending a request to themselves once, which is not allowed.
Return the Answer: After all pairs of ages have been checked, the total number of friend requests is returned as the final answer.

Here is how the conditions look like in code:

j <= 0.5 * i + 7
j > i
j > 100 && i < 100

The solution iterates over all age combinations only once, resulting in an efficient approach with a time complexity that is constant—not dependent on the number of people but rather on the fixed number range (which is 1 to 120). This is a key insight that greatly simplifies an otherwise potentially complex problem, especially since a straightforward nested loop over the original list of ages would have a time complexity more directly tied to the number of persons.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Suppose we have an array of ages: ages = [14, 16, 16, 60].

Let's illustrate the solution approach:

Import the Counter Class: First, we import Counter from collections.
Initialize the Answer: We set ans = 0.
Double Loop Through Each Age: Now, we start two nested loops of ages between 1 and 120 (but in practice, we only consider ages present in our array). Here, they are: 14, 16, and 60.
Getting Count of Each Age Group: We use a Counter to count age occurrences in our example.
- Counter(ages) gives {14: 1, 16: 2, 60: 1}.
- So, n1 is the count of people per age on the outer loop and n2 is that on the inner loop.
Apply the Conditions: We check if person x (i) can send a friend request to person y (j) by negating the conditions given.
- j > 0.5 * i + 7
- j <= i
- Not (j > 100 && i < 100), which simplifies to i >= 100 || j <= 100 (since we can't send to someone over 100 unless i is also over 100).
Update the Answer: We go through combinations, considering our array and other conditions.
- Person 14 cannot send to anyone (fails condition 1 with everyone else).
- Persons of age 16 can send to each other but not to age 14 (fails condition 1) or 60 (fails condition 2).
  - 2 people of age 16 sending requests to 2 people of age 16 (including themselves initially) is 2 * 2.
- Person 60 can send to everyone 16 and over, but since there are only people of age 16 and 60, they can send to the 2 people of age 16.
Self-request Adjustment:
- Since people can't friend request themselves, we subtract each person of age 16 from that count, which gives us 2 * 2 - 2 = 2 valid friend requests from ages 16 to 16.
- There is no need to adjust for age 14 or 60 as 14 cannot send any requests and there is only one person aged 60.
Return the Answer:
- We have 2 requests from persons aged 16 to 16, and each person aged 60 can send to both aged 16, so 2 + 2 = 4.
- The final ans = 4.

This is the total number of valid friend requests that happen in our small example: 4. The process uses logical conditions and arithmetic to carefully tally the requests between age groups, accounting for self-requests and avoids unnecessary computations through the use of a count for each age bracket.

Solution Implementation

1from collections import Counter  # Import the Counter class from the collections module
2
3class Solution:
4    def num_friend_requests(self, ages: List[int]) -> int:
5        # Counter object to store the frequency of each age
6        age_count = Counter(ages)
7      
8        # Initialize the answer to 0
9        friend_requests = 0
10      
11        # Loop through all possible ages from 1 to 120
12        for age_a in range(1, 121):
13            count_a = age_count[age_a]  # Number of people with age age_a
14          
15            # Inner loop to iterate through all possible ages to find potential friends
16            for age_b in range(1, 121):
17                count_b = age_count[age_b]  # Number of people with age age_b
18              
19                # Check the conditions when a person A can send a friend request to B:
20                # Condition 1: B should not be less than or equal to 0.5 * A + 7
21                # Condition 2: B should be less than or equal to A (A can send to B of same age or younger)
22                # Condition 3: If B is over 100, then A must be over 100 as well
23                if not (age_b <= 0.5 * age_a + 7 or age_b > age_a or (age_b > 100 and age_a < 100)):
24                    # If the conditions are met, increase the count of friend requests
25                    friend_requests += count_a * count_b
26                  
27                    # If both ages are the same, we have to subtract the instances where A is B
28                    # because a person cannot friend request themselves
29                    if age_a == age_b:
30                        friend_requests -= count_b
31      
32        # Return the total friend requests that can be made
33        return friend_requests
34

1class Solution {
2    public int numFriendRequests(int[] ages) {
3        // Array to keep count of each age (up to 120)
4        int[] ageCount = new int[121]; 
5        // Fill the ageCount array with the frequency of each age
6        for (int age : ages) {
7            ageCount[age]++;
8        }
9      
10        // Variable to hold the final result
11        int friendRequests = 0;
12      
13        // Loop through each age for the sender
14        for (int senderAge = 1; senderAge < 121; senderAge++) {
15            int senderCount = ageCount[senderAge];
16          
17            // Only continue if there are people with this age
18            if (senderCount > 0) {
19                // Loop through each age for the receiver
20                for (int receiverAge = 1; receiverAge < 121; receiverAge++) {
21                    int receiverCount = ageCount[receiverAge];
22                    // Check if the friend request condition is satisfied
23                    if (!(receiverAge <= 0.5 * senderAge + 7 || receiverAge > senderAge || (receiverAge > 100 && senderAge < 100))) {
24                        // Add the product of the counts of the respective ages
25                        friendRequests += senderCount * receiverCount;
26                        // Deduct the count when sender and receiver are of the same age
27                        if (senderAge == receiverAge) {
28                            friendRequests -= receiverCount;
29                        }
30                    }
31                }
32            }
33        }
34        // Return the total number of friend requests
35        return friendRequests;
36    }
37}
38

1class Solution {
2public:
3    int numFriendRequests(vector<int>& ages) {
4        // Create a counter array to store the number of people at each age.
5        vector<int> ageCounter(121, 0); // Initialized with 121 elements all set to 0
6     
7        // Count the number of instances of each age
8        for (int age : ages) {
9            ageCounter[age]++;
10        }
11      
12        int totalFriendRequests = 0; // Initialize the total number of friend requests to 0
13
14        // Loop through the ages from 1 to 120 (inclusive)
15        for (int ageA = 1; ageA <= 120; ++ageA) {
16            int countAgeA = ageCounter[ageA]; // Number of people with age A
17
18            // Loop through all possible ages for potential friends
19            for (int ageB = 1; ageB <= 120; ++ageB) {
20                int countAgeB = ageCounter[ageB]; // Number of people with age B
21
22                // Check if a friend request can be sent according to the problem's conditions
23                if (!(ageB <= 0.5 * ageA + 7 ||   // Age B should not be less than or equal to 0.5 * Age A + 7
24                      ageB > ageA ||               // Age B should be less than or equal to Age A
25                      (ageB > 100 && ageA < 100)   // If Age B is > 100, then Age A should also be > 100
26                     )) {
27                    totalFriendRequests += countAgeA * countAgeB;  // Add the count product to total requests
28                  
29                    // If ages are the same, subtract the self request count
30                    if (ageA == ageB) {
31                        totalFriendRequests -= countAgeB; // Subtract the diagonal
32                    }
33                }
34            }
35        }
36
37        // Return the total number of friend requests
38        return totalFriendRequests;
39    }
40};
41

1// Array to store the number of people at each age, initialized with 121 elements all set to 0
2const ageCounter: number[] = new Array(121).fill(0); 
3
4// Function that calculates the number of friend requests
5function numFriendRequests(ages: number[]): number {
6    // Count the number of instances of each age in the input array
7    ages.forEach((age) => {
8        ageCounter[age]++;
9    });
10
11    let totalFriendRequests: number = 0; // Initialize the total number of friend requests to 0
12
13    // Iterate through the ages from 1 to 120 (inclusive) to calculate the number of friend requests
14    for (let ageA = 1; ageA <= 120; ++ageA) {
15        const countAgeA = ageCounter[ageA]; // Number of people with age A
16
17        // Loop through all possible ages to check for potential friend matches
18        for (let ageB = 1; ageB <= 120; ++ageB) {
19            const countAgeB = ageCounter[ageB]; // Number of people with age B
20
21            // Check if a friend request can be sent according to the given conditions
22            if (!(ageB <= 0.5 * ageA + 7 ||  // Age B should not be less than or equal to 0.5 times Age A + 7
23                  ageB > ageA ||             // Age B must be less than or equal to Age A
24                  (ageB > 100 && ageA < 100) // If Age B is over 100, then Age A must also be over 100
25                 )) {
26                totalFriendRequests += countAgeA * countAgeB;  // Accumulate the product of the counts into total requests
27              
28                // If Age A is the same as Age B, subtract the count for self requests
29                if (ageA === ageB) {
30                    totalFriendRequests -= countAgeB; // Adjust for self-request scenarios by subtracting the count
31                }
32            }
33        }
34    }
35
36    // Return the total computed friend requests
37    return totalFriendRequests;
38}
39

Time and Space Complexity

Time Complexity

The given code consists of two nested loops each ranging from 1 to 121, resulting in a fixed number of iterations for the loops. Since the loops do not depend on the size of the input (ages list), they have a constant runtime. However, the overall time complexity does still depend on the Counter operation performed on the ages list earlier, which iterates over the entire list once.

The Counter operation has a time complexity of O(N) where N is the number of elements in ages. The nested loops have a constant time complexity of O(121 * 121) because they iterate over a fixed range independent of the input size. Therefore, the total time complexity of the code is predominated by the Counter operation, resulting in O(N).

Space Complexity

The space complexity of the code is influenced by the additional storage needed for the counter variable, which depends on the number of unique elements in ages. In the worst case, each age is unique, so the space complexity for counter is O(K) where K is the number of unique ages. Given the constraints of the problem (ages are between 1 and 120), the maximum number of unique ages K can be 120.

Therefore, the space complexity is O(K), yet since K is constant and limited to 120, this could also be considered O(1) in the context of this problem where K does not scale with the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of these properties could exist for a graph but not a tree?

Contain cycles

There are multiple ways to traverse

Connected

Has no cycle

I don’t know