Friends Of Appropriate Ages LeetCode solution in Python

1
# Runtime: 936 ms (Top 28.73%) | Memory: 14.9 MB (Top 52.36%)
2
class Solution:
3
    """
4
    approach:
5
    we can try solving this problem by finding the valid age group for each age
6
    sort the array in descending order
7
    iterate from right to left
8
    for current age, find the valid agegroup to which the current age person will send a request
9
    we can use binary search for that
10
    if current age is x, then valid age group to send a request is:
11
    x*0.5 + 7 < age(y) <= x
12
    we can find the left limit using binary search
13
    """
14

15
    def binary_search(self, arr, low, high, value):
16
        if low > high:
17
            return high
18
        mid = (low + high) // 2
19
        if arr[mid] > value:
20
            return self.binary_search(arr, low, mid - 1, value)
21
        else:
22
            return self.binary_search(arr, mid + 1, high, value)
23

24
    def numFriendRequests(self, ages: List[int]) -> int:
25
        ages = sorted(ages)
26
        total_count = 0
27
        for i in range(len(ages) - 1, -1, -1):
28
            if i + 1 < len(ages) and ages[i] == ages[i + 1]:
29
                total_count += prev_count
30
                continue
31

32
            prev_count = 0
33
            lower_limit = 0.5 * ages[i] + 7
34
            index = self.binary_search(ages, 0, i - 1, lower_limit)
35
            prev_count = i - (index + 1)
36
            total_count += prev_count
37
        return total_count