LeetCode 1912 - Design Movie Rental System

LeetCode Problem 1912

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Design, Heap (Priority Queue), Ordered Set

Solution

Problem Understanding

The problem requires designing a movie rental system for multiple shops, where each shop carries at most one copy of each movie. We are asked to implement a class that efficiently supports searching for available movies, renting them, returning them, and reporting the cheapest currently rented movies.

The input consists of the number of shops n and a list entries that specifies which shop has which movie and at what price. The expected output depends on the operation:

• search(movie): Returns the cheapest 5 shops with an available copy of movie, sorted first by price and then by shop number.
• rent(shop, movie): Marks a movie as rented at a specific shop. This operation is guaranteed to be valid (the movie is available).
• drop(shop, movie): Returns a previously rented movie. This is guaranteed to be valid as well.
• report(): Returns the cheapest 5 rented movies, sorted by price, then shop number, then movie ID.

The constraints indicate that the number of shops can be large (3 * 10^5) and the number of operations can be up to 10^5. This rules out any naive O(n) search for each operation. Efficient use of data structures like ordered sets, hash maps, and priority queues is necessary to meet time limits.

Important edge cases include:

• Multiple shops having the same price for a movie (sorting by shop ID is required)
• Renting and dropping operations in succession that affect availability
• Less than 5 results for search or report (should return all available entries)
• Rented movies might include duplicates of the same movie ID from different shops

Approaches

The brute-force approach would store all entries in a simple list or hash map and, for each operation, iterate over all entries to find the relevant movies. For search, we would filter unrented movies and sort them; for report, we would filter rented movies and sort them. Although correct, this is too slow due to O(n log n) sorting in every operation and O(n) filtering.

The optimal approach leverages ordered data structures. We can use:

• A dictionary mapping each movie to a sorted set of (price, shop) pairs for unrented copies, allowing O(log n) insertion, deletion, and top-k retrieval.
• A global sorted set of rented movies (price, shop, movie) to efficiently produce the report of the cheapest 5 rented movies.

This allows search, rent, drop, and report to be implemented efficiently in O(log n) per insertion/deletion, and O(k) for fetching top-k elements.

Algorithm Walkthrough

1. Initialization: Create a dictionary mapping each movie to a sorted set of (price, shop) representing unrented copies. Also, create a global sorted set for rented movies (price, shop, movie).
2. Search(movie): Look up the sorted set of unrented copies for the given movie. Take the first 5 elements from the sorted set and return the corresponding shops.
3. Rent(shop, movie): Remove (price, shop) from the unrented set for the movie and add (price, shop, movie) to the rented set.
4. Drop(shop, movie): Remove (price, shop, movie) from the rented set and add (price, shop) back to the unrented set for the movie.
5. Report(): Take the first 5 elements from the rented set and return a list of [shop, movie] pairs.

Why it works: The invariants maintained are that the unrented sets always contain available copies and the rented set always contains rented copies. Sorting ensures we can efficiently fetch the cheapest top-k elements for search and report.

Python Solution

from typing import List
from sortedcontainers import SortedList

class MovieRentingSystem:

    def __init__(self, n: int, entries: List[List[int]]):
        self.movie_to_unrented = {}
        self.rented = SortedList()
        self.price_map = {}
        
        for shop, movie, price in entries:
            if movie not in self.movie_to_unrented:
                self.movie_to_unrented[movie] = SortedList()
            self.movie_to_unrented[movie].add((price, shop))
            self.price_map[(shop, movie)] = price

    def search(self, movie: int) -> List[int]:
        if movie not in self.movie_to_unrented:
            return []
        unrented_list = self.movie_to_unrented[movie]
        return [shop for price, shop in unrented_list[:5]]

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

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

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

Implementation Walkthrough:

Initialization stores both unrented and rented data efficiently. search fetches the top 5 elements in O(k) time since the sorted list maintains order. rent and drop modify both sets in O(log n) due to SortedList operations. report retrieves the cheapest 5 rented movies directly from the sorted list. Using price_map ensures constant-time lookup of prices.

Go Solution

package main

import (
    "sort"
)

type Entry struct {
    price int
    shop  int
    movie int
}

type MovieRentingSystem struct {
    movieToUnrented map[int][]Entry
    rented          []Entry
    priceMap        map[[2]int]int
}

func Constructor(n int, entries [][]int) MovieRentingSystem {
    m := make(map[int][]Entry)
    pMap := make(map[[2]int]int)
    for _, e := range entries {
        shop, movie, price := e[0], e[1], e[2]
        m[movie] = append(m[movie], Entry{price, shop, movie})
        pMap[[2]int{shop, movie}] = price
    }
    for _, list := range m {
        sort.Slice(list, func(i, j int) bool {
            if list[i].price != list[j].price {
                return list[i].price < list[j].price
            }
            return list[i].shop < list[j].shop
        })
    }
    return MovieRentingSystem{m, []Entry{}, pMap}
}

func (this *MovieRentingSystem) Search(movie int) []int {
    res := []int{}
    list := this.movieToUnrented[movie]
    for i := 0; i < len(list) && i < 5; i++ {
        res = append(res, list[i].shop)
    }
    return res
}

func removeEntry(entries []Entry, target Entry) []Entry {
    for i, e := range entries {
        if e.shop == target.shop && e.movie == target.movie {
            return append(entries[:i], entries[i+1:]...)
        }
    }
    return entries
}

func insertEntry(entries []Entry, e Entry) []Entry {
    entries = append(entries, e)
    sort.Slice(entries, func(i, j int) bool {
        if entries[i].price != entries[j].price {
            return entries[i].price < entries[j].price
        }
        if entries[i].shop != entries[j].shop {
            return entries[i].shop < entries[j].shop
        }
        return entries[i].movie < entries[j].movie
    })
    return entries
}

func (this *MovieRentingSystem) Rent(shop int, movie int) {
    price := this.priceMap[[2]int{shop, movie}]
    e := Entry{price, shop, movie}
    this.movieToUnrented[movie] = removeEntry(this.movieToUnrented[movie], e)
    this.rented = insertEntry(this.rented, e)
}

func (this *MovieRentingSystem) Drop(shop int, movie int) {
    price := this.priceMap[[2]int{shop, movie}]
    e := Entry{price, shop, movie}
    this.rented = removeEntry(this.rented, e)
    this.movieToUnrented[movie] = insertEntry(this.movieToUnrented[movie], Entry{price, shop, movie})
}

func (this *MovieRentingSystem) Report() [][]int {
    res := [][]int{}
    for i := 0; i < len(this.rented) && i < 5; i++ {
        res = append(res, []int{this.rented[i].shop, this.rented[i].movie})
    }
    return res
}

Go Implementation Notes: In Go, we emulate ordered sets using slices and sort operations. removeEntry and insertEntry handle updates in