Problem statement

A movie rental company has n shops, numbered 0 to n - 1. Each entries[i] = [shop, movie, price] says that shop has one copy of movie that rents for price. A shop carries at most one copy of each movie.

Write the class MovieRentingSystem:

• MovieRentingSystem(int n, int[][] entries) sets up the shops; every copy starts out unrented.
• int[] search(int movie) returns the shops that have an unrented copy of movie — the cheapest 5 of them (all of them if fewer), ordered by price, then by shop number.
• void rent(int shop, int movie) rents out the unrented copy of movie at shop.
• void drop(int shop, int movie) returns the rented copy of movie to shop.
• int[][] report() returns the cheapest 5 rented copies as [shop, movie] pairs (all of them if fewer), ordered by price, then by shop, then by movie.

rent is only called for a copy that is currently unrented, and drop only for one that is currently rented.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["MovieRentingSystem","search","rent","rent","report","search","drop","search","report"]
[[4,[[0,7,30],[1,7,25],[2,7,30],[3,7,40],[1,9,10],[3,9,10]]],[7],[1,7],[3,9],[],[9],[1,7],[7],[]]
Output: [null,[1,0,2,3],null,null,[[3,9],[1,7]],[1],null,[1,0,2,3],[[3,9]]]
Explanation: Movie 7 is cheapest at shop 1 (25); shops 0 and 2 tie at 30 and are ordered by number. After renting, the rented copies sorted by price are movie 9 at shop 3 (10) and movie 7 at shop 1 (25). Once shop 1's copy of 7 comes back, it is the cheapest again.

Example 2

Input: ["MovieRentingSystem","search","rent","rent","rent","search","report","search"]
[[6,[[0,5,2],[1,5,2],[2,5,2],[3,5,1],[4,5,2],[5,5,2]]],[5],[3,5],[5,5],[0,5],[5],[],[8]]
Output: [null,[3,0,1,2,4],null,null,null,[1,2,4],[[3,5],[0,5],[5,5]],[]]
Explanation: Six shops have movie 5 but search lists only the cheapest five. After three rentals, three shops are left. No shop has movie 8.

Constraints

• 1 <= n <= 3 * 10^5
• 1 <= entries.length <= 10^5
• 0 <= shop < n
• 1 <= movie, price <= 10^4
• Each shop carries at most one copy of a movie
• At most 10^5 calls are made in total to search, rent, drop and report

Hints for Design Movie Rental System

1. Hint 1

   Both queries want "the 5 smallest" of a set that changes one element at a time — an ordered set per question.

2. Hint 2

   For each movie, keep its unrented copies ordered by (price, shop). Keep one global ordered set of rented copies ordered by (price, shop, movie). A map from (shop, movie) to price lets rent and drop find the keys.

3. Hint 3

   rent moves a copy from its movie's set into the rented set; drop moves it back. search and report read the first five elements.

How to solve Design Movie Rental System

Each query is a top-5 over a set that changes by one element per update, so keep those sets ordered: per movie, the unrented copies by (price, shop); globally, the rented copies by (price, shop, movie).

Approach

1. Build price[(shop, movie)] and, for every movie, an ordered set avail[movie] of (price, shop) holding all its copies; start an empty ordered set rented of (price, shop, movie).
2. search(movie): return the shops of the first five elements of avail[movie] (an empty list if the movie is unknown).
3. rent(shop, movie): with p = price[(shop, movie)], remove (p, shop) from avail[movie] and add (p, shop, movie) to rented.
4. drop(shop, movie): the reverse — remove from rented, add back to avail[movie].
5. report(): return [shop, movie] for the first five elements of rented.

Why it works

Every copy is in exactly one place: its movie's available set while unrented, the rented set while out — rent and drop move it across. The sets' orders are exactly the problem's tie-break rules, so their first five elements are the required answers.

Complexity

• Time — O(log E) per rent/drop and O(log E) (plus 5 steps) per search/report with balanced ordered sets; O(E log E) to build
• Space — O(E) for E entries

Pitfalls

• Ties: order by price, then shop (and then movie in the report) — all ascending.
• Return fewer than five when fewer exist, and an empty list for a movie nobody carries or nobody has unrented.
• A shop number alone does not identify a copy — key the price lookup by the pair (shop, movie).

Reference solution

Python

from bisect import bisect_left, insort

class MovieRentingSystem:

    def __init__(self, n: int, entries: List[List[int]]):
        self.price = {}   # (shop, movie) -> price
        self.avail = {}   # movie -> sorted (price, shop) of unrented copies
        self.rented = []  # sorted (price, shop, movie) of rented copies
        for shop, movie, p in entries:
            self.price[(shop, movie)] = p
            self.avail.setdefault(movie, []).append((p, shop))
        for lst in self.avail.values():
            lst.sort()

    def search(self, movie: int) -> List[int]:
        return [shop for _, shop in self.avail.get(movie, [])[:5]]

    def rent(self, shop: int, movie: int) -> None:
        p = self.price[(shop, movie)]
        lst = self.avail[movie]
        del lst[bisect_left(lst, (p, shop))]
        insort(self.rented, (p, shop, movie))

    def drop(self, shop: int, movie: int) -> None:
        p = self.price[(shop, movie)]
        del self.rented[bisect_left(self.rented, (p, shop, movie))]
        insort(self.avail[movie], (p, shop))

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

Java

