1912. Design Movie Rental System

HardDesignArrayHash TableOrdered SetHeap (Priority Queue)
Leetcode Link

Problem Description

This LeetCode problem presents a scenario in which you are required to design a system for a movie rental company that manages several shops. The system should be capable of performing actions such as searching for available copies of a movie to rent, booking (renting) a movie, returning (dropping) a movie, and generating a report of the currently rented movies.

For this system, each movie available for rent is recorded as an entry consisting of the shop number, movie number, and rental price. The challenge is to implement these features while making sure that shop and movie data are handled efficiently for rapid searching, renting, dropping, and reporting activities.

Key functionalities to be supported:

  • Search: Find the cheapest 5 shops (or fewer, if less are available) with available copies of a specific movie to rent. The shops should be sorted primarily by ascending price, then by shop number if prices are identical.

  • Rent: Book an available movie from a specific shop.

  • Drop: Return a rented movie to a specific shop.

  • Report: Generate a list of the cheapest 5 rented movies (or fewer, if less are rented) across all shops, sorted primarily by ascending price, then by shop number, and finally by movie number in case of ties.

The main obstacle is to manage the storage and retrieval of movie data to ensure the operations can be executed efficiently and meet the problem's requirements.

Intuition

The intuition behind solving this problem lies in efficiently managing the data regarding shop inventories and movie rentals. This involves carefully selecting data structures that will allow for fast lookups, insertions, and deletions, which are critical for the operations that the system needs to perform.

Here's the rationale for the solution approach:

  • Use a sorted data structure to maintain the availability and price of unrented movies. This enables us to efficiently search for the cheapest available movies and sort them as required. Python's SortedList, which is part of the sortedcontainers library, is an excellent choice for this task because it maintains sorted order upon insertion and deletion, allowing for efficient operations that conform to the problem's specifications.

  • Maintain a mapping that relates each unique shop and movie pair to their corresponding rental price. This helps quickly reference the price when a movie is rented or returned.

  • Keep another sorted list to track all rented movies. This list is sorted by price, and further by shop and movie numbers when prices are the same, fulfilling the reporting requirement to list rented movies in the desired order.

Using these data structures and maintaining these relationships allows the MovieRenting System to perform search, rent, drop, and report operations as per the given constraints and return the correct results.

The provided Python solution demonstrates implementing this approach with class methods corresponding to the required functionalities.

Learn more about Heap (Priority Queue) patterns.

Solution Approach

The solution is implemented using the MovieRentingSystem class, which maintains three primary data structures to manage unrented and rented movies along with their prices:

  1. self.unrented - A dictionary with keys as movie IDs and values as SortedList objects that hold tuples of (price, shop). This allows keeping the unrented copies of each movie sorted by price (then by shop in case of a tie). The SortedList is suitable for this purpose because it provides efficient O(log n) insertion and removal along with the ability to retrieve the smallest elements, i.e., the cheapest movies.

  2. self.shopAndMovieToPrice - A dictionary to track the price of renting each movie from each shop. The keys are tuples of (shop, movie), and values are the prices. This provides an O(1) lookup for the price when a movie is rented or dropped.

  3. self.rented - A SortedList that maintains all the rented movie data as tuples of (price, shop, movie). Since the list is sorted, this again provides efficient operations and supports getting the cheapest rented movies for the report.

The class methods implement the functionalities as follows:

  • __init__ initializes the system with the given number of shops and movie entries. It populates the self.unrented and self.shopAndMovieToPrice data structures using the entries array.

  • search method takes a movie ID as an argument and returns a list of up to 5 shop numbers offering the cheapest unrented copies of the movie, sorted by price.

  • rent method takes shop and movie IDs and performs the rental operation. It looks up the rental price using self.shopAndMovieToPrice, removes the movie from self.unrented, and adds the rental information to self.rented.

  • drop method is the inverse operation of the rent method. It reinstates the movie to self.unrented and removes it from self.rented, assuming the movie is dropped off at the same shop from where it was rented.

  • report method returns a list of the cheapest 5 (or fewer, if fewer are available) rented movies. It does so by retrieving the first 5 elements from the self.rented list, which are kept sorted by price, and then by shop and movie where needed.

The algorithms employed for the data manipulations within these methods take full advantage of the properties of the SortedList structure (from the sortedcontainers library), which keeps elements sorted automatically. This ensures efficient performance and correctness of the implemented system.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a small example: Imagine we have a movie rental system with two shops (Shop 1 and Shop 2). Each shop has one copy of two movies (Movie A and Movie B) available for rent. Here are the starting rental prices for each movie at each shop:

  • Shop 1: Movie A for 4,MovieBfor4, Movie B for 2
  • Shop 2: Movie A for 3,MovieBfor3, Movie B for 5

With the MovieRentingSystem class, we initialize our system with these movie entries.

Initialization:

1entries = [(1, 'A', 4), (1, 'B', 2), (2, 'A', 3), (2, 'B', 5)]

Here's how the system sets up the initial data structures upon running the __init__ method:

  • self.unrented becomes a dictionary with keys as movie IDs and values as SortedList objects, like so:
    • 'A': [(3, 2), (4, 1)] - sorted by price, then by shop number.
    • 'B': [(2, 1), (5, 2)]
  • self.shopAndMovieToPrice becomes:
    • {(1, 'A'): 4, (1, 'B'): 2, (2, 'A'): 3, (2, 'B'): 5}
  • self.rented is initially empty since no movie has been rented yet: SortedList().

Search Operation: Let's find the cheapest shops to rent Movie A.

1movie_renting_system.search('A')

The search method looks up 'A' in self.unrented dictionary and returns the first 5 (or all, if fewer) tuples, sorted by price:

  • Output: [(3, 2), (4, 1)] - Shop 2 offers the cheapest price for Movie A at 3,andShop1offersitat3, and Shop 1 offers it at 4.

Rent Operation: Suppose we want to rent Movie A from Shop 2.

1movie_renting_system.rent(2, 'A')

The rent method does the following:

  • It removes (3, 2) from self.unrented['A'], resulting in: 'A': [(4, 1)]
  • It adds (3, 2, 'A') to self.rented, resulting in: [(3, 2, 'A')]

Drop Operation: After watching, we return Movie A to Shop 2.

1movie_renting_system.drop(2, 'A')

The drop method essentially reverses the rent operation:

  • It removes (3, 2, 'A') from self.rented.
  • It adds (3, 2) back to self.unrented['A'], now it is: 'A': [(3, 2), (4, 1)] - automatically sorted.

Report Operation: If we now want to generate a report of the rented movies, we call:

1movie_renting_system.report()

The report method reads from self.rented, which is currently empty because the rented movie was dropped off. Thus, the output at this point is an empty list.

This example demonstrates the solution's capability to handle various operations efficiently while accurately maintaining and updating the underlying data structures according to the problem specifications.

Solution Implementation

