algoadvance

Leetcode 825. Friends Of Appropriate Ages

Problem Statement

You are given an array ages where ages[i] is the age of the i-th person. A person A can send a friend request to person B if the following conditions are met:

  1. age[B] <= 0.5 * age[A] + 7
  2. age[B] > age[A]
  3. age[B] > 100 && age[A] < 100

Given these conditions, return the total number of friend requests made.

Clarifying Questions

  1. Are age[B] = age[A] requests allowed?
  2. Is there a maximum length for the ages array or any constraints on it?
  3. Does age start from any particular minimum age?
  4. If age[A] is 100 (or larger), and age[B] is 100 (or larger), are they allowed to send friend requests to each other?

Assuming the constraints are reasonably large (say up to a few thousand elements in ages and age ranges from 1 to 120).

Strategy

We will:

  1. Sort the array to handle age comparisons more efficiently.
  2. Iterate through the array, keeping track of the number of valid friends a particular person can send requests to using two pointers or binary search methods.

Code

import java.util.Arrays;

public class FriendsOfAppropriateAges {
    public int numFriendRequests(int[] ages) {
        // Sort the ages array to facilitate efficient range queries
        Arrays.sort(ages);
        int totalRequests = 0;
        
        for (int i = 0; i < ages.length; i++) {
            int ageA = ages[i];
            if (ageA < 15) continue; // No person with age < 15 can send any valid request
            
            // Find ageB's lower and upper bounds
            int minAgeB = ageA / 2 + 7;
            int maxAgeB = ageA;
            
            int countInRange = countInRange(ages, minAgeB, maxAgeB);
            totalRequests += (countInRange - 1); // Exclude self from the count
        }
        
        return totalRequests;
    }
    
    private int countInRange(int[] ages, int minAge, int maxAge) {
        return upperBound(ages, maxAge) - lowerBound(ages, minAge);
    }
    
    private int lowerBound(int[] ages, int minAge) {
        int left = 0, right = ages.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (ages[mid] > minAge) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
    private int upperBound(int[] ages, int maxAge) {
        int left = 0, right = ages.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (ages[mid] <= maxAge) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    public static void main(String[] args) {
        FriendsOfAppropriateAges solution = new FriendsOfAppropriateAges();
        int[] ages = {16, 17, 18};
        System.out.println(solution.numFriendRequests(ages));  // Output 2
    }
}

Time Complexity

Thus, the overall time complexity is (O(n \log n)).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI