This problem requires maintaining per-movie sorted availability and a global sorted rented list. The key is using array scanning for updates and hash tables for quick lookups. Efficiently handling searches, rentals, returns, and reports relies on combining these structures to preserve order and fast access.
Problem Statement
You are building a movie rental service across n shops. Each shop offers a limited set of movies, each with a fixed rental price. The system must efficiently handle searching for available copies, renting movies, returning them, and generating reports of rented movies.
The input includes a 2D array entries where each entry [shopi, moviei, pricei] represents a copy of movie moviei at shop shopi with price pricei. Each shop holds at most one copy of each movie. Implement a system that supports search(movieID), rent(shopID, movieID), drop(shopID, movieID), and report() operations under these constraints.
Examples
Example 1
Input: See original problem statement.
Output: See original problem statement.
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.
Solution Approach
Use per-movie availability sets
Maintain a sorted set or list for each movie that tracks all available copies. Sorting ensures search returns cheapest shops in order. Hash tables map movie IDs to these sets for fast access during search, rent, and drop operations.
Track rented movies in a global sorted structure
Maintain a sorted set of all currently rented movies keyed by price, then shop ID, then movie ID. This enables efficient report generation by quickly extracting the top rented movies without scanning all entries.
Combine array scanning with hash lookup for updates
When renting or dropping a movie, use the hash table to find the correct set quickly and update the sorted list. Array scanning ensures the order remains consistent, and hash lookups keep operations fast, preventing performance degradation under frequent queries.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity depends on the number of movies and shops and the efficiency of maintaining sorted sets. Search, rent, and drop are roughly O(log m) per operation using ordered sets, where m is number of copies of a movie. Space complexity depends on storing availability sets and rented lists, proportional to entries length.
What Interviewers Usually Probe
- Check if your solution maintains correct ordering when multiple shops have same price.
- Ensure that search, rent, drop, and report operations all meet performance requirements under 10^5 calls.
- Consider whether using built-in sorted structures or custom heaps impacts efficiency and correctness.
Common Pitfalls or Variants
Common pitfalls
- Failing to sort shops correctly in search when prices tie, leading to wrong shop order.
- Updating availability and rented sets incorrectly when a movie is rented or returned.
- Assuming each shop can hold multiple copies of the same movie, which violates constraints.
Follow-up variants
- Add support for bulk rentals and returns where multiple copies are rented or dropped at once.
- Track popularity of movies to generate a report of most rented movies instead of cheapest.
- Extend to handle dynamic price updates while preserving search and report order.
How GhostInterview Helps
- Provides pre-structured arrays and hash maps to implement search, rent, drop, and report efficiently.
- Identifies correct ordering logic for multiple shops with same movie price to avoid common mistakes.
- Generates examples and checks that operations maintain proper availability and rented sets consistently.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What data structures are best for Design Movie Rental System?
Use per-movie sorted sets for availability and a global sorted set for rented movies combined with hash maps for O(1) access.
How does array scanning help in this problem?
Array scanning ensures updates maintain proper order within the sorted sets, which is crucial for search and report correctness.
How do I handle multiple shops with same movie price?
Always sort by price first, then shop ID to guarantee consistent ordering for search and report results.
What is the expected performance for 10^5 operations?
Using sorted sets with hash lookups, each operation runs in O(log m) time where m is number of copies of a movie, keeping performance acceptable.
Can rented movies affect search results?
Yes, rented movies must be removed from availability sets immediately to prevent them from appearing in search results until returned.
Need direct help with Design Movie Rental System instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Design Movie Rental System from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Design a food rating system that tracks and updates ratings of foods, finding the highest rated items by cuisine.
Open problem page#2034 Stock Price FluctuationDesign an efficient algorithm for managing stock price fluctuations with incorrect and unordered data in a data stream.
Open problem page#2336 Smallest Number in Infinite SetDesign a data structure to handle the smallest missing element in an infinite set, with the ability to add and remove elements efficiently.
Open problem page