825. Friends Of Appropriate Ages

Overview of the Approach

There are many approaches to solving this problem: 1) brute force, 2) using a dictionary, 3) sorting + finding a range 1, and 4) sorting + finding a range 2. In the below I provide the code and rationale for each solution. If you have tried solving the problem and struggled like me, I think it’d be helpful to review these solutions in order as they have been sorted in the order of increasing complexity.

Solution

Approach 1. Brute force

1. Code

class Solution {
    func numFriendRequests(_ ages: [Int]) -> Int {     
        var totalCount = 0

        for i in 0..<ages.count-1 {
            for j in i+1..<ages.count {
                if canFriendRequest(ages[i], ages[j]) {
                    totalCount += 1
                }
                if canFriendRequest(ages[j], ages[i]) {
                    totalCount += 1
                }
            }
        }

        return totalCount
    }

    private func canFriendRequest(_ age1: Int, _ age2: Int) -> Bool {
        if Double(age1) <= 0.5 * Double(age2) + 7 {
            return false
        }
        if age1 > age2 {
            return false
        }
        // skip the 3rd condition because the 2nd condition covers it
        return true
    }
}

2. Complexities
   • Time: O(N^2)
   • Space: O(1)
3. Rationale
   • This brute force solution simply scans through the ages array with nested for loops. Each iteration compares a pair of two ages at different possible indices and checks whether one array value can friend request the other and vice versa. This solution works but is too slow to pass the LeetCode submission.

Approach 2. Using a dictionary

1. Code

class Solution {
    func numFriendRequests(_ ages: [Int]) -> Int {     
        var totalCount = 0

        // 1. set up the age count dictionary
        var ageCounts = [Int: Int]()
        for age in ages {
            ageCounts[age, default: 0] += 1
        }

        // 2. iterate through the dictionary's keys
        for (age1, count1) in ageCounts {
            for (age2, count2) in ageCounts {
                // 3. for each pair of ages, handle these cases: 
                guard canFriendRequest(age1, age2) else { continue }
                if age1 == age2 {
                    totalCount += (count1-1) * count2
                } else {
                    totalCount += count1 * count2
                }
            }
        }

        return totalCount
    }

    private func canFriendRequest(_ age1: Int, _ age2: Int) -> Bool {
        if Double(age1) <= 0.5 * Double(age2) + 7 {
            return false
        }
        if age1 > age2 {
            return false
        }
        // skip the 3rd condition because the 2nd condition covers it
        return true
    }
}

2. Complexities
   • Time: O(N + M^2) where M is the number of unique ages in the array. Even though the second part is M^2, this is much better than N^2 because the number of unique ages is unlikely to be meaningfully big. In my view, this solution easy to follow and leaves less room for error when writing code.
   • Space: O(M) for the dictionary
3. Rationale
   • This solution uses the intuition that you can calculate how many friend requests will be made between two ages by multiplying their occurrences. This is different from the intuition used in the next two solutions.

Approach 3. Sorting + finding a range 1

1. Code

class Solution {
    func numFriendRequests(_ ages: [Int]) -> Int {        
        var result = 0, ages = ages.sorted()

        for i in 0..<ages.count {
            var j = 0
            while j < ages.count-1, !canFriendRequest(ages[j], ages[i]) {
                j += 1
            }

            var z = ages.count-1
            while z > 0, !canFriendRequest(ages[z], ages[i]) {
                z -= 1
            }

            let count = (z - j + 1) - 1
            if count > 0 {
                result += count
            }
        }

        return result
    }

    private func canFriendRequest(_ age1: Int, _ age2: Int) -> Bool {
        if Double(age1) <= 0.5 * Double(age2) + 7 {
            return false
        }
        if age1 > age2 {
            return false
        }
        // skip the 3rd condition because the 2nd condition covers it
        return true
    }    
}

2. Complexities
   • Time: O(N*logN + N^2) for sorting and iterating the sorted array.
   • Space: O(N) for storing the sorted ages array.
3. Rationale
   • This solution uses a nested loop approach too. The intuition used is that after you sort the array, you can simply find the minimum and maximum ages that the current age value can friend request to and then count and add the number of age values of the range. This solution is slower than the second approach using a dictionary.

Approach 4. Sorting + finding a range 2

1. Code

class Solution {
    func numFriendRequests(_ ages: [Int]) -> Int {        
        var result = 0, ages = ages.sorted()

        for i in 0..<ages.count {
            var lower = -1, upper = -1

            var left1 = 0, right1 = ages.count-1
            while left1 <= right1 {
                let mid = left1 + (right1-left1)/2
                if Double(ages[mid]) > (0.5 * Double(ages[i]) + 7) {
                    lower = mid
                    right1 = mid-1
                } else {
                    left1 = mid+1
                }
            }
            guard lower >= 0 else { continue }

            var left2 = 0, right2 = ages.count-1
            while left2 <= right2 {
                let mid = left2 + (right2-left2)/2
                if ages[mid] <= ages[i] {
                    upper = mid
                    left2 = mid+1
                } else {
                    right2 = mid-1
                }
            }

            let count = upper - lower + 1 - 1
            if count > 0 {
                result += count
            }
        }

        return result
    }    
}

2. Complexities
   • Time: O(NlogN + 2NlogN) = O(3NlogN) = O(NlogN) for sorting the array and iterating through the array with binary search
   • Space: O(N) for the sorted array
3. Rationale
   • This last solution upgrades the 3rd solution by using binary search for finding the range of valid age values in the sorted array. One tricky thing about this solution is that the canFriendRequest helper method works with the binary search logic so we need to use the insight that some of the conditions provided by the problem can be used for finding the lower bound and others for upper bound.

References

• Facebook Coding Interview Question | Leetcode 825 | Friends Of Appropriate Ages by WorkWithGoogler gives a great explanation for the dictionary approach.
• LeetCode solution by vikasvaish21