Problem

You have a movie renting company consisting of n shops. You want to implement a renting system that supports searching for, booking, and returning movies. The system should also support generating a report of the currently rented movies.

Each movie is given as a 2D integer array entries where entries[i] = [shopi, moviei, pricei] indicates that there is a copy of movie moviei at shop shopi with a rental price of pricei. Each shop carries at most one copy of a movie moviei.

The system should support the following functions:

  • Search : Finds the cheapest 5 shops that have an unrented copy of a given movie. The shops should be sorted by price in ascending order, and in case of a tie, the one with the smallershopi should appear first. If there are less than 5 matching shops, then all of them should be returned. If no shop has an unrented copy, then an empty list should be returned.
  • Rent : Rents an unrented copy of a given movie from a given shop.
  • Drop : Drops off a previously rented copy of a given movie at a given shop.
  • Report : Returns the cheapest 5 rented movies (possibly of the same movie ID) as a 2D list res where res[j] = [shopj, moviej] describes that the jth cheapest rented movie moviej was rented from the shop shopj. The movies in res should be sorted by price in ascending order, and in case of a tie, the one with the smallershopj should appear first, and if there is still tie, the one with the smallermoviej should appear first. If there are fewer than 5 rented movies, then all of them should be returned. If no movies are currently being rented, then an empty list should be returned.

Implement the MovieRentingSystem class:

  • MovieRentingSystem(int n, int[][] entries) Initializes the MovieRentingSystem object with n shops and the movies in entries.
  • List<Integer> search(int movie) Returns a list of shops that have an unrented copy of the given movie as described above.
  • void rent(int shop, int movie) Rents the given movie from the given shop.
  • void drop(int shop, int movie) Drops off a previously rented movie at the given shop.
  • List<List<Integer>> report() Returns a list of cheapest rented movies as described above.

Note: The test cases will be generated such that rent will only be called if the shop has an unrented copy of the movie, and drop will only be called if the shop had previously rented out the movie.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


    
    
    **Input**
    ["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"]
    [[3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]], [1], [0, 1], [1, 2], [], [1, 2], [2]]
    **Output**
    [null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]]
    
    **Explanation**
    MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]);
    movieRentingSystem.search(1);  // return [1, 0, 2], Movies of ID 1 are unrented at shops 1, 0, and 2. Shop 1 is cheapest; shop 0 and 2 are the same price, so order by shop number.
    movieRentingSystem.rent(0, 1); // Rent movie 1 from shop 0. Unrented movies at shop 0 are now [2,3].
    movieRentingSystem.rent(1, 2); // Rent movie 2 from shop 1. Unrented movies at shop 1 are now [1].
    movieRentingSystem.report();   // return [[0, 1], [1, 2]]. Movie 1 from shop 0 is cheapest, followed by movie 2 from shop 1.
    movieRentingSystem.drop(1, 2); // Drop off movie 2 at shop 1. Unrented movies at shop 1 are now [1,2].
    movieRentingSystem.search(2);  // return [0, 1]. Movies of ID 2 are unrented at shops 0 and 1. Shop 0 is cheapest, followed by shop 1.

Constraints

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

Solution

Method 1 – Hash Maps and Ordered Sets (Heaps/TreeSets)

Intuition

We need to efficiently support search, rent, drop, and report operations with custom sorting. By using hash maps for fast lookups and ordered sets (like TreeSet or heap with lazy deletion) for sorted queries, we can achieve efficient operations.

