Problem Description

This LeetCode problem presents a scenario in which you are required to design a system for a movie rental company that manages several shops. The system should be capable of performing actions such as searching for available copies of a movie to rent, booking (renting) a movie, returning (dropping) a movie, and generating a report of the currently rented movies.

For this system, each movie available for rent is recorded as an entry consisting of the shop number, movie number, and rental price. The challenge is to implement these features while making sure that shop and movie data are handled efficiently for rapid searching, renting, dropping, and reporting activities.

Key functionalities to be supported:

• Search: Find the cheapest 5 shops (or fewer, if less are available) with available copies of a specific movie to rent. The shops should be sorted primarily by ascending price, then by shop number if prices are identical.

• Rent: Book an available movie from a specific shop.

• Drop: Return a rented movie to a specific shop.

• Report: Generate a list of the cheapest 5 rented movies (or fewer, if less are rented) across all shops, sorted primarily by ascending price, then by shop number, and finally by movie number in case of ties.

The main obstacle is to manage the storage and retrieval of movie data to ensure the operations can be executed efficiently and meet the problem's requirements.

Intuition

The intuition behind solving this problem lies in efficiently managing the data regarding shop inventories and movie rentals. This involves carefully selecting data structures that will allow for fast lookups, insertions, and deletions, which are critical for the operations that the system needs to perform.

Here's the rationale for the solution approach:

• Use a sorted data structure to maintain the availability and price of unrented movies. This enables us to efficiently search for the cheapest available movies and sort them as required. Python's SortedList, which is part of the sortedcontainers library, is an excellent choice for this task because it maintains sorted order upon insertion and deletion, allowing for efficient operations that conform to the problem's specifications.

• Maintain a mapping that relates each unique shop and movie pair to their corresponding rental price. This helps quickly reference the price when a movie is rented or returned.

• Keep another sorted list to track all rented movies. This list is sorted by price, and further by shop and movie numbers when prices are the same, fulfilling the reporting requirement to list rented movies in the desired order.

Using these data structures and maintaining these relationships allows the MovieRenting System to perform search, rent, drop, and report operations as per the given constraints and return the correct results.

The provided Python solution demonstrates implementing this approach with class methods corresponding to the required functionalities.

Learn more about Heap (Priority Queue) patterns.

Solution Approach

The solution is implemented using the MovieRentingSystem class, which maintains three primary data structures to manage unrented and rented movies along with their prices:

1. self.unrented - A dictionary with keys as movie IDs and values as SortedList objects that hold tuples of (price, shop). This allows keeping the unrented copies of each movie sorted by price (then by shop in case of a tie). The SortedList is suitable for this purpose because it provides efficient O(log n) insertion and removal along with the ability to retrieve the smallest elements, i.e., the cheapest movies.

2. self.shopAndMovieToPrice - A dictionary to track the price of renting each movie from each shop. The keys are tuples of (shop, movie), and values are the prices. This provides an O(1) lookup for the price when a movie is rented or dropped.

3. self.rented - A SortedList that maintains all the rented movie data as tuples of (price, shop, movie). Since the list is sorted, this again provides efficient operations and supports getting the cheapest rented movies for the report.

The class methods implement the functionalities as follows:

• __init__ initializes the system with the given number of shops and movie entries. It populates the self.unrented and self.shopAndMovieToPrice data structures using the entries array.

• search method takes a movie ID as an argument and returns a list of up to 5 shop numbers offering the cheapest unrented copies of the movie, sorted by price.

• rent method takes shop and movie IDs and performs the rental operation. It looks up the rental price using self.shopAndMovieToPrice, removes the movie from self.unrented, and adds the rental information to self.rented.

• drop method is the inverse operation of the rent method. It reinstates the movie to self.unrented and removes it from self.rented, assuming the movie is dropped off at the same shop from where it was rented.

• report method returns a list of the cheapest 5 (or fewer, if fewer are available) rented movies. It does so by retrieving the first 5 elements from the self.rented list, which are kept sorted by price, and then by shop and movie where needed.

The algorithms employed for the data manipulations within these methods take full advantage of the properties of the SortedList structure (from the sortedcontainers library), which keeps elements sorted automatically. This ensures efficient performance and correctness of the implemented system.

