Approach #1: Counting [Accepted]
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.
For each pair
(ageB, countB), if the conditions are satisfied with respect to age, then
countA * countB pairs of people made friend requests.
ageA == ageB, then we overcounted: we should have
countA * (countA - 1) pairs of people making friend requests instead, as you cannot friend request yourself.
Time Complexity: , where is the number of people, and is the number of ages.
Space Complexity: , the space used to store
Analysis written by: @awice.