Some people will make friend requests. The list of their ages is given and ages[i] is the age of the ith person.
Person A will NOT friend request person B (B != A) if any of the following conditions are true:
age[B] <= 0.5 * age[A] + 7age[B] > age[A]age[B] > 100 && age[A] < 100
Otherwise, A will friend request B.
Note that if A requests B, B does not necessarily request A. Also, people will not friend request themselves.
How many total friend requests are made?
Example 1:
Input: [16,16] Output: 2 Explanation: 2 people friend request each other.
Example 2:
Input: [16,17,18] Output: 2 Explanation: Friend requests are made 17 -> 16, 18 -> 17.
Example 3:
Input: [20,30,100,110,120] Output: Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.
Notes:
-
1 <= ages.length <= 20000. -
1 <= ages[i] <= 120.
Idea 1. Two pointer, sort the array, right pointer to expand for age[A] until all same value with age[A] group together, left pointer to expand age[B], assum the example is like
b1b2b3aaa, the whole length d = right - left + 1 = 6, x = duplicates(ages[right]) = 3 for 3as, the total pairs would (d-x) * x + x*(x-1) = x(d-1), since duplicates can refer to each other, if there n duplicates, there are n*(n-1) pairs with direction.
Rule 1, age[B] <= 0.5 * age[A] + 7 -> age[B] > 0.5*age[A] + 7
2. age[B] > age[A] -> age[B] <= age[A] or age[A] >= age[B]
it means age[A] > 0.5*age[A] + 7 -> age[A] > 14 plus age[A] > age[B]
1 class Solution { 2 public int numFriendRequests(int[] ages) { 3 Arrays.sort(ages); 4 int result = 0; 5 6 for(int leftB = 0, rightA = 1; rightA < ages.length; ++rightA) { 7 while(leftB < rightA && ages[leftB] <= 0.5* ages[rightA] + 7) { 8 ++leftB; 9 } 10 11 if(leftB < rightA) { 12 int oldA = rightA; 13 while(rightA + 1 < ages.length && ages[rightA] == ages[rightA+1]) { 14 ++rightA; 15 } 16 17 int duplicates = rightA - oldA + 1; 18 if(ages[leftB] == ages[rightA]) { 19 duplicates += 1; 20 } 21 result += (rightA - leftB + 1 - duplicates) * duplicates + (duplicates * (duplicates-1)); 22 } 23 } 24 25 return result; 26 } 27 }
Time complexity: O(nlgn + n), O(nlgn) to sort, O(n) to scan
Space complexity: O(1) if modified the array is allowed
Idea 2. Age is in range [1, 120], can use count sort and prefix sum, bruteforce approach is to check all pairs, slight optimisatiion is counting sort and prefix sum of the counts in the order of age
Time complexity: O(A^2 + N), A = max(ages[i]), N = ages.length
Space complexity: O(A)
1 class Solution { 2 public int numFriendRequests(int[] ages) { 3 Map<Integer, Integer> count = new HashMap<>(); 4 for(int age: ages) { 5 count.put(age, count.getOrDefault(age, 0) + 1); 6 } 7 8 int result = 0; 9 for(int a: count.keySet()) { 10 for(int b: count.keySet()) { 11 if(b <= 0.5 * a + 7) { 12 continue; 13 } 14 if(b > a) { 15 continue; 16 } 17 if(b > 100 && a < 100) { 18 continue; 19 } 20 21 result += count.get(a) * count.get(b); 22 if(a == b) { 23 result -= count.get(a); 24 } 25 } 26 } 27 return result; 28 } 29 }
Idea 2.b use Map to count the occurence of ages, prefixsum array helps to build the counts between a and b (prefix[a] - prefix[0.5a+7]), as b > 0.5a + 7, exclusively, get the numbers between (ages[b], ages[a]), and count(ages[a]).
Time complexity: O(A + N)
Space complexity: O(A)
1 class Solution { 2 public int numFriendRequests(int[] ages) { 3 Map<Integer, Integer> counts = new HashMap<>(); 4 5 for(int age: ages) { 6 counts.put(age, counts.getOrDefault(age, 0) + 1); 7 } 8 9 int len = 121; 10 int[] prefix = new int[len]; 11 for(int i = 1; i < len; ++i) { 12 prefix[i] = prefix[i-1] + counts.getOrDefault(i, 0); 13 } 14 15 int result = 0; 16 for(int a = 15; a < len; ++a) { 17 int b = (int)(0.5*a + 7); 18 result += (prefix[a] - prefix[b] - 1) * counts.getOrDefault(a, 0); 19 } 20 21 return result; 22 } 23 }
build counts array, instead of map
1 class Solution { 2 public int numFriendRequests(int[] ages) { 3 int len = 121; 4 int[] counts = new int[len]; 5 6 for(int age: ages) { 7 ++counts[age]; 8 } 9 10 int[] prefix = new int[len]; 11 for(int i = 1; i < len; ++i) { 12 prefix[i] = prefix[i-1] + counts[i]; 13 } 14 15 int result = 0; 16 for(int a = 15; a < len; ++a) { 17 int b = (int)(0.5*a + 7); 18 result += (prefix[a] - prefix[b] - 1) * counts[a]; 19 } 20 21 return result; 22 } 23 }