Example Walkthrough

Let's illustrate the solution approach using a small example: Imagine we have a movie rental system with two shops (Shop 1 and Shop 2). Each shop has one copy of two movies (Movie A and Movie B) available for rent. Here are the starting rental prices for each movie at each shop:

• Shop 1: Movie A for $4, Movie B for$2
• Shop 2: Movie A for $3, Movie B for$5

With the MovieRentingSystem class, we initialize our system with these movie entries.

Initialization:

entries = [(1, 'A', 4), (1, 'B', 2), (2, 'A', 3), (2, 'B', 5)]

Here's how the system sets up the initial data structures upon running the __init__ method:

• self.unrented becomes a dictionary with keys as movie IDs and values as SortedList objects, like so:
  • 'A': [(3, 2), (4, 1)] - sorted by price, then by shop number.
  • 'B': [(2, 1), (5, 2)]
• self.shopAndMovieToPrice becomes:
  • {(1, 'A'): 4, (1, 'B'): 2, (2, 'A'): 3, (2, 'B'): 5}
• self.rented is initially empty since no movie has been rented yet: SortedList().

Search Operation: Let's find the cheapest shops to rent Movie A.

movie_renting_system.search('A')

The search method looks up 'A' in self.unrented dictionary and returns the first 5 (or all, if fewer) tuples, sorted by price:

• Output: [(3, 2), (4, 1)] - Shop 2 offers the cheapest price for Movie A at $3, and Shop 1 offers it at$4.

Rent Operation: Suppose we want to rent Movie A from Shop 2.

movie_renting_system.rent(2, 'A')

The rent method does the following:

• It removes (3, 2) from self.unrented['A'], resulting in: 'A': [(4, 1)]
• It adds (3, 2, 'A') to self.rented, resulting in: [(3, 2, 'A')]

Drop Operation: After watching, we return Movie A to Shop 2.

movie_renting_system.drop(2, 'A')

The drop method essentially reverses the rent operation:

• It removes (3, 2, 'A') from self.rented.
• It adds (3, 2) back to self.unrented['A'], now it is: 'A': [(3, 2), (4, 1)] - automatically sorted.

Report Operation: If we now want to generate a report of the rented movies, we call:

movie_renting_system.report()

The report method reads from self.rented, which is currently empty because the rented movie was dropped off. Thus, the output at this point is an empty list.

This example demonstrates the solution's capability to handle various operations efficiently while accurately maintaining and updating the underlying data structures according to the problem specifications.

Solution Implementation

Time and Space Complexity

The given Python code defines a class MovieRentingSystem that keeps track of rented and unrented movies between various shops with their respective prices and implements methods to search, rent, drop, and report movies.

Space Complexity

• The space complexity for initializing the system is O(E) where E is the number of entries, considering that each entry is stored in self.unrented and self.shopAndMovieToPrice.

Time Complexity

• init method: For each entry, the add operation to self.unrented SortedList is O(logS) where S is the number of different movies in the worst case, and adding to self.shopAndMovieToPrice is O(1) making the overall complexity O(E * logS) for initializing the system.

• search method: Retrieving the top 5 movies is O(1) per movie but since we need to retrieve up to 5 it becomes O(5) or simply O(1) regardless of the number of movies because it's a constant-time operation due to the limitation of 5 shops.

• rent method: The remove operation from self.unrented[movie] is O(logS) since it's a portion of SortedList and adding the entry to self.rented is also O(logR) where R is the number of rented movies at the time. Thus, the time complexity for this method is O(logS + logR).

• drop method: Similar to the rent method, we have a remove operation from self.rented which is O(logR) and an add operation to self.unrented[movie] which is O(logS). Hence, the time complexity here is also O(logS + logR).

• report method: The generation of the report, which involves getting up to the top 5 entries, is O(1) since it doesn't depend on the size of the self.rented but is rather capped at 5.

Considering that S and R can vary independently, we should not simplify O(logS + logR) to O(log(S + R)) or any such combined form since they represent different aspects of the system's data.

Learn more about how to find time and space complexity quickly using problem constraints.