Approach

  1. Use a map priceMap[(shop, movie)] = price for quick price lookup.
  2. For each movie, maintain a sorted set (by price, shop) of unrented shops: unrented[movie].
  3. Maintain a global sorted set (by price, shop, movie) of rented movies: rented.
  4. For search(movie), return up to 5 shops from unrented[movie].
  5. For rent(shop, movie), remove from unrented[movie] and add to rented.
  6. For drop(shop, movie), remove from rented and add back to unrented[movie].
  7. For report(), return up to 5 entries from rented.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class MovieRentingSystem {
    unordered_map<int, set<pair<int, int>>> unrented; // movie -> set of (price, shop)
    set<tuple<int, int, int>> rented; // (price, shop, movie)
    unordered_map<pair<int, int>, int, hash<pair<int, int>>> priceMap;
public:
    MovieRentingSystem(int n, vector<vector<int>>& entries) {
        for (auto& e : entries) {
            int shop = e[0], movie = e[1], price = e[2];
            unrented[movie].insert({price, shop});
            priceMap[{shop, movie}] = price;
        }
    }
    vector<int> search(int movie) {
        vector<int> ans;
        for (auto& [price, shop] : unrented[movie]) {
            ans.push_back(shop);
            if (ans.size() == 5) break;
        }
        return ans;
    }
    void rent(int shop, int movie) {
        int price = priceMap[{shop, movie}];
        unrented[movie].erase({price, shop});
        rented.insert({price, shop, movie});
    }
    void drop(int shop, int movie) {
        int price = priceMap[{shop, movie}];
        rented.erase({price, shop, movie});
        unrented[movie].insert({price, shop});
    }
    vector<vector<int>> report() {
        vector<vector<int>> ans;
        for (auto& [price, shop, movie] : rented) {
            ans.push_back({shop, movie});
            if (ans.size() == 5) break;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

type entry struct{price, shop int}
type rentedEntry struct{price, shop, movie int}
type MovieRentingSystem struct {
    unrented map[int][]entry
    rented []rentedEntry
    priceMap map[[2]int]int
}
func Constructor(n int, entries [][]int) MovieRentingSystem {
    m := MovieRentingSystem{unrented: map[int][]entry{}, rented: []rentedEntry{}, priceMap: map[[2]int]int{}}
    for _, e := range entries {
        shop, movie, price := e[0], e[1], e[2]
        m.unrented[movie] = append(m.unrented[movie], entry{price, shop})
        m.priceMap[[2]int{shop, movie}] = price
    }
    return m
}
func (m *MovieRentingSystem) Search(movie int) []int {
    es := m.unrented[movie]
    sort.Slice(es, func(i, j int) bool { if es[i].price == es[j].price { return es[i].shop < es[j].shop }; return es[i].price < es[j].price })
    ans := []int{}
    for i := 0; i < len(es) && i < 5; i++ { ans = append(ans, es[i].shop) }
    return ans
}
func (m *MovieRentingSystem) Rent(shop, movie int) {
    price := m.priceMap[[2]int{shop, movie}]
    es := m.unrented[movie]
    for i, e := range es {
        if e.price == price && e.shop == shop {
            m.unrented[movie] = append(es[:i], es[i+1:]...)
            break
        }
    }
    m.rented = append(m.rented, rentedEntry{price, shop, movie})
}
func (m *MovieRentingSystem) Drop(shop, movie int) {
    price := m.priceMap[[2]int{shop, movie}]
    for i, e := range m.rented {
        if e.price == price && e.shop == shop && e.movie == movie {
            m.rented = append(m.rented[:i], m.rented[i+1:]...)
            break
        }
    }
    m.unrented[movie] = append(m.unrented[movie], entry{price, shop})
}
func (m *MovieRentingSystem) Report() [][]int {
    sort.Slice(m.rented, func(i, j int) bool {
        if m.rented[i].price != m.rented[j].price { return m.rented[i].price < m.rented[j].price }
        if m.rented[i].shop != m.rented[j].shop { return m.rented[i].shop < m.rented[j].shop }
        return m.rented[i].movie < m.rented[j].movie
    })
    ans := [][]int{}
    for i := 0; i < len(m.rented) && i < 5; i++ {
        ans = append(ans, []int{m.rented[i].shop, m.rented[i].movie})
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public class MovieRentingSystem {
    private Map<Integer, TreeSet<int[]>> unrented = new HashMap<>(); // movie -> set of [price, shop]
    private TreeSet<int[]> rented = new TreeSet<>((a, b) -> a[0]!=b[0]?a[0]-b[0]:a[1]!=b[1]?a[1]-b[1]:a[2]-b[2]);
    private Map<List<Integer>, Integer> priceMap = new HashMap<>();
    public MovieRentingSystem(int n, int[][] entries) {
        for (int[] e : entries) {
            int shop = e[0], movie = e[1], price = e[2];
            unrented.computeIfAbsent(movie, k -> new TreeSet<>((a, b) -> a[0]!=b[0]?a[0]-b[0]:a[1]-b[1])).add(new int[]{price, shop});
            priceMap.put(Arrays.asList(shop, movie), price);
        }
    }
    public List<Integer> search(int movie) {
        List<Integer> ans = new ArrayList<>();
        if (!unrented.containsKey(movie)) return ans;
        for (int[] arr : unrented.get(movie)) {
            ans.add(arr[1]);
            if (ans.size() == 5) break;
        }
        return ans;
    }
    public void rent(int shop, int movie) {
        int price = priceMap.get(Arrays.asList(shop, movie));
        unrented.get(movie).remove(new int[]{price, shop});
        rented.add(new int[]{price, shop, movie});
    }
    public void drop(int shop, int movie) {
        int price = priceMap.get(Arrays.asList(shop, movie));
        rented.remove(new int[]{price, shop, movie});
        unrented.get(movie).add(new int[]{price, shop});
    }
    public List<List<Integer>> report() {
        List<List<Integer>> ans = new ArrayList<>();
        for (int[] arr : rented) {
            ans.add(Arrays.asList(arr[1], arr[2]));
            if (ans.size() == 5) break;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class MovieRentingSystem(n: Int, entries: Array<IntArray>) {
    private val priceMap = mutableMapOf<Pair<Int, Int>, Int>()
    private val unrented = mutableMapOf<Int, sortedSetOf<Pair<Int, Int>>>()
    private val rented = sortedSetOf<Triple<Int, Int, Int>>(compareBy({ it.first }, { it.second }, { it.third }))
    init {
        for (e in entries) {
            val (shop, movie, price) = e
            priceMap[shop to movie] = price
            unrented.getOrPut(movie) { sortedSetOf(compareBy<Pair<Int, Int>> { it.first }.thenBy { it.second }) }.add(price to shop)
        }
    }
    fun search(movie: Int): List<Int> = unrented[movie]?.take(5)?.map { it.second } ?: emptyList()
    fun rent(shop: Int, movie: Int) {
        val price = priceMap[shop to movie]!!
        unrented[movie]?.remove(price to shop)
        rented.add(Triple(price, shop, movie))
    }
    fun drop(shop: Int, movie: Int) {
        val price = priceMap[shop to movie]!!
        rented.remove(Triple(price, shop, movie))
        unrented[movie]?.add(price to shop)
    }
    fun report(): List<List<Int>> = rented.take(5).map { listOf(it.second, it.third) }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import heapq
class MovieRentingSystem:
    def __init__(self, n: int, entries: list[list[int]]):
        self.price_map = {}
        self.unrented = {}
        self.rented = set()
        for shop, movie, price in entries:
            self.price_map[(shop, movie)] = price
            self.unrented.setdefault(movie, set()).add((price, shop))
        self.rented_heap = []
    def search(self, movie: int) -> list[int]:
        if movie not in self.unrented:
            return []
        shops = sorted(self.unrented[movie])
        return [shop for price, shop in shops[:5]]
    def rent(self, shop: int, movie: int) -> None:
        price = self.price_map[(shop, movie)]
        self.unrented[movie].remove((price, shop))
        self.rented.add((price, shop, movie))
    def drop(self, shop: int, movie: int) -> None:
        price = self.price_map[(shop, movie)]
        self.rented.remove((price, shop, movie))
        self.unrented[movie].add((price, shop))
    def report(self) -> list[list[int]]:
        rented_list = sorted(self.rented)
        return [[shop, movie] for price, shop, movie in rented_list[:5]]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

use std::collections::{BTreeSet, HashMap};
struct MovieRentingSystem {
    price_map: HashMap<(i32, i32), i32>,
    unrented: HashMap<i32, BTreeSet<(i32, i32)>>,
    rented: BTreeSet<(i32, i32, i32)>,
}
impl MovieRentingSystem {
    fn new(_n: i32, entries: Vec<Vec<i32>>) -> Self {
        let mut price_map = HashMap::new();
        let mut unrented = HashMap::new();
        let mut rented = BTreeSet::new();
        for e in entries {
            let (shop, movie, price) = (e[0], e[1], e[2]);
            price_map.insert((shop, movie), price);
            unrented.entry(movie).or_insert(BTreeSet::new()).insert((price, shop));
        }
        Self { price_map, unrented, rented }
    }
    fn search(&self, movie: i32) -> Vec<i32> {
        self.unrented.get(&movie)
            .map(|set| set.iter().take(5).map(|&(_, shop)| shop).collect())
            .unwrap_or_default()
    }
    fn rent(&mut self, shop: i32, movie: i32) {
        let price = self.price_map[&(shop, movie)];
        self.unrented.get_mut(&movie).unwrap().remove(&(price, shop));
        self.rented.insert((price, shop, movie));
    }
    fn drop(&mut self, shop: i32, movie: i32) {
        let price = self.price_map[&(shop, movie)];
        self.rented.remove(&(price, shop, movie));
        self.unrented.get_mut(&movie).unwrap().insert((price, shop));
    }
    fn report(&self) -> Vec<Vec<i32>> {
        self.rented.iter().take(5).map(|&(_, shop, movie)| vec![shop, movie]).collect()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class MovieRentingSystem {
    private priceMap = new Map<string, number>();
    private unrented = new Map<number, Set<string>>();
    private rented = new Set<string>();
    constructor(n: number, entries: number[][]) {
        for (const [shop, movie, price] of entries) {
            this.priceMap.set(`${shop},${movie}`, price);
            if (!this.unrented.has(movie)) this.unrented.set(movie, new Set());
            this.unrented.get(movie)!.add(`${price},${shop}`);
        }
    }
    search(movie: number): number[] {
        if (!this.unrented.has(movie)) return [];
        const arr = Array.from(this.unrented.get(movie)!).map(s => s.split(',').map(Number));
        arr.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
        return arr.slice(0, 5).map(([_, shop]) => shop);
    }
    rent(shop: number, movie: number): void {
        const price = this.priceMap.get(`${shop},${movie}`)!;
        this.unrented.get(movie)!.delete(`${price},${shop}`);
        this.rented.add(`${price},${shop},${movie}`);
    }
    drop(shop: number, movie: number): void {
        const price = this.priceMap.get(`${shop},${movie}`)!;
        this.rented.delete(`${price},${shop},${movie}`);
        this.unrented.get(movie)!.add(`${price},${shop}`);
    }
    report(): number[][] {
        const arr = Array.from(this.rented).map(s => s.split(',').map(Number));
        arr.sort((a, b) => a[0] - b[0] || a[1] - b[1] || a[2] - b[2]);
        return arr.slice(0, 5).map(([_, shop, movie]) => [shop, movie]);
    }
}

Complexity

  • ⏰ Time complexity: O(log n) for each operation (with TreeSet/heap), O(k) for search/report (k=5).
  • 🧺 Space complexity: O(e), where e is the number of entries.