algoadvance

In a social group, there are n people with unique ages. We would like to define a relationship rule to determine if two people can be friends:

Given an array ages of n integers representing the ages of people in the group, return the number of friend requests made given the aforementioned rules.

Example:

Input: ages = [16, 16]
Output: 2
Explanation: 2 people of age 16 can send friend requests to each other.

Input: ages = [16, 17, 18]
Output: 2
Explanation: Friend requests are made from 17 -> 16, 18 -> 16, and 18 -> 17.

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

Constraints:

Clarifying Questions

  1. Can a person send a friend request to themselves?
    • No, a person cannot send a friend request to themselves.
  2. Should we consider the upper limit of ages (i.e., <= 120) as a strict constraint?
    • Yes, ages are strictly between 1 and 120.

Strategy

  1. Sort the ages: This will help efficiently manage the conditions.
  2. Use two pointers or binary search: To manage and count pair-wise relationships efficiently.
  3. Handle range constraints:
    • Ensure age[B] <= 0.5 * age[A] + 7.
    • Ensure age[B] > age[A].
    • Ensure age[B] > 100 && age[A] < 100.
  4. Count the requests: Iterate over the array while applying the conditions and count the valid requests.

Code

def numFriendRequests(ages):
    ages.sort()
    requests = 0
    
    for i in range(len(ages)):
        for j in range(len(ages)):
            if i != j:
                ageA = ages[i]
                ageB = ages[j]
                if ageB > 0.5 * ageA + 7 and ageB <= ageA and (ageA <= 100 or ageB >= 100):
                    requests += 1
    
    return requests

# Testing the function
print(numFriendRequests([16, 16]))  # Output: 2
print(numFriendRequests([16, 17, 18]))  # Output: 2
print(numFriendRequests([20, 30, 100, 110, 120]))  # Output: 3

Time Complexity

For n up to 20,000 this approach might seem inefficient. We can further optimize using counting sort and prefix sums.

Optimized Strategy (Sketch)

  1. Counting Sort: Keep track of the count of each age.
  2. Prefix Sums: Use prefix sums to count valid pairs efficiently.

This redesign will further bring the complexity down to manageable levels.

def numFriendRequests(ages):
    from collections import Counter
    
    count = Counter(ages)
    requests = 0
    
    for ageA in count:
        for ageB in count:
            if ageA != ageB:
                if ageB > 0.5 * ageA + 7 and ageB <= ageA and (ageA <= 100 or ageB >= 100):
                    requests += count[ageA] * count[ageB]
                    
            if ageA == ageB:
                if ageA > 0.5 * ageA + 7:
                    requests += count[ageA] * (count[ageA] - 1)
    
    return requests

# Testing the function
print(numFriendRequests([16, 16]))  # Output: 2
print(numFriendRequests([16, 17, 18]))  # Output: 2
print(numFriendRequests([20, 30, 100, 110, 120]))  # Output: 3

This optimized approach counts pairs more efficiently and manages constraints better.

Try our interview co-pilot at AlgoAdvance.com