# Friends Of Appropriate Ages
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/friends-of-appropriate-ages)
Canonical: https://scaleengineer.com/dsa/problems/friends-of-appropriate-ages
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
There are `n` persons on a social media website. You are given an integer array `ages` where `ages[i]` is the age of the `ith` 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 * 104`
* `1 <= ages[i] <= 120`

# Approaches
## Brute Force
The most straightforward approach is to simulate the process directly. We can consider every possible pair of people `(x, y)` where `x` is the sender and `y` is the potential recipient. For each pair, we check if the three conditions for sending a friend request are satisfied. If they are, we increment a counter. This involves a nested loop over the `ages` array.
**Time:** O(N^2), where N is the number of people. We have two nested loops, each iterating up to N times. · **Space:** O(1), as we only use a few variables to store the counts and loop indices.
**Pros:** Simple to understand and implement.; Requires no extra space besides a counter variable.
**Cons:** Highly inefficient due to its quadratic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints (N up to 2 * 10^4).
### Explanation
This method iterates through each person `x` and, for each `x`, iterates through all other people `y`. For every pair `(x, y)` where `x` and `y` are not the same person, it evaluates the conditions given in the problem statement. A request is sent from `x` to `y` if `age[y]` is not too young (`> 0.5 * age[x] + 7`) and not older (`<= age[x]`). The third condition (`age[y] > 100 && age[x] < 100`) is implicitly handled by the second condition, but we can check it for completeness. If the conditions hold, we count it as one request.

```java
class Solution {
    public int numFriendRequests(int[] ages) {
        int n = ages.length;
        int totalRequests = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                if (isRequestSent(ages[i], ages[j])) {
                    totalRequests++;
                }
            }
        }
        return totalRequests;
    }

    private boolean isRequestSent(int ageX, int ageY) {
        // A request is NOT sent if any of these are true.
        if (ageY <= 0.5 * ageX + 7) return false;
        if (ageY > ageX) return false;
        if (ageY > 100 && ageX < 100) return false;
        // Otherwise, a request is sent.
        return true;
    }
}
```
### Algorithm
1. Initialize a variable `totalRequests` to 0.
2. Use a nested loop to iterate through every possible pair of distinct people, `x` (outer loop, index `i`) and `y` (inner loop, index `j`).
3. For each pair, let `ageX = ages[i]` and `ageY = ages[j]`.
4. Check if person `x` will send a friend request to person `y` by verifying that none of the blocking conditions are met:
   - `ageY > 0.5 * ageX + 7`
   - `ageY <= ageX`
   - `!(ageY > 100 && ageX < 100)` (This condition is actually redundant given the second one).
5. If all conditions for sending a request are true, increment `totalRequests`.
6. After iterating through all pairs, return `totalRequests`.

## Sorting and Two Pointers
The brute-force approach is slow because for each person, we scan the entire array. We can optimize this by sorting the `ages` array first. Once sorted, for each person `x` with `ageX`, we can efficiently find the number of people `y` whose age `ageY` falls into the valid range `(0.5 * ageX + 7, ageX]`. This can be done using binary search or a two-pointer approach. A two-pointer approach is particularly efficient here.
**Time:** O(N log N). The sorting step takes O(N log N). The subsequent two-pointer scan takes O(N). Thus, the overall complexity is dominated by sorting. · **Space:** O(log N) or O(N), depending on the implementation of the sorting algorithm used. For example, Java's `Arrays.sort()` for primitives uses a dual-pivot quicksort which has an average space complexity of O(log N).
**Pros:** Significantly more efficient than the brute-force approach.; Passes the time constraints of the problem.
**Cons:** The time complexity is dominated by the sorting step.; It can be slightly more complex to implement correctly compared to the brute-force approach, especially handling duplicates.
### Explanation
After sorting the `ages` array, we can iterate through each person `i`. For each person `i` with age `ageA = ages[i]`, we need to count how many other people `j` have an age `ageB` in the valid range. We can maintain two pointers, `left` and `right`, to define a window of valid ages. As we iterate `i` through the sorted array, `ageA` increases, and the valid window `(0.5 * ageA + 7, ageA]` also slides. The `left` and `right` pointers will only ever move forward, making the search for the window bounds very efficient (amortized O(1) for each `i`). The total number of requests from person `i` is the size of this window, minus one (for person `i` themselves).

```java
import java.util.Arrays;

