Skip to main content
Talentd

Design Movie Rental System - Solution & Explanation

HardArrayHash TableDesignHeap (Priority Queue)20 min readAsked at: Amazon, Flipkart
Practice this problem

Problem Statement

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:

  • Search: Finds the cheapest 5 shops that have an unrented copy of a given movie. The shops should be sorted by price in ascending order, and in case of a tie, the one with the smaller 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.
  • Rent: Rents an unrented copy of a given movie from a given shop.
  • Drop: Drops off a previously rented copy of a given movie at a given shop.
  • Report: Returns the cheapest 5 rented movies (possibly of the same movie ID) as a 2D list 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 * 105
  • 1 <= entries.length <= 105
  • 0 <= shopi < n
  • 1 <= moviei, pricei <= 104
  • Each shop carries at most one copy of a movie moviei.
  • At most 105 calls in total will be made to search, rent, drop and report.

Approach Overview

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 1: Using HashMap and SortedList

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 2: Using Priority Queues and HashSet

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.

Code

C++JavaScript

C++

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Ordered Set

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using HashMap and SortedList

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.

Using Priority Queues and HashSet

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.

Ordered Set—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap + Ordered Set / SortedListO(log n) per rent/drop, O(log n + k) search/reportO(n)Best when language provides TreeSet/SortedList for direct ordered operations
Priority Queues + HashSet (Lazy Deletion)O(log n) amortizedO(n)Useful when ordered sets are unavailable and heaps are easier to implement

Video Solution

Design Movie Rental System | Detailed Analysis | Leetcode 1912 | codestorywithMIK • codestorywithMIK • 7,254 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Design Movie Rental System easy or hard?
Design Movie Rental System is classified as a Hard problem on LeetCode. The difficulty comes from maintaining multiple sorted views of the same data while supporting efficient updates for rent, drop, search, and report operations.
Design Movie Rental System Python/Java solution
Python implementations typically use dictionaries with SortedList from the sortedcontainers library, while Java solutions use HashMap and TreeSet. Both approaches maintain sorted entries by (price, shop, movie) and perform updates in O(log n) time.
How to solve Design Movie Rental System in O(n)?
The system cannot realistically achieve O(n) for all operations because results must stay sorted by price. Instead, the optimal design uses O(log n) updates with ordered sets or heaps. These structures maintain sorted order automatically without scanning the entire dataset.
What is the best approach for Design Movie Rental System?
The most practical solution uses a HashMap combined with ordered sets (TreeSet or SortedList). The hash map stores price lookups for (shop, movie), while ordered sets keep movies sorted by price and shop ID. This allows search, rent, drop, and report operations to run in O(log n) time while always returning the cheapest results.
Is Design Movie Rental System asked at Google/Amazon/Meta?
Design-heavy data structure problems like this commonly appear in interviews at companies such as Google, Amazon, and Meta. The question evaluates your ability to combine hash maps, heaps, and ordered structures to support efficient dynamic queries.
What data structure is used in Design Movie Rental System?
The core data structures include HashMap for constant-time lookups, ordered sets (TreeSet or SortedList) for maintaining sorted movie availability, and heaps (priority queues) for retrieving the cheapest items. Some implementations also use HashSet for lazy deletion tracking.
What is the time complexity of Design Movie Rental System?
Efficient implementations support rent and drop in O(log n) time due to ordered set or heap updates. The search and report operations return up to 5 items and typically run in O(log n + k) where k ≤ 5. Overall system space complexity is O(n) to store all shop–movie entries.

Ready to solve this problem?

Practice Design Movie Rental System with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays