Design Movie Rental System: Sorted Containers Meet Heaps

Design Movie Rental System is LeetCode problem 1912, and it is one of those hard design problems that looks overwhelming at first but becomes manageable once you pick the right data structures. The challenge is not any single operation. It is keeping all five operations fast at the same time. You need sorted containers that support both insertion and removal in O(log n), plus a dictionary for O(1) price lookups. Get the data structure design right and the code almost writes itself.

The problem

You have n movie rental shops. Each shop carries a set of movies at fixed prices. You need to design a system that supports five operations:

• MovieRentingSystem(n, entries) - Initialize with n shops. Each entry is [shop, movie, price].
• search(movie) - Return the 5 cheapest unrented shops that have this movie, sorted by price, then by shop id.
• rent(shop, movie) - Rent the given movie from the given shop.
• drop(shop, movie) - Return (drop off) the given movie to the given shop.
• report() - Return the 5 cheapest currently rented movies, sorted by price, then shop, then movie.

All "cheapest" queries break ties by shop id, then by movie id. If fewer than 5 results exist, return all of them.

The approach

The trick is recognizing that you need three data structures working together:

1. unrented[movie] - A sorted container for each movie, holding (price, shop) tuples. This lets search(movie) grab the first 5 entries in O(5 * log n) time.

2. price[(shop, movie)] - A plain dictionary mapping each (shop, movie) pair to its price. When you call rent(shop, movie), you need to know the price so you can locate the entry in the sorted containers. This gives O(1) lookup.

3. rented - A single sorted container holding (price, shop, movie) tuples for all currently rented movies. This lets report() grab the first 5 entries.

The rent operation looks up the price, removes (price, shop) from unrented[movie], and adds (price, shop, movie) to rented. The drop operation does the reverse: removes from rented, adds back to unrented[movie].

In Python, the SortedList from the sortedcontainers library gives you O(log n) add, remove, and indexed access. This is the cleanest approach for interviews, and interviewers generally accept it as long as you explain what it does under the hood.

from sortedcontainers import SortedList
from collections import defaultdict

class MovieRentingSystem:
    def __init__(self, n, entries):
        self.price = {}
        self.unrented = defaultdict(SortedList)
        self.rented = SortedList()

        for shop, movie, p in entries:
            self.price[(shop, movie)] = p
            self.unrented[movie].add((p, shop))

    def search(self, movie):
        return [s for _, s in self.unrented[movie][:5]]

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

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

    def report(self):
        return [[s, m] for _, s, m in self.rented[:5]]

The solution is short because the sorted containers handle all the heavy lifting. Every operation is just "look up the price, remove from one container, add to another." The sorted order is maintained automatically.

Why SortedList?

You might wonder why a regular heap does not work here. A heap supports O(log n) insertion and O(log n) removal of the minimum, but it does not support O(log n) removal of an arbitrary element. When you rent(shop, movie), you need to remove a specific (price, shop) entry from unrented[movie]. With a heap, finding that entry takes O(n) time.

You could use lazy deletion with a heap (mark entries as deleted and skip them during extraction), but that complicates every operation and can lead to memory bloat if many rent/drop cycles happen. The SortedList approach is cleaner: it gives you O(log n) for add, remove by value, and indexed access, which is exactly what this problem needs.

If your language does not have a sorted container library, you can implement the same idea using a balanced BST or a skip list. In Java, TreeSet or TreeMap works. In C++, std::set or std::multiset works. The key property you need is O(log n) insertion, deletion, and ordered iteration.

Complexity analysis

Let m be the total number of entries across all shops.

Init inserts each entry into a SortedList, which takes O(log n) per entry and O(m log m) total.

search and report slice the first 5 elements from a sorted container. The slice is O(5) but accessing by index in a SortedList is O(log n), so the total is O(5 * log m) which simplifies to O(log m).

rent and drop each do one remove and one add, both O(log m).

Space is O(m) total for the three data structures. Each entry exists in exactly one of unrented or rented at any time, plus the price dictionary holds all m entries.

The Building Blocks

This problem combines three patterns that appear across many design problems:

Sorted containers for top-k queries. When you need the k smallest or largest elements and the collection changes dynamically (insertions and deletions), a sorted container is the right tool. This is the same idea behind Kth Largest Element, but here the collection is not static. You cannot just build a heap once. You need to add and remove elements over time while maintaining sorted order.

Dictionary for O(1) metadata lookup. The price[(shop, movie)] dictionary is a classic pattern. You store metadata separately so that other operations can look it up in constant time. This same pattern appears in LRU Cache, where the hash map stores pointers to linked list nodes. The principle is the same: keep a fast-access index alongside your ordered data structure.

Moving elements between containers. The rent and drop operations move entries between unrented and rented. This "transfer between two ordered structures" pattern shows up whenever you model state transitions, like moving tasks between queues or toggling items between active and archived sets.

Edge cases to watch for

• Fewer than 5 results. Both search and report should return fewer than 5 entries if not enough exist. The [:5] slice handles this naturally in Python.
• Rent and drop the same movie repeatedly. A movie can be rented and returned multiple times. Each rent removes from unrented and adds to rented. Each drop reverses it. Make sure you are not duplicating entries.
• Multiple shops with the same price. The sort key is (price, shop) for unrented and (price, shop, movie) for rented. Since shop ids are unique per entry, ties on price are broken by shop id, which matches the problem's requirements.
• A movie with no unrented copies. If all copies of a movie are rented out, search(movie) returns an empty list. The SortedList will be empty, and [:5] returns [].
• No rented movies. report() returns an empty list when nothing has been rented. Same [:5] on an empty SortedList.

From understanding to recall

You have read through the Design Movie Rental System solution. The data structure design makes sense: three containers, each serving a specific query. The code is clean. But can you write the whole MovieRentingSystem class from scratch in five minutes?

The part you will forget is the sort keys. Was it (price, shop) or (shop, price) for the unrented list? Does rented sort by (price, shop, movie) or (price, movie, shop)? These details matter because getting the tuple order wrong means your search and report results come out in the wrong order.

Spaced repetition locks in these details. You practice writing the class from memory, and each time you get the sort keys wrong, you correct yourself and the correction sticks a little deeper. After a few reps, the tuple orders become automatic.

Related posts

• Kth Largest Element - Uses heaps for top-k queries on a static array. Design Movie Rental System extends this idea to dynamic collections with insertions and deletions.
• LRU Cache - Another design problem that pairs a dictionary with an ordered data structure. The hash-map-plus-ordered-container pattern is the same.
• Design Add and Search Words - A design problem that combines a trie with DFS. Good practice for the "pick the right data structure" skill that this problem tests.