Problem statement

https://leetcode.com/problems/friends-of-appropriate-ages/

Solution 1

Notice, that person with age A will request persons with age B if and only if:

  1. if A >= 100, then 0.5A + 7 < B <= A
  2. if A < 100, then 0.5A + 7 < B < min(A, 100) = A, which is exactly the same as previous condition, so actually third condition is redundant here.

So, what we can do is to sort our numbers and then do binary search. Notice also that person with age <= 14 will not have any requests, because interval is empty.

Complexity

Time complexity will be O(n log n), space complexity is O(n).

Code

from bisect import bisect

class Solution:
    def numFriendRequests(self, ages):
        ages.sort()
        ans = 0
        for A in ages:
            if A >= 15:
                ans += (bisect(ages, A) - bisect(ages, A/2+7)) - 1
        return ans

Solution 2

There is also O(n + A) solution, where A is range of ages: count each age and then calculate number of connections for each age.

Complexity

It is O(n + A) for time and O(A) for space.

Code

class Solution:
    def numFriendRequests(self, ages):
        cnt = [0]*121
        for a in ages: cnt[a] += 1    
        acc = list(accumulate(cnt))
        return sum(cnt[i] * (acc[i] - acc[i//2+7] - 1) for i in range(15, 121))