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.

Examples

Example 1

1
2
3

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

Example 2

1
2
3

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

Example 3

1
2
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^4
  • 1 <= ages[i] <= 120

Solution

Method 1 – Sorting and Two Pointers

Intuition

If we sort the ages, we can efficiently count valid friend requests for each person by using two pointers to find the valid age range for each person. This avoids checking every possible pair.

Approach

  1. Sort the ages array.
  2. For each person (age a):
    • Use two pointers to find the smallest index l such that ages[l] > 0.5 * a + 7.
    • Use another pointer to find the largest index r such that ages[r] <= a.
    • The number of valid requests for this person is r - l (excluding self).
  3. Sum the valid requests for all people.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        sort(ages.begin(), ages.end());
        int ans = 0, n = ages.size();
        for (int i = 0; i < n; ++i) {
            int a = ages[i];
            int l = upper_bound(ages.begin(), ages.end(), 0.5 * a + 7) - ages.begin();
            int r = upper_bound(ages.begin(), ages.end(), a) - ages.begin();
            if (r > l + 1) ans += r - l - 1;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

type Solution struct{}
func (Solution) numFriendRequests(ages []int) int {
    sort.Ints(ages)
    ans, n := 0, len(ages)
    for i := 0; i < n; i++ {
        a := ages[i]
        l := sort.SearchInts(ages, int(0.5*float64(a)+7.1)+1)
        r := sort.SearchInts(ages, a+1)
        if r > l+1 {
            ans += r - l - 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int numFriendRequests(int[] ages) {
        Arrays.sort(ages);
        int ans = 0, n = ages.length;
        for (int i = 0; i < n; i++) {
            int a = ages[i];
            int l = upperBound(ages, (int)(0.5 * a + 7));
            int r = upperBound(ages, a);
            if (r > l + 1) ans += r - l - 1;
        }
        return ans;
    }
    private int upperBound(int[] arr, int val) {
        int l = 0, r = arr.length;
        while (l < r) {
            int m = (l + r) / 2;
            if (arr[m] <= val) l = m + 1;
            else r = m;
        }
        return l;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun numFriendRequests(ages: IntArray): Int {
        ages.sort()
        var ans = 0
        for (i in ages.indices) {
            val a = ages[i]
            val l = ages.upperBound((0.5 * a + 7).toInt())
            val r = ages.upperBound(a)
            if (r > l + 1) ans += r - l - 1
        }
        return ans
    }
    private fun IntArray.upperBound(x: Int): Int {
        var l = 0; var r = size
        while (l < r) {
            val m = (l + r) / 2
            if (this[m] <= x) l = m + 1 else r = m
        }
        return l
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def numFriendRequests(self, ages: list[int]) -> int:
        ages.sort()
        ans = 0
        n = len(ages)
        for i, a in enumerate(ages):
            l = self.upper_bound(ages, 0.5 * a + 7)
            r = self.upper_bound(ages, a)
            if r > l + 1:
                ans += r - l - 1
        return ans
    def upper_bound(self, arr: list[int], val: float) -> int:
        l, r = 0, len(arr)
        while l < r:
            m = (l + r) // 2
            if arr[m] <= val:
                l = m + 1
            else:
                r = m
        return l
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
    pub fn num_friend_requests(mut ages: Vec<i32>) -> i32 {
        ages.sort();
        let n = ages.len();
        let mut ans = 0;
        for i in 0..n {
            let a = ages[i];
            let l = upper_bound(&ages, (0.5 * a as f64 + 7.0) as i32);
            let r = upper_bound(&ages, a);
            if r > l + 1 {
                ans += (r - l - 1) as i32;
            }
        }
        ans
    }
}
fn upper_bound(arr: &Vec<i32>, val: i32) -> usize {
    let (mut l, mut r) = (0, arr.len());
    while l < r {
        let m = (l + r) / 2;
        if arr[m] <= val {
            l = m + 1;
        } else {
            r = m;
        }
    }
    l
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
  numFriendRequests(ages: number[]): number {
    ages.sort((a, b) => a - b);
    let ans = 0;
    for (let i = 0; i < ages.length; i++) {
      const a = ages[i];
      const l = this.upperBound(ages, 0.5 * a + 7);
      const r = this.upperBound(ages, a);
      if (r > l + 1) ans += r - l - 1;
    }
    return ans;
  }
  upperBound(arr: number[], val: number): number {
    let l = 0, r = arr.length;
    while (l < r) {
      const m = (l + r) >> 1;
      if (arr[m] <= val) l = m + 1;
      else r = m;
    }
    return l;
  }
}

Complexity

  • ⏰ Time complexity: O(n log n), due to sorting and binary search for each person.
  • 🧺 Space complexity: O(1), ignoring the space for sorting.