class MovieRentingSystem {
    private HashMap<Long, Integer> price = new HashMap<>(); // (shop, movie) -> price
    private HashMap<Integer, TreeSet<int[]>> avail = new HashMap<>(); // movie -> {price, shop}
    private TreeSet<int[]> rented = new TreeSet<>((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 static long key(int shop, int movie) { return (long) shop << 14 | movie; }

    public MovieRentingSystem(int n, int[][] entries) {
        for (int[] e : entries) {
            price.put(key(e[0], e[1]), e[2]);
            avail.computeIfAbsent(e[1], k -> new TreeSet<>((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]});
        }
    }

    public int[] search(int movie) {
        TreeSet<int[]> s = avail.get(movie);
        if (s == null) return new int[0];
        int[] out = new int[Math.min(5, s.size())];
        int i = 0;
        for (int[] c : s) { if (i == out.length) break; out[i++] = c[1]; }
        return out;
    }

    public void rent(int shop, int movie) {
        int p = price.get(key(shop, movie));
        avail.get(movie).remove(new int[]{p, shop});
        rented.add(new int[]{p, shop, movie});
    }

    public void drop(int shop, int movie) {
        int p = price.get(key(shop, movie));
        rented.remove(new int[]{p, shop, movie});
        avail.get(movie).add(new int[]{p, shop});
    }

    public int[][] report() {
        int[][] out = new int[Math.min(5, rented.size())][];
        int i = 0;
        for (int[] c : rented) { if (i == out.length) break; out[i++] = new int[]{c[1], c[2]}; }
        return out;
    }
}

C++

class MovieRentingSystem {
    unordered_map<long long, int> price;              // (shop, movie) -> price
    unordered_map<int, set<pair<int, int>>> avail;    // movie -> (price, shop) unrented
    set<tuple<int, int, int>> rented;                 // (price, shop, movie)

    static long long key(int shop, int movie) { return (long long)shop << 14 | movie; }
public:
    MovieRentingSystem(int n, vector<vector<int>>& entries) {
        for (auto& e : entries) {
            price[key(e[0], e[1])] = e[2];
            avail[e[1]].insert({e[2], e[0]});
        }
    }

    vector<int> search(int movie) {
        vector<int> out;
        auto it = avail.find(movie);
        if (it == avail.end()) return out;
        for (auto& c : it->second) {
            if (out.size() == 5) break;
            out.push_back(c.second);
        }
        return out;
    }

    void rent(int shop, int movie) {
        int p = price[key(shop, movie)];
        avail[movie].erase({p, shop});
        rented.insert(make_tuple(p, shop, movie));
    }

    void drop(int shop, int movie) {
        int p = price[key(shop, movie)];
        rented.erase(make_tuple(p, shop, movie));
        avail[movie].insert({p, shop});
    }

    vector<vector<int>> report() {
        vector<vector<int>> out;
        for (auto& c : rented) {
            if (out.size() == 5) break;
            out.push_back({get<1>(c), get<2>(c)});
        }
        return out;
    }
};

JavaScript

// A copy's keys are packed into exact doubles: (price, shop) as price * 2^19 + shop,
// and (price, shop, movie) as that times 2^14 plus movie — at most 2^47.
var MR_SHOP = 524288, MR_MOVIE = 16384;

function mrPos(a, x) { // first index whose key is >= x
    var lo = 0, hi = a.length;
    while (lo < hi) {
        var mid = (lo + hi) >> 1;
        if (a[mid] < x) lo = mid + 1; else hi = mid;
    }
    return lo;
}

var MovieRentingSystem = function(n, entries) {
    this.price = new Map(); // shop * 2^14 + movie -> price
    this.avail = new Map(); // movie -> sorted (price, shop) keys of unrented copies
    this.rented = [];       // sorted (price, shop, movie) keys of rented copies
    for (var i = 0; i < entries.length; i++) {
        var shop = entries[i][0], movie = entries[i][1], p = entries[i][2];
        this.price.set(shop * MR_MOVIE + movie, p);
        if (!this.avail.has(movie)) this.avail.set(movie, []);
        this.avail.get(movie).push(p * MR_SHOP + shop);
    }
    this.avail.forEach(function(a) { a.sort(function(x, y) { return x - y; }); });
};

MovieRentingSystem.prototype.search = function(movie) {
    var a = this.avail.get(movie) || [], out = [];
    for (var i = 0; i < a.length && i < 5; i++) out.push(a[i] % MR_SHOP);
    return out;
};

MovieRentingSystem.prototype.rent = function(shop, movie) {
    var p = this.price.get(shop * MR_MOVIE + movie), a = this.avail.get(movie), key = p * MR_SHOP + shop;
    a.splice(mrPos(a, key), 1);
    var full = key * MR_MOVIE + movie;
    this.rented.splice(mrPos(this.rented, full), 0, full);
};

MovieRentingSystem.prototype.drop = function(shop, movie) {
    var p = this.price.get(shop * MR_MOVIE + movie), a = this.avail.get(movie), key = p * MR_SHOP + shop;
    this.rented.splice(mrPos(this.rented, key * MR_MOVIE + movie), 1);
    a.splice(mrPos(a, key), 0, key);
};

MovieRentingSystem.prototype.report = function() {
    var out = [];
    for (var i = 0; i < this.rented.length && i < 5; i++) {
        var full = this.rented[i], movie = full % MR_MOVIE, key = (full - movie) / MR_MOVIE;
        out.push([key % MR_SHOP, movie]);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard
• Sum of Imbalance Numbers of All Subarrays Hard