Design Movie Rental System

Hard Heaps Composite comparator Original on LeetCode

Reported atFlipkart

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 of movie, 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 of movie at shop.
  • void drop(int shop, int movie) returns that previously rented copy to shop.
  • 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^5
  • 1 <= 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.
  • rent is only called for an unrented copy that exists, and drop only for a copy that is currently rented.
  • At most 10^5 calls in total to search, rent, drop and report.

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.

00:00
Testcase

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.

ApproachTimeSpace
Brute force (scan and sort)O(E log E) per search/report, O(E) per rent/dropO(E)
Optimal (min-heaps with lazy deletion)O(log E) amortized per operationO(E)

1Brute force (scan and sort)

TimeO(E log E) per search/report, O(E) per rent/dropEvery query scans all E copies and sorts the matching ones.
SpaceO(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.

  1. search(movie): collect unrented copies of movie, sort by (price, shop), return up to 5 shops.
  2. rent / drop: scan for the copy (shop, movie) and set or clear its rented flag.
  3. 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;
    }
}

2Optimal (min-heaps with lazy deletion)

TimeO(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.
SpaceO(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.

  1. Constructor: record each copy's price; push (price, shop) into its movie's heap and mark it as present there.
  2. rent: mark the copy rented; if it is not already in the rented heap, push (price, shop, movie) and mark it present.
  3. drop: unmark rented; if it is not already in its movie heap, push (price, shop) and mark it present.
  4. 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.
  5. 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;
    }
}

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.