Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1912. Design Movie Rental System - Leetcode Solution

Problem Description

The "Design Movie Rental System" problem requires you to implement a class that simulates a movie rental service across multiple shops. Each shop has a set of movies, each with a rental price. The system must support the following operations:

  • search(movie): Return up to 5 shops with the lowest price for a given movie that is currently available (not rented), sorted by price, then shop id.
  • rent(shop, movie): Mark the movie as rented from the given shop.
  • drop(shop, movie): Mark the movie as returned to the given shop.
  • report(): Return up to 5 currently rented movies, sorted by price, then shop id, then movie id. Each entry is a tuple [shop, movie].

You are given the initial inventory as a list of [shop, movie, price] entries. Each shop can have multiple movies, and prices may vary per shop. You must ensure all operations are efficient and maintain the correct orderings.

Constraints:

  • No two entries will have the same shop and movie pair.
  • All operations must be efficient (ideally O(log n) for inserts/removals/searches).
  • Do not reuse entries: a movie cannot be rented twice from the same shop until it is dropped.

Thought Process

At first glance, we might consider storing all movies in a simple list or dictionary and scanning through them for each operation. However, this would be inefficient, especially for the search and report operations, which require sorted results and must be fast.

We need a way to:

  • Quickly find the cheapest available shops for a movie (for search).
  • Efficiently update the status of a movie as rented or dropped.
  • Efficiently retrieve the currently rented movies in sorted order (for report).
This suggests we need data structures that support fast insertion, deletion, and sorted access, such as balanced binary search trees or sorted lists. Since standard libraries in Python, Java, C++, and JavaScript differ, we may use SortedList (from sortedcontainers) in Python, TreeSet in Java, set in C++ (with custom comparators), and arrays with binary search in JavaScript.

Solution Approach

Let's break down the design step by step:

  1. Data Structures:
    • For each movie, maintain a sorted list of available copies across shops, sorted by price and shop id.
    • Maintain a global sorted list of rented movies, sorted by price, shop id, and movie id.
    • Use a map from (shop, movie) to price for quick lookups.
  2. search(movie):
    • Return up to 5 lowest-price available copies of the movie, using its sorted list.
  3. rent(shop, movie):
    • Remove (price, shop) from the available list for that movie.
    • Add (price, shop, movie) to the global rented list.
  4. drop(shop, movie):
    • Remove (price, shop, movie) from the rented list.
    • Add (price, shop) back to the available list for that movie.
  5. report():
    • Return up to 5 entries from the global rented list, each as [shop, movie].

These steps ensure all operations are efficient and results are always sorted as required.

Example Walkthrough

Suppose the initial inventory is:

  • [0, 1, 5] (Shop 0 has Movie 1 for $5)
  • [0, 2, 6] (Shop 0 has Movie 2 for $6)
  • [1, 1, 4] (Shop 1 has Movie 1 for $4)
  • [2, 1, 4] (Shop 2 has Movie 1 for $4)

  1. search(1):
    • Available: (1, 4), (2, 4), (0, 5)
    • Sorted: Shop 1 ($4), Shop 2 ($4), Shop 0 ($5)
    • Return: [1, 2, 0]
  2. rent(1, 1):
    • Remove (1, 4) from available for movie 1.
    • Add (4, 1, 1) to rented list.
  3. search(1):
    • Available: (2, 4), (0, 5)
    • Return: [2, 0]
  4. report():
    • Rented: (4, 1, 1)
    • Return: [[1, 1]]
  5. drop(1, 1):
    • Remove (4, 1, 1) from rented.
    • Add (1, 4) back to available for movie 1.
  6. search(1):
    • Available: (1, 4), (2, 4), (0, 5)
    • Return: [1, 2, 0]

Time and Space Complexity

  • Brute-force approach:
    • Each search or report would scan all entries: O(N) per call.
    • rent and drop would also be O(N) due to searching for the correct entry.
  • Optimized approach (as above):
    • All operations are O(log N) due to balanced trees/sorted lists.
    • Space is O(N), storing all movie copies and rental status.

The use of sorted data structures ensures that both searching and updating operations remain efficient even as the number of shops and movies grows.

Summary

The key to solving the Movie Rental System problem efficiently is to use data structures that maintain sorted order and allow for fast insertions and deletions. By keeping per-movie available lists and a global rented list, and updating these as rentals and drops occur, we can support all required operations in logarithmic time. This approach is both elegant and practical, leveraging the strengths of balanced trees or sorted lists to maintain order and efficiency.

Code Implementation

from collections import defaultdict
from sortedcontainers import SortedList

class MovieRentingSystem:

    def __init__(self, n, entries):
        # (shop, movie) -> price
        self.price_map = {}
        # movie -> SortedList[(price, shop)]
        self.available = defaultdict(SortedList)
        # SortedList[(price, shop, movie)]
        self.rented = SortedList()
        for shop, movie, price in entries:
            self.price_map[(shop, movie)] = price
            self.available[movie].add((price, shop))

    def search(self, movie):
        # Return up to 5 shops with lowest price for movie
        return [shop for price, shop in self.available[movie][:5]]

    def rent(self, shop, movie):
        price = self.price_map[(shop, movie)]
        self.available[movie].remove((price, shop))
        self.rented.add((price, shop, movie))

    def drop(self, shop, movie):
        price = self.price_map[(shop, movie)]
        self.rented.remove((price, shop, movie))
        self.available[movie].add((price, shop))

    def report(self):
        # Return up to 5 rented movies as [shop, movie]
        return [[shop, movie] for price, shop, movie in self.rented[:5]]
      
#include <vector>
#include <map>
#include <set>
#include <tuple>

using namespace std;

class MovieRentingSystem {
    map<pair<int, int>, int> price_map;
    map<int, set<pair<int, int>>> available;
    set<tuple<int, int, int>> rented;

public:
    MovieRentingSystem(int n, vector<vector<int>>& entries) {
        for (auto& e : entries) {
            int shop = e[0], movie = e[1], price = e[2];
            price_map[{shop, movie}] = price;
            available[movie].insert({price, shop});
        }
    }

    vector<int> search(int movie) {
        vector<int> res;
        auto& av = available[movie];
        for (auto it = av.begin(); it != av.end() && res.size() < 5; ++it)
            res.push_back(it->second);
        return res;
    }

    void rent(int shop, int movie) {
        int price = price_map[{shop, movie}];
        available[movie].erase({price, shop});
        rented.insert({price, shop, movie});
    }

    void drop(int shop, int movie) {
        int price = price_map[{shop, movie}];
        rented.erase({price, shop, movie});
        available[movie].insert({price, shop});
    }

    vector<vector<int>> report() {
        vector<vector<int>> res;
        int cnt = 0;
        for (auto it = rented.begin(); it != rented.end() && cnt < 5; ++it, ++cnt)
            res.push_back({get<1>(*it), get<2>(*it)});
        return res;
    }
};
      
import java.util.*;

class MovieRentingSystem {
    Map<Pair, Integer> priceMap = new HashMap<>();
    Map<Integer, TreeSet<ShopPrice>> available = new HashMap<>();
    TreeSet<RentedMovie> rented = new TreeSet<>();

    static class Pair {
        int shop, movie;
        Pair(int s, int m) { shop = s; movie = m; }
        public boolean equals(Object o) {
            if (!(o instanceof Pair)) return false;
            Pair p = (Pair)o;
            return shop == p.shop && movie == p.movie;
        }
        public int hashCode() { return shop * 10007 + movie; }
    }

    static class ShopPrice implements Comparable<ShopPrice> {
        int price, shop;
        ShopPrice(int p, int s) { price = p; shop = s; }
        public int compareTo(ShopPrice o) {
            if (price != o.price) return price - o.price;
            return shop - o.shop;
        }
    }

    static class RentedMovie implements Comparable<RentedMovie> {
        int price, shop, movie;
        RentedMovie(int p, int s, int m) { price = p; shop = s; movie = m; }
        public int compareTo(RentedMovie o) {
            if (price != o.price) return price - o.price;
            if (shop != o.shop) return shop - o.shop;
            return movie - o.movie;
        }
    }

    public MovieRentingSystem(int n, int[][] entries) {
        for (int[] e : entries) {
            int shop = e[0], movie = e[1], price = e[2];
            priceMap.put(new Pair(shop, movie), price);
            available.computeIfAbsent(movie, k -> new TreeSet<>()).add(new ShopPrice(price, shop));
        }
    }

    public List<Integer> search(int movie) {
        List<Integer> res = new ArrayList<>();
        TreeSet<ShopPrice> set = available.get(movie);
        if (set == null) return res;
        int cnt = 0;
        for (ShopPrice sp : set) {
            if (cnt++ == 5) break;
            res.add(sp.shop);
        }
        return res;
    }

    public void rent(int shop, int movie) {
        int price = priceMap.get(new Pair(shop, movie));
        available.get(movie).remove(new ShopPrice(price, shop));
        rented.add(new RentedMovie(price, shop, movie));
    }

    public void drop(int shop, int movie) {
        int price = priceMap.get(new Pair(shop, movie));
        rented.remove(new RentedMovie(price, shop, movie));
        available.get(movie).add(new ShopPrice(price, shop));
    }

    public List<List<Integer>> report() {
        List<List<Integer>> res = new ArrayList<>();
        int cnt = 0;
        for (RentedMovie rm : rented) {
            if (cnt++ == 5) break;
            res.add(Arrays.asList(rm.shop, rm.movie));
        }
        return res;
    }
}
      
class MovieRentingSystem {
    constructor(n, entries) {
        this.priceMap = new Map();
        this.available = new Map(); // movieId -> array of [price, shop]
        this.rented = []; // array of [price, shop, movie]
        for (const [shop, movie, price] of entries) {
            this.priceMap.set(shop + ',' + movie, price);
            if (!this.available.has(movie)) this.available.set(movie, []);
            this.available.get(movie).push([price, shop]);
        }
        // Sort each movie's available list
        for (const arr of this.available.values()) {
            arr.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
        }
    }

    search(movie) {
        let arr = this.available.get(movie) || [];
        return arr.slice(0, 5).map(x => x[1]);
    }

    rent(shop, movie) {
        let price = this.priceMap.get(shop + ',' + movie);
        let arr = this.available.get(movie);
        for (let i = 0; i < arr.length; ++i) {
            if (arr[i][1] === shop && arr[i][0] === price) {
                arr.splice(i, 1);
                break;
            }
        }
        this.rented.push([price, shop, movie]);
        this.rented.sort((a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]);
    }

    drop(shop, movie) {
        let price = this.priceMap.get(shop + ',' + movie);
        for (let i = 0; i < this.rented.length; ++i) {
            let [p, s, m] = this.rented[i];
            if (s === shop && m === movie && p === price) {
                this.rented.splice(i, 1);
                break;
            }
        }
        let arr = this.available.get(movie);
        arr.push([price, shop]);
        arr.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    }

    report() {
        return this.rented.slice(0, 5).map(x => [x[1], x[2]]);
    }
}