You have a movie renting company consisting of n shops. You want to implement a renting system that supports searching for, booking, and returning movies. The system should also support generating a report of the currently rented movies.
Each movie is given as a 2D integer array entries where entries[i] = [shopi, moviei, pricei] indicates that there is a copy of movie moviei at shop shopi with a rental price of pricei. Each shop carries at most one copy of a movie moviei.
The system should support the following functions:
shopi should appear first. If there are less than 5 matching shops, then all of them should be returned. If no shop has an unrented copy, then an empty list should be returned.res where res[j] = [shopj, moviej] describes that the jth cheapest rented movie moviej was rented from the shop shopj. The movies in res should be sorted by price in ascending order, and in case of a tie, the one with the smaller shopj should appear first, and if there is still tie, the one with the smaller moviej should appear first. If there are fewer than 5 rented movies, then all of them should be returned. If no movies are currently being rented, then an empty list should be returned.Implement the MovieRentingSystem class:
MovieRentingSystem(int n, int[][] entries) Initializes the MovieRentingSystem object with n shops and the movies in entries.List<Integer> search(int movie) Returns a list of shops that have an unrented copy of the given movie as described above.void rent(int shop, int movie) Rents the given movie from the given shop.void drop(int shop, int movie) Drops off a previously rented movie at the given shop.List<List<Integer>> report() Returns a list of cheapest rented movies as described above.Note: The test cases will be generated such that rent will only be called if the shop has an unrented copy of the movie, and drop will only be called if the shop had previously rented out the movie.
Example 1:
Input ["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"] [[3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]], [1], [0, 1], [1, 2], [], [1, 2], [2]] Output [null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]] Explanation MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]); movieRentingSystem.search(1); // return [1, 0, 2], Movies of ID 1 are unrented at shops 1, 0, and 2. Shop 1 is cheapest; shop 0 and 2 are the same price, so order by shop number. movieRentingSystem.rent(0, 1); // Rent movie 1 from shop 0. Unrented movies at shop 0 are now [2,3]. movieRentingSystem.rent(1, 2); // Rent movie 2 from shop 1. Unrented movies at shop 1 are now [1]. movieRentingSystem.report(); // return [[0, 1], [1, 2]]. Movie 1 from shop 0 is cheapest, followed by movie 2 from shop 1. movieRentingSystem.drop(1, 2); // Drop off movie 2 at shop 1. Unrented movies at shop 1 are now [1,2]. movieRentingSystem.search(2); // return [0, 1]. Movies of ID 2 are unrented at shops 0 and 1. Shop 0 is cheapest, followed by shop 1.
Constraints:
1 <= n <= 3 * 1051 <= entries.length <= 1050 <= shopi < n1 <= moviei, pricei <= 104moviei.105 calls in total will be made to search, rent, drop and report.Problem Overview: You need to design a movie rental system that tracks which shop rents which movie and at what price. The system must support four operations: search(movie) to find the cheapest shops with that movie, rent(shop, movie), drop(shop, movie), and report() to list the cheapest currently rented movies.
Approach 1: HashMap + Ordered Set / SortedList (O(log n) per update)
This approach models the system using multiple hash maps and ordered sets. Maintain a HashMap mapping (shop, movie) to price for quick lookup. For the search operation, store all available copies of a movie in an ordered structure (such as SortedList or TreeSet) sorted by (price, shop). When a movie is rented, remove the entry from the movie's available set and insert it into another ordered set tracking currently rented movies sorted by (price, shop, movie). Because ordered sets maintain sorted order automatically, retrieving the cheapest 5 results becomes a simple iteration over the first elements. Each insert or delete costs O(log n), while lookups are O(1) using a hash table. Space complexity is O(n) for storing all movie-shop relationships.
Approach 2: Priority Queues + HashSet with Lazy Deletion (O(log n) amortized)
Another design uses priority queues to track the cheapest entries. Each movie maintains a min-heap ordered by (price, shop). The global rented list is another heap ordered by (price, shop, movie). Since heaps do not support efficient removal of arbitrary elements, track rental state using a HashSet. When an item is rented or dropped, update the set and push the new state into the heap instead of deleting old entries. During search or report, repeatedly pop invalid entries until the top of the heap matches the current state. This technique is called lazy deletion. Heap operations take O(log n), and invalid entries are discarded amortized over future operations. Space complexity remains O(n) because multiple heap entries may temporarily exist.
Both designs rely heavily on efficient ordering and fast lookups. Data structures like ordered sets or heaps ensure the system can always retrieve the cheapest available or rented movies without scanning the entire dataset.
Recommended for interviews: The HashMap + ordered set design is usually the cleanest and easiest to reason about. It provides deterministic O(log n) updates and direct removal of elements. The heap + lazy deletion approach demonstrates deeper understanding of priority queues and is useful when ordered sets are unavailable in the language.
This approach utilizes hash maps to store the details of available movies per shop and uses a sorted list to efficiently manage and sort rented movies. We will use a map to keep track of unrented movies per movie ID with the shop details, and a separate sorted list to maintain the currently rented movies for easy sorting and reporting.
The solution uses the SortedList from sortedcontainers in Python to maintain the rented movies in a sorted order based on price, shop, and movie IDs. The available movies are stored in a dictionary with movie IDs as keys and a SortedList to keep shop prices ordered for efficient searching and renting operations.
Time Complexity: O(log n) for rent and drop, O(1) for search and report. Space Complexity: O(m + r) where m is the number of movies and r is the number of rented records.
This approach leverages priority queues to efficiently manage the ordering of movies by price. For managing rented movies, a priority queue is used alongside a hash set to quickly verify current rentals. This structure facilitates rapid data retrieval and updates when executing search and report operations.
The C++ solution employs unordered maps to track available movies and their details, while priority queues maintain the sorted order for both available and rented movies. This setup allows efficient access to the top entries for search and report operations, leveraging the hash set to verify current rentals efficiently.
C++
JavaScript
Time Complexity: O(log n) for rent, drop, and report with heap operations. Space Complexity: O(m + r) where m is the count of unrented entries and r is rented entries.
We define an ordered set available, where available[movie] stores a list of all shops that have not rented out the movie movie. Each element in the list is (price, shop), sorted in ascending order by price, and if prices are equal, by shop in ascending order.
Additionally, we define a hash map price_map, where price_map[f(shop, movie)] stores the rental price of movie movie in shop shop.
We also define an ordered set rented, which stores all rented movies as (price, shop, movie), sorted in ascending order by price, then by shop, and if both are equal, by movie.
For the MovieRentingSystem(n, entries) operation, we iterate through entries and add each shop's movie information to both available and price_map. The time complexity is O(m log m), where m is the length of entries.
For the search(movie) operation, we return the shop IDs of the first 5 shops in available[movie]. The time complexity is O(1).
For the rent(shop, movie) operation, we remove (price, shop) from available[movie] and add (price, shop, movie) to rented. The time complexity is O(log m).
For the drop(shop, movie) operation, we remove (price, shop, movie) from rented and add (price, shop) back to available[movie]. The time complexity is O(log m).
For the report() operation, we return the shop and movie IDs of the first 5 rented movies in rented. The time complexity is O(1).
The space complexity is O(m), where m is the length of entries.
| Approach | Complexity |
|---|---|
| Using HashMap and SortedList | Time Complexity: O(log n) for |
| Using Priority Queues and HashSet | Time Complexity: O(log n) for |
| Ordered Set | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap + Ordered Set / SortedList | O(log n) per rent/drop, O(log n + k) search/report | O(n) | Best when language provides TreeSet/SortedList for direct ordered operations |
| Priority Queues + HashSet (Lazy Deletion) | O(log n) amortized | O(n) | Useful when ordered sets are unavailable and heaps are easier to implement |
Design Movie Rental System | Detailed Analysis | Leetcode 1912 | codestorywithMIK • codestorywithMIK • 7,040 views views
Watch 9 more video solutions →Practice Design Movie Rental System with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor