Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Searching and reporting need two different sorted views: available copies grouped by movie, and all rented copies together. Moving a copy between those views on each rental change keeps the first five results ready in the required order.

Approach

Store each (shop, movie) price in a lookup. For each movie, keep available copies ordered by (price, shop); keep rentals ordered by (price, shop, movie). search returns shop IDs from the first five available records for its movie. rent removes the copy from availability and inserts it into rentals; drop reverses those updates using the saved price. report returns shop/movie pairs from the first five rental records. Tuple ordering handles price ties, then shop ties, and finally movie ties for reports; prices are not returned.

class MovieRentingSystem:
    def __init__(self, n: int, entries: List[List[int]]):
        self.movies = defaultdict(SortedList)
        self.sm_p = {}
        self.rented = SortedList()

        for s, m, p in entries:
            self.movies[m].add((p, s))
            self.sm_p[(s, m)] = p

    def search(self, movie: int) -> List[int]:
        res = []
        n = len(self.movies[movie])

        for i in range(5):
            if i == n:
                break
            res.append(self.movies[movie][i][1]) # [s]

        return res

    def rent(self, shop: int, movie: int) -> None:
        p = self.sm_p[(shop, movie)]
        self.movies[movie].discard((p, shop))
        self.rented.add((p, shop, movie))

    def drop(self, shop: int, movie: int) -> None:
        p = self.sm_p[(shop, movie)]
        self.movies[movie].add((p, shop))
        self.rented.discard((p, shop, movie))

    def report(self) -> List[List[int]]:
        res = []
        n = len(self.rented)

        for i in range(5):
            if i == n:
                break
            res.append([self.rented[i][1], self.rented[i][2]]) # [s, m]

        return res

Complexity analysis

Let E be the entry count and U the number of distinct absent movie IDs searched. Both solutions retain O(E + U) state because absent searches create empty movie collections. JavaScript's AVL tree gives O(E log(E + 1)) construction and O(log(E + 1)) rent/drop tree work, with usual expected constant-time map access. Its first(5) walks at most five linked records from the stored head, so search/report take O(1) expected time and constant output space. Python SortedList updates are documented as approximately logarithmic, not strict worst-case: O(E log E) construction and O(log E) updates are practical models; conservative worst-case bounds are O(E^2) construction and O(E) per update due to block movement and index maintenance. With its default block size, the at-most-five indexed reads stay in the first block's direct-access fast path, so search/report are O(1) expected time here too. JavaScript's AVL traversal is iterative and uses O(1) working pointers; Python updates can allocate temporary buffers, within O(E + U) peak storage.