825. Friends Of Appropriate Ages #

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+ 7
age[y] > age[x]
age[y] > 100 && age< 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^4
1 <= ages[i] <= 120

Problem Summary #

There are n users on a social media website. You are given an integer array ages, where ages[i] is the age of the ith user.

If any of the following conditions is true, then user x will not send a friend request to user y (x != y):

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

Otherwise, x will send a friend request to y. Note that if x sends a friend request to y, y does not necessarily have to send a friend request to x. Also, users will not send friend requests to themselves. Return the total number of friend requests made on this social media website.

Solution Ideas #

Solution 3: brute force. First count the number of people of each age in the range [1,120]. Then use the three conditions in the problem to filter the valid user pairs. Note that people of the same age can send friend requests to each other. Friend requests between people of different ages are one-way: older people send friend requests to younger people, while younger people will not send friend requests to older people.
Solution 2: sorting + two pointers. The 3 conditions given in the problem are actually 2 conditions. Condition 3 is included in condition 2. Combining condition 1 and condition 2 gives 0.5 × ages[x]+7 < ages[y] ≤ ages[x]. When ages is less than 15, this inequality has no solution. Considering that ages are monotonically increasing, the left and right boundaries of the interval (0.5 × ages[x]+7,ages[x]] are also monotonically increasing. Therefore, two pointers can be used to maintain the two boundaries. Within the interval [left, right], all y values corresponding to these indices satisfy the conditions. When ages[left] > 0.5 × ages[x]+7, the left pointer stops moving right. When ages[right+1] > ages[x], the right pointer stops moving right. Within the [left, right] interval, there are right-left+1 y values satisfying the conditions, meaning ages[y] takes values between (0.5 × ages[x]+7,ages[x]]. According to the problem statement, x≠y, so the right boundary of this interval cannot be taken. The number of possible y values needs to be decreased by one, subtracting the index where the value is the same as x. Thus each interval can take right-left values. Accumulating all valid values gives the total number of friend requests.
Solution 1. In Solution 2, when calculating the interval containing the indices of y that satisfy the inequality, intervals may overlap, and these overlaps lead to duplicate calculations. So we can optimize here. A prefix sum array can be used for optimization. See the code below.

Code #

package leetcocde

import "sort"

// Solution 1: prefix sum, time complexity O(n)
func numFriendRequests(ages []int) int {
	count, prefixSum, res := make([]int, 121), make([]int, 121), 0
	for _, age := range ages {
		count[age]++
	}
	for i := 1; i < 121; i++ {
		prefixSum[i] = prefixSum[i-1] + count[i]
	}
	for i := 15; i < 121; i++ {
		if count[i] > 0 {
			bound := i/2 + 8
			res += count[i] * (prefixSum[i] - prefixSum[bound-1] - 1)
		}
	}
	return res
}

// Solution 2: two pointers + sorting, time complexity O(n logn)
func numFriendRequests1(ages []int) int {
	sort.Ints(ages)
	left, right, res := 0, 0, 0
	for _, age := range ages {
		if age < 15 {
			continue
		}
		for ages[left]*2 <= age+14 {
			left++
		}
		for right+1 < len(ages) && ages[right+1] <= age {
			right++
		}
		res += right - left
	}
	return res
}

// Solution 3: brute force O(n^2)
func numFriendRequests2(ages []int) int {
	res, count := 0, [125]int{}
	for _, x := range ages {
		count[x]++
	}
	for i := 1; i <= 120; i++ {
		for j := 1; j <= 120; j++ {
			if j > i {
				continue
			}
			if (j-7)*2 <= i {
				continue
			}
			if j > 100 && i < 100 {
				continue
			}
			if i != j {
				res += count[i] * count[j]
			} else {
				res += count[i] * (count[j] - 1)
			}
		}
	}
	return res
}