Leetcode 825: Friends Of Appropriate Ages
You are given an integer array ages, where each element represents the age of a person on a social media platform. A person will not send a friend request to another person if any of the following conditions are true:
- The recipient’s age is less than or equal to half of the sender’s age plus 7.
- The recipient’s age is greater than the sender’s age.
- The recipient’s age is greater than 100 and the sender’s age is less than 100.
Otherwise, the sender can send a friend request. Return the total number of friend requests made between people.
Problem
Approach
Steps
Complexity
Input: The input consists of a single integer array `ages` of length `n` (the number of people). Each element represents the age of a person.
Example: Input: ages = [18, 20, 30, 40]
Constraints:
• 1 <= n <= 2 * 10^4
• 1 <= ages[i] <= 120
Output: The output should be an integer representing the total number of valid friend requests made according to the given conditions.
Example: Output: 4
Constraints:
• The output must be an integer representing the number of friend requests.
Goal: The goal is to compute the total number of friend requests by checking each pair of people in the `ages` array and applying the given conditions.
Steps:
• Step 1: Create a frequency map of the ages.
• Step 2: For each pair of distinct ages, check if they meet the conditions for sending a friend request.
• Step 3: If a valid request is possible, add the appropriate number of requests to the result.
Goal: Ensure that the input adheres to the problem constraints and that the logic handles all edge cases correctly.
Steps:
• All elements of `ages` must be within the range of 1 to 120.
Assumptions:
• There are no people with ages less than 1 or greater than 120.
• The problem guarantees that the input array will not be empty.
• Input: Input: ages = [18, 20, 30, 40]
• Explanation: The person with age 20 will send a request to 18, 30, and 40. The person with age 30 will send a request to 40. This results in a total of 4 requests.
Approach: The approach involves iterating through each possible pair of people in the `ages` array and applying the given conditions to count the valid requests.
Observations:
• The conditions for sending a friend request are simple comparisons of the ages.
• We can take advantage of counting the occurrences of each age and use these counts to avoid directly comparing every possible pair of people.
Steps:
• Step 1: Create a frequency map for the ages to count how many people have each age.
• Step 2: For each pair of ages, check the conditions for sending a friend request.
• Step 3: If a valid request is possible, add the product of the frequencies of those ages to the result, adjusting for cases where the ages are the same.
Empty Inputs:
• There will always be at least one person, so the input will never be empty.
Large Inputs:
• When the input size is large, the solution should still handle it efficiently.
Special Values:
• Ensure correct handling of the edge case where someone is 100 years old or more.
Constraints:
• The algorithm should efficiently handle inputs with up to 20,000 elements.
int numFriendRequests(vector<int>& ages) {
unordered_map<int, int> cnt;
for(int age: ages)
cnt[age]++;
int res = 0;
for(auto a: cnt)
for(auto b: cnt)
if(request(a.first, b.first))
res += a.second * (b.second - (a.first == b.first? 1: 0));
return res;
}
bool request(int a, int b) {
return !(b <= 0.5 * a + 7 || b > a || (b > 100 && a < 100));
}
1 : Function Declaration
int numFriendRequests(vector<int>& ages) {
Declares the function `numFriendRequests` that takes a vector of integers `ages` representing the ages of individuals, and returns the number of valid friend requests.
2 : Map Initialization
unordered_map<int, int> cnt;
Initializes an unordered map `cnt` to keep track of the frequency of each age in the `ages` vector.
3 : Loop
for(int age: ages)
Iterates through each `age` in the `ages` vector to populate the `cnt` map with the count of each age.
4 : Map Update
cnt[age]++;
Increments the count of the current `age` in the `cnt` map.
5 : Result Initialization
int res = 0;
Declares and initializes an integer variable `res` to store the total number of valid friend requests.
6 : Nested Loop
for(auto a: cnt)
Begins a loop that iterates over each age `a` in the `cnt` map, representing the first person in a potential friend request.
7 : Nested Loop
for(auto b: cnt)
Begins a second nested loop that iterates over each age `b` in the `cnt` map, representing the second person in a potential friend request.
8 : Condition Check
if(request(a.first, b.first))
Checks whether a valid friend request can be made between person `a` and person `b` by calling the `request` function.
9 : Calculation
res += a.second * (b.second - (a.first == b.first? 1: 0));
If a valid request is possible, increment `res` by the product of the counts of ages `a` and `b`, adjusting for the case where `a` and `b` are the same age.
10 : Return Statement
return res;
Returns the total number of valid friend requests calculated.
11 : Function Declaration
bool request(int a, int b) {
Declares the `request` function that checks whether a person with age `a` can send a friend request to a person with age `b` based on specific conditions.
12 : Condition Check
return !(b <= 0.5 * a + 7 || b > a || (b > 100 && a < 100));
Returns true if the conditions for a valid friend request are met, otherwise false. The conditions include age restrictions for sending requests.
Best Case: O(n), where n is the number of people, as we can use frequency counting to reduce the number of comparisons.
Average Case: O(n^2), if we need to check all pairs of ages.
Worst Case: O(n^2), for the largest inputs where all people have distinct ages.
Description: The time complexity is O(n^2) in the worst case, where we need to compare each pair of distinct ages.
Best Case: O(1), if there are few distinct ages.
Worst Case: O(n), where n is the number of distinct ages.
Description: The space complexity is O(n) due to the space required for the frequency map.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus