#825

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Friends Of Appropriate Ages

The Friends Of Appropriate Ages problem involves counting valid friend requests between people based on their ages with a focus on binary search.

array two pointers binary search sorting

Problem Statement

You are given an array of integers, ages, representing the ages of individuals on a social media platform. A person x will not send a friend request to a person y if any of the following conditions are true: y's age is less than 0.5 * x's age + 7 or y's age is greater than x's age, or y's age is greater than 100 and x's age is less than 100. Otherwise, a valid friend request can be made.

Your task is to count how many friend requests can be made within the given array of ages by ensuring each pair of individuals satisfies the conditions outlined. The goal is to compute this efficiently, especially given the constraints on the number of people (up to 20,000).

Examples

Example 1

Input: ages = [16,16]

Output: 2

2 people friend request each other.

Example 2

Input: ages = [16,17,18]

Output: 2

Friend requests are made 17 -> 16, 18 -> 17.

Example 3

Input: ages = [20,30,100,110,120]

Output: 3

Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

Constraints

n == ages.length
1 <= n <= 2 * 104
1 <= ages[i] <= 120

Solution Approach

Sort and Binary Search

The first step in the solution is to sort the array of ages. Once sorted, we can use binary search to efficiently determine the valid range of friend requests for each person. This significantly reduces the number of comparisons required compared to a brute force approach.

Two Pointers for Counting

After sorting the array, we use a two-pointer technique. For each person x, we can find the range of people whose ages allow them to send a request to x using the binary search results. The two-pointer method helps to count valid pairs efficiently.

Final Calculation of Requests

For each person in the array, once we have the valid range of ages that can send requests to them, we simply multiply the number of people within that range by the number of people to whom they can send requests. This allows us to count the total number of valid friend requests.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(n log n) due to the sorting step, followed by O(n log n) for binary searches, leading to an overall time complexity of O(n log n). The space complexity is O(n) due to the storage requirements for the sorted array and the auxiliary space used by the binary search.

What Interviewers Usually Probe

Candidate demonstrates understanding of binary search and two-pointer techniques.
Candidate suggests sorting as a first step for optimization.
Candidate efficiently calculates the number of valid requests without resorting to brute force.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle edge cases, such as when people have very young or very old ages.
Incorrectly calculating the valid age range for friend requests, especially when ages are close to boundaries.
Attempting to brute force the solution without leveraging sorting and binary search for optimization.

Follow-up variants

Implement a solution without sorting the array, using only binary search to determine valid pairs.
Modify the problem to allow for weighted age differences when determining valid requests.
Adapt the problem for real-time computations with streaming data, requiring constant updates to the array of ages.

FAQ

How can binary search be used in Friends Of Appropriate Ages?

Binary search helps by efficiently finding the range of ages that can send a friend request to a given person. This reduces the number of comparisons needed, speeding up the solution.

Why is sorting necessary in Friends Of Appropriate Ages?

Sorting helps arrange the ages in increasing order, making it easier to apply binary search and use two pointers to efficiently count valid pairs.

What are common mistakes in solving Friends Of Appropriate Ages?

Common mistakes include neglecting to handle edge cases, making incorrect age comparisons, and failing to optimize the solution with sorting and binary search.

How does GhostInterview optimize the solving process?

GhostInterview helps by providing focused guidance on sorting, binary search, and two-pointer techniques, allowing you to quickly implement an efficient solution.

Can the problem be solved without sorting the array?

While it is possible to solve the problem without sorting, using sorting and binary search is the most efficient approach for this problem, reducing time complexity.

terminal

Solution

Solution 1: Counting + Enumeration

We can use an array $\textit{cnt}$ of length $121$ to record the number of people of each age.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        cnt = [0] * 121
        for x in ages:
            cnt[x] += 1
        ans = 0
        for ax, x in enumerate(cnt):
            for ay, y in enumerate(cnt):
                if not (ay <= 0.5 * ax + 7 or ay > ax or (ay > 100 and ax < 100)):
                    ans += x * (y - int(ax == ay))
        return ans

Continue Practicing

#826 most profit assigning work #786 k th smallest prime fraction #719 find k th smallest pair distance