Approach #1: Counting [Accepted]

Intuition

Instead of processing all 20000 people, we can process pairs of (age, count) representing how many people are that age. Since there are only 120 possible ages, this is a much faster loop.

Algorithm

For each pair (ageA, countA), (ageB, countB), if the conditions are satisfied with respect to age, then countA * countB pairs of people made friend requests.

If ageA == ageB, then we overcounted: we should have countA * (countA - 1) pairs of people making friend requests instead, as you cannot friend request yourself.

Complexity Analysis

  • Time Complexity: , where is the number of people, and is the number of ages.

  • Space Complexity: , the space used to store count.


Analysis written by: @awice.