Design Movie Rental System
Design Movie Rental System is a hard heaps problem solved with the composite comparator pattern.
The best approach, optimal (min-heaps with lazy deletion), runs in O(log E) amortized per operation time and O(E) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan and sort) up.
Problem
A chain of n movie rental shops wants a system for searching, renting, returning and reporting movies. You get entries, where entries[i] = [shop, movie, price] means shop shop owns one copy of movie that rents for price. Implement MovieRentingSystem:
MovieRentingSystem(int n, int[][] entries)sets up the system; every copy starts unrented.List<Integer> search(int movie)returns the shops that have an unrented copy ofmovie, cheapest first, breaking ties by the smaller shop id. Return at most 5 shops (fewer if fewer exist).void rent(int shop, int movie)rents out the unrented copy ofmovieatshop.void drop(int shop, int movie)returns that previously rented copy toshop.List<List<Integer>> report()returns up to 5 currently rented copies as[shop, movie]pairs, cheapest first; ties go to the smaller shop, then the smaller movie.
Examples
Example 1
- Input
MovieRentingSystem(3, [[0, 7, 4], [1, 7, 4], [2, 7, 2], [1, 9, 6]]), search(7), rent(2, 7), rent(1, 9), report(), search(7), drop(2, 7), search(9)- Output
[2, 0, 1], [[2, 7], [1, 9]], [0, 1], []- Why
- Shop 2 is cheapest for movie 7, and shops 0 and 1 tie at price 4 so the lower shop comes first. After renting, report lists (2, 7) at price 2 before (1, 9) at price 6. Movie 9 is still rented, so searching it returns nothing.
Example 2
- Input
MovieRentingSystem(1, [[0, 5, 10]]), search(3), report(), rent(0, 5), search(5), drop(0, 5), search(5)- Output
[], [], [], [0]- Why
- Movie 3 is not stocked anywhere, nothing is rented at first, and the only copy of movie 5 is unavailable until it is dropped.
Constraints
1 <= n <= 3 * 10^51 <= entries.length <= 10^5,entries[i] = [shop, movie, price]0 <= shop < n,1 <= movie, price <= 10^4- Each shop holds at most one copy of any given movie.
rentis only called for an unrented copy that exists, anddroponly for a copy that is currently rented.- At most
10^5calls in total tosearch,rent,dropandreport.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan and sort) | O(E log E) per search/report, O(E) per rent/drop | O(E) |
| Optimal (min-heaps with lazy deletion) | O(log E) amortized per operation | O(E) |
1Brute force (scan and sort)
O(E log E) per search/report, O(E) per rent/dropEvery query scans all E copies and sorts the matching ones.O(E)One record per copy, plus the temporary list of matches.Store every copy as [shop, movie, price, rented] in one list. rent and drop find the copy and flip its flag. search and report filter the list, sort the matches by the required order and return the first 5.
- search(movie): collect unrented copies of
movie, sort by (price, shop), return up to 5 shops. - rent / drop: scan for the copy
(shop, movie)and set or clear its rented flag. - report(): collect rented copies, sort by (price, shop, movie), return up to 5
[shop, movie]pairs.
class MovieRentingSystem {
private final List<int[]> copies = new ArrayList<>();
public MovieRentingSystem(int n, int[][] entries) {
for (int[] e : entries) copies.add(new int[] { e[0], e[1], e[2], 0 });
}
public List<Integer> search(int movie) {
List<int[]> match = new ArrayList<>();
for (int[] c : copies) if (c[1] == movie && c[3] == 0) match.add(c);
match.sort((a, b) -> a[2] != b[2] ? Integer.compare(a[2], b[2]) : Integer.compare(a[0], b[0]));
List<Integer> res = new ArrayList<>();
for (int i = 0; i < Math.min(5, match.size()); i++) res.add(match.get(i)[0]);
return res;
}
public void rent(int shop, int movie) {
find(shop, movie)[3] = 1;
}
public void drop(int shop, int movie) {
find(shop, movie)[3] = 0;
}
public List<List<Integer>> report() {
List<int[]> match = new ArrayList<>();
for (int[] c : copies) if (c[3] == 1) match.add(c);
match.sort((a, b) -> a[2] != b[2] ? Integer.compare(a[2], b[2])
: a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < Math.min(5, match.size()); i++) res.add(Arrays.asList(match.get(i)[0], match.get(i)[1]));
return res;
}
private int[] find(int shop, int movie) {
for (int[] c : copies) if (c[0] == shop && c[1] == movie) return c;
return null;
}
}class MovieRentingSystem:
def __init__(self, n: int, entries: List[List[int]]):
self.copies = [[s, m, p, False] for s, m, p in entries]
def search(self, movie: int) -> List[int]:
match = [c for c in self.copies if c[1] == movie and not c[3]]
match.sort(key=lambda c: (c[2], c[0]))
return [c[0] for c in match[:5]]
def rent(self, shop: int, movie: int) -> None:
self._find(shop, movie)[3] = True
def drop(self, shop: int, movie: int) -> None:
self._find(shop, movie)[3] = False
def report(self) -> List[List[int]]:
match = [c for c in self.copies if c[3]]
match.sort(key=lambda c: (c[2], c[0], c[1]))
return [[c[0], c[1]] for c in match[:5]]
def _find(self, shop: int, movie: int) -> list:
for c in self.copies:
if c[0] == shop and c[1] == movie:
return c
return Noneclass MovieRentingSystem {
vector<array<int, 4>> copies;
array<int, 4>* find(int shop, int movie) {
for (auto& c : copies) if (c[0] == shop && c[1] == movie) return &c;
return nullptr;
}
public:
MovieRentingSystem(int n, vector<vector<int>>& entries) {
for (auto& e : entries) copies.push_back({e[0], e[1], e[2], 0});
}
vector<int> search(int movie) {
vector<array<int, 4>> match;
for (auto& c : copies) if (c[1] == movie && c[3] == 0) match.push_back(c);
sort(match.begin(), match.end(), [](const array<int, 4>& a, const array<int, 4>& b) {
return a[2] != b[2] ? a[2] < b[2] : a[0] < b[0];
});
vector<int> res;
for (int i = 0; i < min(5, (int)match.size()); i++) res.push_back(match[i][0]);
return res;
}
void rent(int shop, int movie) { (*find(shop, movie))[3] = 1; }
void drop(int shop, int movie) { (*find(shop, movie))[3] = 0; }
vector<vector<int>> report() {
vector<array<int, 4>> match;
for (auto& c : copies) if (c[3] == 1) match.push_back(c);
sort(match.begin(), match.end(), [](const array<int, 4>& a, const array<int, 4>& b) {
if (a[2] != b[2]) return a[2] < b[2];
if (a[0] != b[0]) return a[0] < b[0];
return a[1] < b[1];
});
vector<vector<int>> res;
for (int i = 0; i < min(5, (int)match.size()); i++) res.push_back({match[i][0], match[i][1]});
return res;
}
};class MovieRentingSystem {
constructor(n, entries) {
this.copies = entries.map(([s, m, p]) => [s, m, p, false]);
}
search(movie) {
return this.copies
.filter((c) => c[1] === movie && !c[3])
.sort((a, b) => a[2] - b[2] || a[0] - b[0])
.slice(0, 5)
.map((c) => c[0]);
}
rent(shop, movie) {
this.copies.find((c) => c[0] === shop && c[1] === movie)[3] = true;
}
drop(shop, movie) {
this.copies.find((c) => c[0] === shop && c[1] === movie)[3] = false;
}
report() {
return this.copies
.filter((c) => c[3])
.sort((a, b) => a[2] - b[2] || a[0] - b[0] || a[1] - b[1])
.slice(0, 5)
.map((c) => [c[0], c[1]]);
}
}2Optimal (min-heaps with lazy deletion)
O(log E) amortized per operationA query does at most 5 valid pops and pushes; every discarded stale entry was paid for by an earlier push.O(E)Each copy sits at most once in its movie heap and at most once in the rented heap.Keep one min-heap of (price, shop) per movie for available copies and one global min-heap of (price, shop, movie) for rented copies. Do not delete from a heap when a copy changes state: a query pops entries in order, throws away the ones that are no longer valid, keeps the first 5 valid ones and pushes them back. To avoid duplicates, remember which copies are currently sitting in each heap and only push a copy when it is not already there.
- Constructor: record each copy's price; push
(price, shop)into its movie's heap and mark it as present there. - rent: mark the copy rented; if it is not already in the rented heap, push
(price, shop, movie)and mark it present. - drop: unmark rented; if it is not already in its movie heap, push
(price, shop)and mark it present. - search(movie): pop from the movie heap; a rented entry is discarded (and unmarked as present); stop after 5 valid entries, then push those back.
- report(): same on the rented heap, discarding entries that are no longer rented.
class MovieRentingSystem {
private final Map<Long, Integer> price = new HashMap<>();
private final Set<Long> rented = new HashSet<>();
private final Map<Integer, PriorityQueue<int[]>> available = new HashMap<>();
private final Set<Long> inAvailable = new HashSet<>();
private final PriorityQueue<int[]> rentedHeap = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0])
: a[1] != b[1] ? Integer.compare(a[1], b[1]) : Integer.compare(a[2], b[2]));
private final Set<Long> inRented = new HashSet<>();
private static long key(int shop, int movie) {
return (long) shop * 100001 + movie;
}
public MovieRentingSystem(int n, int[][] entries) {
for (int[] e : entries) {
price.put(key(e[0], e[1]), e[2]);
available.computeIfAbsent(e[1], m -> new PriorityQueue<>((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0])
: Integer.compare(a[1], b[1]))).add(new int[] { e[2], e[0] });
inAvailable.add(key(e[0], e[1]));
}
}
public List<Integer> search(int movie) {
List<Integer> res = new ArrayList<>();
PriorityQueue<int[]> pq = available.get(movie);
if (pq == null) return res;
List<int[]> keep = new ArrayList<>();
while (!pq.isEmpty() && keep.size() < 5) {
int[] top = pq.poll();
long k = key(top[1], movie);
if (rented.contains(k)) {
inAvailable.remove(k);
continue;
}
keep.add(top);
res.add(top[1]);
}
pq.addAll(keep);
return res;
}
public void rent(int shop, int movie) {
long k = key(shop, movie);
rented.add(k);
if (inRented.add(k)) rentedHeap.add(new int[] { price.get(k), shop, movie });
}
public void drop(int shop, int movie) {
long k = key(shop, movie);
rented.remove(k);
if (inAvailable.add(k)) available.get(movie).add(new int[] { price.get(k), shop });
}
public List<List<Integer>> report() {
List<List<Integer>> res = new ArrayList<>();
List<int[]> keep = new ArrayList<>();
while (!rentedHeap.isEmpty() && keep.size() < 5) {
int[] top = rentedHeap.poll();
long k = key(top[1], top[2]);
if (!rented.contains(k)) {
inRented.remove(k);
continue;
}
keep.add(top);
res.add(Arrays.asList(top[1], top[2]));
}
rentedHeap.addAll(keep);
return res;
}
}class MovieRentingSystem:
def __init__(self, n: int, entries: List[List[int]]):
self.price = {}
self.rented = set()
self.available = {}
self.in_available = set()
self.rented_heap = []
self.in_rented = set()
for shop, movie, p in entries:
self.price[(shop, movie)] = p
self.available.setdefault(movie, []).append((p, shop))
self.in_available.add((shop, movie))
for heap in self.available.values():
heapq.heapify(heap)
def search(self, movie: int) -> List[int]:
heap = self.available.get(movie)
if heap is None:
return []
keep = []
while heap and len(keep) < 5:
p, shop = heapq.heappop(heap)
if (shop, movie) in self.rented:
self.in_available.discard((shop, movie))
continue
keep.append((p, shop))
for item in keep:
heapq.heappush(heap, item)
return [shop for _, shop in keep]
def rent(self, shop: int, movie: int) -> None:
k = (shop, movie)
self.rented.add(k)
if k not in self.in_rented:
self.in_rented.add(k)
heapq.heappush(self.rented_heap, (self.price[k], shop, movie))
def drop(self, shop: int, movie: int) -> None:
k = (shop, movie)
self.rented.discard(k)
if k not in self.in_available:
self.in_available.add(k)
heapq.heappush(self.available[movie], (self.price[k], shop))
def report(self) -> List[List[int]]:
keep = []
while self.rented_heap and len(keep) < 5:
p, shop, movie = heapq.heappop(self.rented_heap)
if (shop, movie) not in self.rented:
self.in_rented.discard((shop, movie))
continue
keep.append((p, shop, movie))
for item in keep:
heapq.heappush(self.rented_heap, item)
return [[shop, movie] for _, shop, movie in keep]class MovieRentingSystem {
using P2 = pair<int, int>;
using P3 = tuple<int, int, int>;
unordered_map<long long, int> price;
unordered_set<long long> rented, inAvailable, inRented;
unordered_map<int, priority_queue<P2, vector<P2>, greater<P2>>> available;
priority_queue<P3, vector<P3>, greater<P3>> rentedHeap;
static long long key(int shop, int movie) { return (long long)shop * 100001 + movie; }
public:
MovieRentingSystem(int n, vector<vector<int>>& entries) {
for (auto& e : entries) {
price[key(e[0], e[1])] = e[2];
available[e[1]].push({e[2], e[0]});
inAvailable.insert(key(e[0], e[1]));
}
}
vector<int> search(int movie) {
vector<int> res;
auto it = available.find(movie);
if (it == available.end()) return res;
auto& pq = it->second;
vector<P2> keep;
while (!pq.empty() && keep.size() < 5) {
P2 top = pq.top();
pq.pop();
long long k = key(top.second, movie);
if (rented.count(k)) {
inAvailable.erase(k);
continue;
}
keep.push_back(top);
res.push_back(top.second);
}
for (auto& x : keep) pq.push(x);
return res;
}
void rent(int shop, int movie) {
long long k = key(shop, movie);
rented.insert(k);
if (inRented.insert(k).second) rentedHeap.push({price[k], shop, movie});
}
void drop(int shop, int movie) {
long long k = key(shop, movie);
rented.erase(k);
if (inAvailable.insert(k).second) available[movie].push({price[k], shop});
}
vector<vector<int>> report() {
vector<vector<int>> res;
vector<P3> keep;
while (!rentedHeap.empty() && keep.size() < 5) {
P3 top = rentedHeap.top();
rentedHeap.pop();
auto [p, shop, movie] = top;
long long k = key(shop, movie);
if (!rented.count(k)) {
inRented.erase(k);
continue;
}
keep.push_back(top);
res.push_back({shop, movie});
}
for (auto& x : keep) rentedHeap.push(x);
return res;
}
};class MinHeap {
constructor() {
this.a = [];
}
static less(x, y) {
for (let i = 0; i < x.length; i++) if (x[i] !== y[i]) return x[i] < y[i];
return false;
}
get size() {
return this.a.length;
}
push(x) {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (!MinHeap.less(a[i], a[p])) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a;
const top = a[0];
const last = a.pop();
if (a.length > 0) {
a[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && MinHeap.less(a[l], a[m])) m = l;
if (r < a.length && MinHeap.less(a[r], a[m])) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
class MovieRentingSystem {
constructor(n, entries) {
this.price = new Map();
this.rented = new Set();
this.available = new Map();
this.inAvailable = new Set();
this.rentedHeap = new MinHeap();
this.inRented = new Set();
for (const [shop, movie, p] of entries) {
const k = shop * 100001 + movie;
this.price.set(k, p);
if (!this.available.has(movie)) this.available.set(movie, new MinHeap());
this.available.get(movie).push([p, shop]);
this.inAvailable.add(k);
}
}
search(movie) {
const heap = this.available.get(movie);
if (!heap) return [];
const keep = [];
while (heap.size > 0 && keep.length < 5) {
const top = heap.pop();
const k = top[1] * 100001 + movie;
if (this.rented.has(k)) {
this.inAvailable.delete(k);
continue;
}
keep.push(top);
}
for (const x of keep) heap.push(x);
return keep.map((x) => x[1]);
}
rent(shop, movie) {
const k = shop * 100001 + movie;
this.rented.add(k);
if (!this.inRented.has(k)) {
this.inRented.add(k);
this.rentedHeap.push([this.price.get(k), shop, movie]);
}
}
drop(shop, movie) {
const k = shop * 100001 + movie;
this.rented.delete(k);
if (!this.inAvailable.has(k)) {
this.inAvailable.add(k);
this.available.get(movie).push([this.price.get(k), shop]);
}
}
report() {
const keep = [];
while (this.rentedHeap.size > 0 && keep.length < 5) {
const top = this.rentedHeap.pop();
const k = top[1] * 100001 + top[2];
if (!this.rented.has(k)) {
this.inRented.delete(k);
continue;
}
keep.push(top);
}
for (const x of keep) this.rentedHeap.push(x);
return keep.map((x) => [x[1], x[2]]);
}
}Edge cases to test
- Fewer than 5 matching copies (return all of them), or none at all
- Equal prices, where the smaller shop id (and then the smaller movie id in report) must come first
- Renting, dropping and renting the same copy again
- A movie whose every copy is rented
- Many rented copies where only the 5 cheapest may be returned
Hints
Hint 1
The simplest version keeps one list of all copies with a rented flag and sorts the matching ones on every query. Where is the time going?
Hint 2
search only needs the cheapest 5 unrented copies of one movie, and report the cheapest 5 rented copies overall: these are priority-queue questions.
Hint 3
Instead of removing a copy from a heap when its state changes, leave it there and skip it when it surfaces (lazy deletion). Re-insert a copy only if it is not already sitting in that heap.
FAQ
What is the best time complexity for Design Movie Rental System?
Optimal (min-heaps with lazy deletion) runs in O(log E) amortized per operation time and O(E) extra space. A query does at most 5 valid pops and pushes; every discarded stale entry was paid for by an earlier push.
Which pattern does Design Movie Rental System use?
It is a heaps problem that uses the composite comparator pattern. Other problems with the same pattern: Top K Frequent Elements, Design Task Manager, Rank Teams by Votes.
Is there a brute force solution for Design Movie Rental System?
Yes. Brute force (scan and sort) takes O(E log E) per search/report, O(E) per rent/drop time and O(E) space. Store every copy as [shop, movie, price, rented] in one list.
Which edge cases should I test for Design Movie Rental System?
Fewer than 5 matching copies (return all of them), or none at all; Equal prices, where the smaller shop id (and then the smaller movie id in report) must come first; Renting, dropping and renting the same copy again; A movie whose every copy is rented; Many rented copies where only the 5 cheapest may be returned.