1import collections
2from typing import List
3from sortedcontainers import SortedList
4
5class MovieRentingSystem:
6    def __init__(self, n: int, entries: List[List[int]]):
7        # Initialize a dictionary to hold unrented movies with each movie's price and shop info.
8        self.unrented_movies = collections.defaultdict(SortedList)  # {movie: (price, shop)}
9      
10        # A dictionary to map each shop and movie combo to its price.
11        self.price_lookup = {}  # {(shop, movie): price}
12      
13        # Initialize a SortedList to hold rented movies with their price, shop, and movie info.
14        self.rented_movies = SortedList()  # (price, shop, movie)
15      
16        # Fill dictionaries with initial entries.
17        for shop, movie, price in entries:
18            self.unrented_movies[movie].add((price, shop))
19            self.price_lookup[(shop, movie)] = price
20
21    def search(self, movie: int) -> List[int]:
22        # Return a list of shops that have the specified movie among the 5 cheapest options.
23        return [shop for _, shop in self.unrented_movies[movie][:5]]
24
25    def rent(self, shop: int, movie: int) -> None:
26        # Rent a movie by moving it from the unrented_movie list to the rented_movies list.
27        price = self.price_lookup[(shop, movie)]
28        self.unrented_movies[movie].remove((price, shop))
29        self.rented_movies.add((price, shop, movie))
30
31    def drop(self, shop: int, movie: int) -> None:
32        # Drop off a rented movie by moving it back from the rented_movies list to unrented_movies.
33        price = self.price_lookup[(shop, movie)]
34        self.unrented_movies[movie].add((price, shop))
35        self.rented_movies.remove((price, shop, movie))
36
37    def report(self) -> List[List[int]]:
38        # Report the 5 cheapest rented movies as a list of [shop, movie] pairs.
39        return [[shop, movie] for _, shop, movie in self.rented_movies[:5]]
40
41# End of the MovieRentingSystem class
42
43# The MovieRentingSystem class can be used as follows:
44# obj = MovieRentingSystem(n, entries)
45# available_shops = obj.search(movie)
46# obj.rent(shop, movie)
47# obj.drop(shop, movie)
48# report = obj.report()
49
1import java.util.*;
2
3class MovieRentingSystem {
4    // A map to hold unrented movies with each movie's price and shop info.
5    private TreeMap<Integer, TreeSet<int[]>> unrentedMovies;
6  
7    // A map to track the price for each shop and movie combination.
8    private Map<Integer, Integer> priceLookup;
9  
10    // A SortedSet to hold rented movies with their price, shop, and movie info.
11    private TreeSet<int[]> rentedMovies;
12
13    public MovieRentingSystem(int n, int[][] entries) {
14        unrentedMovies = new TreeMap<>();
15        priceLookup = new HashMap<>();
16        rentedMovies = new TreeSet<>(
17            (a, b) -> {
18                if (a[0] != b[0]) return a[0] - b[0]; // First sort by price
19                if (a[1] != b[1]) return a[1] - b[1]; // Then by shop
20                return a[2] - b[2]; // Finally by movie
21            }
22        );
23      
24        for (int[] entry : entries) {
25            int shop = entry[0];
26            int movie = entry[1];
27            int price = entry[2];
28          
29            int[] shopPricePair = new int[]{price, shop};
30            unrentedMovies.computeIfAbsent(movie, x -> new TreeSet<>(
31                (a, b) -> {
32                    if (a[0] != b[0]) return a[0] - b[0]; // Sort by price
33                    return a[1] - b[1]; // Then by shop
34                }
35            )).add(shopPricePair);
36          
37            priceLookup.put(shop * 10001 + movie, price); // Composite key to map uniquely to every shop and movie combination
38        }
39    }
40
41    // Return a list of shops that have the specified movie among the 5 cheapest options.
42    public List<Integer> search(int movie) {
43        List<Integer> shops = new ArrayList<>();
44        if (!unrentedMovies.containsKey(movie)) return shops;
45      
46        for (int[] pair : unrentedMovies.get(movie).headSet(new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE}, true)) {
47            shops.add(pair[1]);
48            if (shops.size() == 5) break;
49        }
50      
51        return shops;
52    }
53
54    // Rent a movie by removing it from the unrented list and adding it to the rented list.
55    public void rent(int shop, int movie) {
56        int price = priceLookup.get(shop * 10001 + movie);
57        unrentedMovies.get(movie).remove(new int[]{price, shop});
58        rentedMovies.add(new int[]{price, shop, movie});
59    }
60
61    // Drop off a rented movie by moving it back from the rented list to the unrented list.
62    public void drop(int shop, int movie) {
63        int price = priceLookup.get(shop * 10001 + movie);
64        unrentedMovies.computeIfAbsent(movie, x -> new TreeSet<>(
65            Comparator.comparingInt((int[] arr) -> arr[0]).thenComparingInt(arr -> arr[1])
66        )).add(new int[]{price, shop});
67        rentedMovies.remove(new int[]{price, shop, movie});
68    }
69
70    // Report the 5 cheapest rented movies as a list of [shop, movie] pairs.
71    public List<List<Integer>> report() {
72        List<List<Integer>> result = new ArrayList<>();
73        for (int[] info : rentedMovies) {
74            List<Integer> pair = new ArrayList<>();
75            pair.add(info[1]);
76            pair.add(info[2]);
77            result.add(pair);
78            if (result.size() == 5) break;
79        }
80      
81        return result;
82    }
83}
84
85// Usage example:
86// MovieRentingSystem obj = new MovieRentingSystem(n, entries);
87// List<Integer> availableShops = obj.search(movie);
88// obj.rent(shop, movie);
89// obj.drop(shop, movie);
90// List<List<Integer>> report = obj.report();
91
1#include <vector>
2#include <unordered_map>
3#include <set>
4
5using namespace std;
6
7// Defining a comparator for the set so that we can keep the entries sorted based on price first, and then shop.
8struct MovieComparator {
9    bool operator() (const tuple<int, int, int>& a, const tuple<int, int, int>& b) const {
10        if (get<0>(a) != get<0>(b))
11            return get<0>(a) < get<0>(b);
12        if (get<1>(a) != get<1>(b))
13            return get<1>(a) < get<1>(b);
14        return get<2>(a) < get<2>(b);
15    }
16};
17
18class MovieRentingSystem {
19private:
20    unordered_map<int, set<pair<int, int>>> unrentedMovies; // {movie: set of (price, shop)}
21    unordered_map<pair<int, int>, int, hash<pair<int,int>>> priceLookup; // {(shop, movie): price}
22    set<tuple<int, int, int>, MovieComparator> rentedMovies; // set of (price, shop, movie)
23
24public:
25    MovieRentingSystem(int n, vector<vector<int>>& entries) {
26        for (const auto& e : entries) {
27            int shop = e[0], movie = e[1], price = e[2];
28            unrentedMovies[movie].insert({price, shop});
29            priceLookup[{shop, movie}] = price;
30        }
31    }
32
33    vector<int> search(int movie) {
34        vector<int> shops;
35        for (const auto& [price, shop] : unrentedMovies[movie]) {
36            if (shops.size() >= 5) break; // Only interested in the 5 cheapest options
37            shops.push_back(shop);
38        }
39        return shops;
40    }
41
42    void rent(int shop, int movie) {
43        int price = priceLookup[{shop, movie}];
44        unrentedMovies[movie].erase({price, shop});
45        rentedMovies.insert(make_tuple(price, shop, movie));
46    }
47
48    void drop(int shop, int movie) {
49        int price = priceLookup[{shop, movie}];
50        unrentedMovies[movie].insert({price, shop});
51        rentedMovies.erase(make_tuple(price, shop, movie));
52    }
53
54    vector<vector<int>> report() {
55        vector<vector<int>> cheapestRentedMovies;
56        for (const auto& [price, shop, movie] : rentedMovies) {
57            if (cheapestRentedMovies.size() >= 5) break; // Report only the 5 cheapest rented movies
58            cheapestRentedMovies.push_back({shop, movie});
59        }
60        return cheapestRentedMovies;
61    }
62};
63
64// Usage example:
65// MovieRentingSystem obj(n, entries);
66// vector<int> availableShops = obj.search(movie);
67// obj.rent(shop, movie);
68// obj.drop(shop, movie);
69// vector<vector<int>> report = obj.report();
70
1import { SortedList } from 'sortedcontainers';
2
3// TypeScript does not have a direct equivalent to Python's `defaultdict`.
4// We create a Map that returns a new SortedList if the key is not found.
5const unrentedMovies: Map<number, SortedList<[number, number]>> = new Map();
6
7// A Map to keep track of the price of renting a movie from a specific shop.
8const priceLookup: Map<string, number> = new Map();
9
10// A SortedList to hold rented movies with their price, shop, and movie info.
11const rentedMovies: SortedList<[number, number, number]> = new SortedList();
12
13interface Entry {
14  shop: number;
15  movie: number;
16  price: number;
17}
18
19// A function to initialize the system with the given list of entries.
20function initializeSystem(entries: Entry[]): void {
21  entries.forEach(entry => {
22    const { shop, movie, price } = entry;
23    if (!unrentedMovies.has(movie)) {
24      unrentedMovies.set(movie, new SortedList());
25    }
26    unrentedMovies.get(movie)?.add([price, shop]);
27    priceLookup.set(`${shop}-${movie}`, price);
28  });
29}
30
31// A function to search for the 5 cheapest copies of a specified movie.
32function search(movie: number): number[] {
33  const availableShops = unrentedMovies.get(movie);
34  return availableShops?.toArray().slice(0, 5).map(([_, shop]) => shop) || [];
35}
36
37// A function to rent a movie, moving it from unrented to rented.
38function rent(shop: number, movie: number): void {
39  const price = priceLookup.get(`${shop}-${movie}`);
40  if (price !== undefined) {
41    unrentedMovies.get(movie)?.remove([price, shop]);
42    rentedMovies.add([price, shop, movie]);
43  }
44}
45
46// A function to drop off a rented movie, moving it back to unrented.
47function drop(shop: number, movie: number): void {
48  const price = priceLookup.get(`${shop}-${movie}`);
49  if (price !== undefined) {
50    rentedMovies.remove([price, shop, movie]);
51    unrentedMovies.get(movie)?.add([price, shop]);
52  }
53}
54
55// A function to report the 5 cheapest rented movies.
56function report(): number[][] {
57  return rentedMovies.toArray().slice(0, 5).map(([_, shop, movie]) => [shop, movie]);
58}
59
60// Function calls for the system would replace class method calls:
61// initializeSystem(entries);
62// const availableShops = search(movie);
63// rent(shop, movie);
64// drop(shop, movie);
65// const reportList = report();
66

