825. Friends Of Appropriate Ages

Version #1 Bucket Sort and Prefix Sum[Preferred]
99.23 
class Solution {
    public int numFriendRequests(int[] ages) {
        if (ages == null || ages.length == 0) {
            return 0;
        }
        /*
        age[B] <= 0.5 * age[A] + 7
        B > 0.5A + 7
        0.5A + 7 < B <= A
        0.5 A + 7 = A
        A = 14
        */
        int[] bucket = new int[121];
        int[] prefixSum = new int[121];
        for (int age : ages) {
            bucket[age]++;
        }
     
        for (int i = 1; i < 121; i++) {
            prefixSum[i] = prefixSum[i - 1] + bucket[i];
        }
        int result = 0;
        for (int i = 15; i < bucket.length; i++) {
            if (bucket[i] != 0) {
                result += (prefixSum[i] - prefixSum[i / 2 + 7] - 1) * bucket[i];
            }
        } 
        return result;
    }
}



Version #2 Two Pointers
Time O(nlogn)
Space O(1)

19.70 %
class Solution {
    public int numFriendRequests(int[] ages) {
        // age[B] <= 0.5 * age[A] + 7
        // B <= 0.5A + 7 || B > A
        // B > 0.5A + 7 && B <= A
        // (0.5A + 7, A]
        // if A <= 0.5A + 7 -> A <= 14 -> B doesn't exist
        Arrays.sort(ages);
        int result = 0;
        int j = 0, dupStart = 0;
        for (int i = 0; i < ages.length; i++) { // ages[i] -> A, ages[j, i) -> B, A request B
            if (ages[i] <= 14) continue;
            if (i > 0 && ages[i] != ages[i - 1]) dupStart = i;
            while (ages[j] <= 0.5 * ages[i] + 7) {
                j++;
            }
            if (j < i) {
                result += i - j;
            }
            if (dupStart < i) {
                result += i - dupStart;
            }
        }
        return result;
    }
}