#1912

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Design Movie Rental System

Implement a movie rental system with efficient search, rent, drop, and report operations using arrays and hash lookups.

array hash table design heap priority queue ordered set

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.

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.

terminal

Solution

Solution 1: Ordered Set

We define an ordered set $\textit{available}$, where $\textit{available}[movie]$ stores a list of all shops that have not rented out the movie $movie$. Each element in the list is $(\textit{price}, \textit{shop})$, sorted in ascending order by $\textit{price}$, and if prices are equal, by $\textit{shop}$ in ascending order.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

class MovieRentingSystem:

    def __init__(self, n: int, entries: List[List[int]]):
        self.available = defaultdict(lambda: SortedList())
        self.price_map = {}
        for shop, movie, price in entries:
            self.available[movie].add((price, shop))
            self.price_map[self.f(shop, movie)] = price
        self.rented = SortedList()

    def search(self, movie: int) -> List[int]:
        return [shop for _, shop in self.available[movie][:5]]

    def rent(self, shop: int, movie: int) -> None:
        price = self.price_map[self.f(shop, movie)]
        self.available[movie].remove((price, shop))
        self.rented.add((price, shop, movie))

    def drop(self, shop: int, movie: int) -> None:
        price = self.price_map[self.f(shop, movie)]
        self.rented.remove((price, shop, movie))
        self.available[movie].add((price, shop))

    def report(self) -> List[List[int]]:
        return [[shop, movie] for _, shop, movie in self.rented[:5]]

    def f(self, shop: int, movie: int) -> int:
        return shop << 30 | movie


# Your MovieRentingSystem object will be instantiated and called as such:
# obj = MovieRentingSystem(n, entries)
# param_1 = obj.search(movie)
# obj.rent(shop,movie)
# obj.drop(shop,movie)
# param_4 = obj.report()

Continue Practicing

#2353 design a food rating system #2034 stock price fluctuation #2336 smallest number in infinite set