Watch 10 video solutions for Design Movie Rental System, a hard level problem involving Array, Hash Table, Design. This walkthrough by codestorywithMIK has 7,040 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |