825. Friends Of Appropriate Ages

Array Two Pointers Binary Search Sorting

Time: O(n + 120²)

Space: O(120)

Intuition

For a person A to friend B: age[B] ≤ 0.5*age[A]+7 must be false, age[B] > age[A] must be false, age[B] > 100 and age[A] < 100 must be false. Count valid pairs.

Algorithm

1Sort ages. For each pair (A,B) with A!=B, check the 3 conditions.
2Or: use frequency count by age (1-120). For each age pair (a,b), count[a]*count[b] pairs (minus if a==b, subtract count[a] for self-friending).

Common Pitfalls

•The condition simplifies to: age[B] > 0.5*age[A]+7 AND age[B] ≤ age[A]. Persons don't friend themselves.

825.cs

// Approach: Build a frequency array for ages 1–120; use an O(120²) nested loop to count valid friend requests by the age condition.
// Time: O(n + 120²) Space: O(120)

public class Solution
{
    public int NumFriendRequests(int[] ages)
    {
        int ans = 0;
        int[] count = new int[121];

        foreach (int age in ages)
            ++count[age];

        for (int ageA = 1; ageA <= 120; ++ageA)
        {
            for (int ageB = 1; ageB <= 120; ++ageB)
            {
                int countA = count[ageA];
                int countB = count[ageB];
                if (countA > 0 && countB > 0 && Request(ageA, ageB))
                {
                    if (ageA == ageB)
                        ans += countA * (countB - 1);
                    else
                        ans += countA * countB;
                }
            }
        }

        return ans;
    }

    private bool Request(int ageA, int ageB)
    {
        return !(ageB <= 0.5 * ageA + 7 || ageB > ageA || ageB > 100 && ageA < 100);
    }
}

Was this solution helpful?