class Solution {
    public int numFriendRequests(int[] ages) {
        Arrays.sort(ages);
        int n = ages.length;
        int totalRequests = 0;
        int left = 0, right = 0;

        for (int i = 0; i < n; i++) {
            int ageA = ages[i];
            
            // People aged 14 or younger cannot send requests
            if (ageA <= 14) {
                continue;
            }

            // Find the lower bound for recipient's age
            // ages[left] must be > 0.5 * ageA + 7
            while (ages[left] <= 0.5 * ageA + 7) {
                left++;
            }

            // Find the upper bound for recipient's age
            // ages[right] must be <= ageA
            while (right < n && ages[right] <= ageA) {
                right++;
            }

            // All people in window [left, right) are valid targets.
            // The count is (right - 1) - left + 1 = right - left.
            // We subtract 1 because person i cannot request themselves.
            if (right > left) {
                totalRequests += (right - left - 1);
            }
        }
        return totalRequests;
    }
}
```
### Algorithm
1. Sort the `ages` array in non-decreasing order.
2. Initialize `totalRequests = 0`, and two pointers `left = 0`, `right = 0`.
3. Iterate through the sorted `ages` array with index `i` from `0` to `n-1`. Let `ageA = ages[i]`.
4. For each `ageA`, we need to find the number of people `ageB` such that `0.5 * ageA + 7 < ageB <= ageA`.
5. Advance the `left` pointer to the first index where `ages[left] > 0.5 * ageA + 7`.
6. Advance the `right` pointer to the first index where `ages[right] > ageA`.
7. The indices from `left` to `right - 1` represent all people with a valid age to receive a request from person `i`.
8. The total number of such people is `right - left`. Since person `i` cannot send a request to themselves, we subtract 1.
9. Add `right - left - 1` to `totalRequests`, ensuring the count is positive.
10. The `left` and `right` pointers only move forward, so their total movement across all iterations of `i` is O(N).

## Counting Sort with Prefix Sums
The most efficient approach leverages the constraint that ages are in a small, fixed range `[1, 120]`. Instead of considering each person individually, we can group them by age. We first count the number of people of each age. Then, for each pair of ages `(ageA, ageB)`, we can calculate how many requests are sent from the group with `ageA` to the group with `ageB`. To make this even faster, we can use a prefix sum array on the age counts to find the number of people in a valid age range in O(1) time.
**Time:** O(N + A), where N is the number of people and A is the range of ages (121). This is the most optimal solution as it's linear in the size of the input. · **Space:** O(A), where A is the maximum possible age (121). Since A is a constant, this is considered O(1) constant space.
**Pros:** Extremely efficient, with a time complexity that is linear in the number of people.; The complexity is independent of N after the initial count, making it very fast for large inputs.
**Cons:** Requires extra space for the counting and prefix sum arrays.; The logic can be slightly more complex to devise than simpler approaches.
### Explanation
This approach avoids sorting and pairwise comparisons of all `N` people. First, we create a frequency map (an array `ageCounts` of size 121) to count how many people exist for each age from 1 to 120. Then, we build a prefix sum array `prefixSum` on top of `ageCounts`. `prefixSum[i]` will store the total number of people with age up to `i`. 

With these data structures, we can iterate through each possible age `ageA` from 1 to 120. For each `ageA` that exists in our input (`ageCounts[ageA] > 0`), we determine the valid age range for recipients: `(0.5 * ageA + 7, ageA]`. Using the prefix sum array, we can find the number of people in this range in constant time. Let this be `numTargets`. Each of the `ageCounts[ageA]` people of age `ageA` will send a request to these `numTargets` people, excluding themselves. Therefore, the total number of requests from this age group is `ageCounts[ageA] * (numTargets - 1)`. We sum this value over all possible `ageA` to get the final answer.

```java
class Solution {
    public int numFriendRequests(int[] ages) {
        int[] ageCounts = new int[121];
        for (int age : ages) {
            ageCounts[age]++;
        }

        int[] prefixSum = new int[121];
        prefixSum[0] = ageCounts[0];
        for (int i = 1; i <= 120; i++) {
            prefixSum[i] = prefixSum[i - 1] + ageCounts[i];
        }

        int totalRequests = 0;
        // People aged 14 or younger cannot send requests.
        for (int ageA = 15; ageA <= 120; ageA++) {
            if (ageCounts[ageA] == 0) {
                continue;
            }

            int lowerBoundAge = (int) (0.5 * ageA + 7);
            
            // Count of people with age in (lowerBoundAge, ageA]
            int numTargets = prefixSum[ageA] - prefixSum[lowerBoundAge];

            // Each of the ageCounts[ageA] people sends a request to numTargets people.
            // They don't send to themselves, so they send to (numTargets - 1) people.
            if (numTargets > 0) {
                totalRequests += ageCounts[ageA] * (numTargets - 1);
            }
        }
        return totalRequests;
    }
}
```
### Algorithm
1. Notice that the ages are limited to the range `[1, 120]`. Create a frequency array `ageCounts` of size 121 to store the count of people for each age.
2. Populate `ageCounts` by iterating through the input `ages` array. This takes O(N) time.
3. Create a prefix sum array `prefixSum` of size 121 from `ageCounts`. `prefixSum[i]` will store the total number of people with an age less than or equal to `i`. This takes O(A) time, where A=120.
4. Initialize `totalRequests = 0`.
5. Iterate through each possible sender age, `ageA`, from 1 to 120.
6. If `ageCounts[ageA]` is 0, there are no senders of this age, so continue.
7. For each `ageA`, calculate the valid range for a recipient's age, `ageB`. The lower bound is `lowerBoundAge = 0.5 * ageA + 7` and the upper bound is `ageA`.
8. Use the `prefixSum` array to find the total number of people whose age falls in the range `(lowerBoundAge, ageA]`. This count is `numTargets = prefixSum[ageA] - prefixSum[lowerBoundAge]`.
9. Each of the `ageCounts[ageA]` people will send a request to these `numTargets` people, but not to themselves. So, each person sends `numTargets - 1` requests.
10. Add `ageCounts[ageA] * (numTargets - 1)` to `totalRequests`.
11. Return `totalRequests`.

# Solutions
### Java

```java
class Solution {
public
  int numFriendRequests(int[] ages) {
    int[] counter = new int[121];
    for (int age : ages) {
      ++counter[age];
    }
    int ans = 0;
    for (int i = 1; i < 121; ++i) {
      int n1 = counter[i];
      for (int j = 1; j < 121; ++j) {
        int n2 = counter[j];
        if (!(j <= 0.5 * i + 7 || j > i || (j > 100 && i < 100))) {
          ans += n1 * n2;
          if (i == j) {
            ans -= n2;
          }
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numFriendRequests(vector<int> &ages) {
    vector<int> counter(121);
    for (int age : ages)
      ++counter[age];
    int ans = 0;
    for (int i = 1; i < 121; ++i) {
      int n1 = counter[i];
      for (int j = 1; j < 121; ++j) {
        int n2 = counter[j];
        if (!(j <= 0.5 * i + 7 || j > i || (j > 100 && i < 100))) {
          ans += n1 * n2;
          if (i == j)
            ans -= n2;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numFriendRequests(self, ages: List[int]) -> int: counter = Counter(ages) ans = 0 for i in range(1, 121): n1 = counter[i] for j in range(1, 121): n2 = counter[j] if not (j <= 0.5 * i + 7 or j > i or (j > 100 and i < 100)): ans += n1 * n2 if i == j: ans -= n2 return ans

```