Unpopular Books - Leetcode Solution

Problem statement:

Given a list of book IDs and their frequency of reading, find the IDs of all books that are not read frequently and return them in ascending order.

Input:

• A list of integers representing the book IDs (1 ≤ bookIds[i] ≤ 10^6).
• A list of integers representing the frequency of reading each book (1 ≤ frequencies[i] ≤ 10^6).
• Length of both input lists is between 1 and 10^5.

Output:

• A list of integers representing the IDs of all books that are not frequently read.

Solution:

One way to solve the problem is to first find the maximum frequency of reading among all books. Then, iterate over the list of frequencies and add the IDs of books that have frequency less than the maximum to a set. Finally, convert the set to a list and sort it in ascending order.

Python code:

def unpopular_books(bookIds, frequencies):
    max_freq = max(frequencies)
    unpopular_set = set()
    for i in range(len(bookIds)):
        if frequencies[i] < max_freq:
            unpopular_set.add(bookIds[i])
    return sorted(list(unpopular_set))

Time Complexity: O(n log n) Space Complexity: O(n)

Explanation:

• The max() function takes O(n) time to find the maximum frequency.
• The for loop iterates over each item in the input lists, which takes O(n) time.
• The add() method of a set takes O(1) time on average, so adding n items to the set takes O(n) time.
• The sorted() function takes O(n log n) time to sort the list of unpopular IDs.
• Overall, the time complexity of the solution is O(n log n) due to the sorting operation.
• The space complexity is O(n) because the set can store up to n unpopular IDs.

1