Solution
Notice that the third condition is obsolete as it is contained in the second condition. If age[B]>100 and age[A]<100 then age[B] > age[A] so by the second condition, A will not friend request B. So all we have to do is keep the first two conditions in mind. Now, the constraints mention that 1 <= ages[i] <= 120. We can simply have an array of length 121 (1-indexed rather than 0-indexed) which stores the count of people of age = i. So our array a will have a[i] = count(age = i). Then, for each age i, we can start from 0.5*i+8 to i and add the friend requests to the answer. Note the following:
- People younger than 15 cannot make requests due to the first rule (in the first condition, put age[A] = age[B] and solve for it).
- From the age of 15, people can make requests to the same age: a[i] * (a[i] - 1) requests.
- People can make requests to younger people older than 0.5 * i + 7: a[j] * a[i] requests.
int numFriendRequests(vector<int>& ages) { int a[121] = {}, res = 0; for (auto age : ages) ++a[age]; for (auto i = 15; i <= 120; ++i) for (int j = 0.5 * i + 8; j <= i; ++j) res += a[j] * (a[i] - (i == j)); return res; }
As mentioned by votrubac, we can optimize the counting by using a sliding sum of friend requests. Sliding sum for an age i is defined as sum starting at the minimum age (0.5 * i + 7) and ending at i. Let’s say for an age i, the sum stores number of people from ages h to i = a[h] + a[h+1] + … + a[i]. Now, total number of requests sent by a[i] = a[i]*a[h] + a[i]*a[h+1] + ... + a[i]*a[i-1] + a[i]*(a[i]-1) = a[i]*(a[h] + a[h+1] + ... + a[i-1] + a[i] - 1) = a[i]*(slidingSum - 1).
The complexity of optimized solution is O(n + m) vs. O(n + m * m), where m is the age range.
int numFriendRequests(vector<int>& ages) {
int a[121] = {}, res = 0;
for (auto age : ages) ++a[age];
for (auto i = 15, minAge = 15, sSum = 0; i <= 120; sSum += a[i], res += a[i++] * (sSum - 1))
while (minAge <= 0.5 * i + 7) sSum -= a[minAge++];
return res;
}