825. Friends Of Appropriate Ages

/*
Time Complexity: O(n + maxAge)
Space Complexity: O(maxAge)

(B <= A/2 + 7) & (B > A) ==> (A <= A/2+7) ==> A <= 14 .. for these ages of A its not valid.
*/
class Solution {
    public int numFriendRequests(int[] ages) {
        if (ages == null || ages.length == 0) {
            return 0;
        }
        int minAge = Integer.MAX_VALUE;
        int maxAge = 0;
        HashMap<Integer, Integer> counts = new HashMap<>();
        for (int age : ages) {
            minAge = Math.min(minAge, age);
            maxAge = Math.max(maxAge, age);
            counts.put(age, counts.getOrDefault(age, 0)+1);
        }
        // (B <= A/2 + 7) & (B > A) ==> (A <= A/2+7) ==> A <= 14 .. for these ages of A its not valid.
        if (maxAge < 15) {
            return 0;
        }
        minAge = Math.max(minAge, 15);
        int[] prefixSum = new int[maxAge+1];

        int result = 0;
        for (int i = minAge; i <= maxAge; i++) {
            prefixSum[i] = prefixSum[i-1];
            if (!counts.containsKey(i)) {
                continue;
            }
            int count = counts.get(i);
            prefixSum[i] += count;
            result += (prefixSum[i] - prefixSum[(int)(i*0.5+7)] - 1) * count;
        }
        return result;
    }
}


/*
Time Complexity: O(n + 121)
Space Complexity: O(121)
*/
// class Solution {
//     public int numFriendRequests(int[] ages) {
//         if (ages == null || ages.length == 0) {
//             return 0;
//         }
//         // int minAge = 120;
//         // int maxAge = 15;
//         int[] counts = new int[121];
//         int[] prefixSum = new int[121];
//         for (int age : ages) {
//             // minAge = Math.min(minAge, age);
//             // maxAge = Math.max(maxAge, age);
//             counts[age]++;
//         }

//         // if (minAge < 15) {
//         //     minAge = 15;
//         // }
//         int result = 0;
//         // for (int i = minAge; i <= maxAge; i++) {
//         for (int i = 15; i <= 120; i++) {
//             prefixSum[i] = prefixSum[i-1] + counts[i];
//             if (counts[i] > 0) {
//                 result += (prefixSum[i] - prefixSum[(int)(i*0.5+7)] - 1) * counts[i];
//             }
//         }
//         return result;
//     }
// }