Time and Space Complexity

The given Python code defines a class MovieRentingSystem that keeps track of rented and unrented movies between various shops with their respective prices and implements methods to search, rent, drop, and report movies.

Space Complexity

  • The space complexity for initializing the system is O(E) where E is the number of entries, considering that each entry is stored in self.unrented and self.shopAndMovieToPrice.

Time Complexity

  • init method: For each entry, the add operation to self.unrented SortedList is O(logS) where S is the number of different movies in the worst case, and adding to self.shopAndMovieToPrice is O(1) making the overall complexity O(E * logS) for initializing the system.

  • search method: Retrieving the top 5 movies is O(1) per movie but since we need to retrieve up to 5 it becomes O(5) or simply O(1) regardless of the number of movies because it's a constant-time operation due to the limitation of 5 shops.

  • rent method: The remove operation from self.unrented[movie] is O(logS) since it's a portion of SortedList and adding the entry to self.rented is also O(logR) where R is the number of rented movies at the time. Thus, the time complexity for this method is O(logS + logR).

  • drop method: Similar to the rent method, we have a remove operation from self.rented which is O(logR) and an add operation to self.unrented[movie] which is O(logS). Hence, the time complexity here is also O(logS + logR).

  • report method: The generation of the report, which involves getting up to the top 5 entries, is O(1) since it doesn't depend on the size of the self.rented but is rather capped at 5.

Considering that S and R can vary independently, we should not simplify O(logS + logR) to O(log(S + R)) or any such combined form since they represent different aspects of the system's data.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Depth first search is equivalent to which of the tree traversal order?


Recommended Readings