852. Friends Of Appropriate Ages¶

Difficulty: Medium

852. Friends Of Appropriate Ages

Medium

There are n persons on a social media website. You are given an integer array ages where ages[i] is the age of the i^th person.

A Person x will not send a friend request to a person y (x != y) if any of the following conditions is true:

age[y] <= 0.5 * age[x] + 7
age[y] > age[x]
age[y] > 100 && age[x] < 100

Otherwise, x will send a friend request to y.

Note that if x sends a request to y, y will not necessarily send a request to x. Also, a person will not send a friend request to themself.

Return the total number of friend requests made.

Example 1:

Input: ages = [16,16]
Output: 2
Explanation: 2 people friend request each other.

Example 2:

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

Example 3:

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

Constraints:

n == ages.length
1 <= n <= 2 * 10⁴
1 <= ages[i] <= 120

Solution¶

class Solution {
    public int numFriendRequests(int[] ages) {
        int n = ages.length, count = 0;
        Arrays.sort(ages);
        for (int i = 0; i < n / 2; i++) {
            int temp = ages[i];
            ages[i] = ages[n - 1 - i];
            ages[n - 1 - i] = temp;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int current = ages[i];
            int res = binarySearch(i, current, ages);
            if (!map.containsKey(current)) map.put(current, res);
        }
        for (int i = 0; i < n; i++) count += map.getOrDefault(ages[i], 0);
        return count;
    }
    private int binarySearch(int current_ind, int current, int ages[]) {
        int n = ages.length;
        int low = current_ind + 1, high = n - 1, ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (ages[mid] <= current && ages[mid] > 0.5 * current + 7 && !(ages[mid] > 100 && current < 100)) {
                ans = mid;
                low = mid + 1;
            }
            else high = mid - 1;
        }
        if (ans == -1) return 0;
        return ans - current_ind;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here