LeetCode 1912: Design Movie Rental System Solution

Master LeetCode problem 1912 (Design Movie Rental System), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1912. Design Movie Rental System

Hard

Array Hash Table Design Heap (Priority Queue)Ordered Set

Problem Explanation

Explanation

To solve this problem, we can use a combination of data structures such as Maps, Priority Queues, and Sets.

We will maintain three main data structures:
- A Map to store the rental prices of movies at each shop for quick access during search operations.
- A Map to store the rented movies along with their prices and shops where they were rented.
- A Priority Queue to keep track of the cheapest rented movies.
For the search operation, we will iterate through the entries to find unrented copies of the movie requested. We will use a Priority Queue to maintain the cheapest 5 shops with unrented copies.
For the rent operation, we will update the rented movies map and remove the rented movie from the unrented copies.
For the drop operation, we will update the rented movies map and add the dropped movie back as an unrented copy.
For the report operation, we will return the cheapest 5 rented movies using the Priority Queue.

The time complexity for search, rent, drop, and report operations is O(log n) due to the use of Priority Queues. The space complexity is O(n) to store the movie entries and rented movies.

Solution Code

import java.util.*;

class MovieRentingSystem {
    Map<Integer, TreeSet<int[]>> moviePrices;
    Map<Integer, TreeSet<int[]>> rentedMovies;
    PriorityQueue<int[]> cheapestRentedMovies;

    public MovieRentingSystem(int n, int[][] entries) {
        moviePrices = new HashMap<>();
        rentedMovies = new HashMap<>();
        cheapestRentedMovies = new PriorityQueue<>((a, b) -> {
            if (a[1] != b[1]) return a[1] - b[1];
            if (a[0] != b[0]) return a[0] - b[0];
            return a[2] - b[2];
        });

        for (int[] entry : entries) {
            moviePrices.computeIfAbsent(entry[1], k -> new TreeSet<>((a, b) -> {
                if (a[1] != b[1]) return a[1] - b[1];
                return a[0] - b[0];
            })).add(new int[]{entry[0], entry[2]});
        }
    }

    public List<Integer> search(int movie) {
        List<Integer> result = new ArrayList<>();
        if (moviePrices.containsKey(movie)) {
            TreeSet<int[]> prices = moviePrices.get(movie);
            for (int[] price : prices) {
                result.add(price[0]);
                if (result.size() == 5) break;
            }
        }
        return result;
    }

    public void rent(int shop, int movie) {
        int[] price = moviePrices.get(movie).stream().filter(p -> p[0] == shop).findFirst().get();
        moviePrices.get(movie).remove(price);
        rentedMovies.computeIfAbsent(movie, k -> new TreeSet<>((a, b) -> {
            if (a[1] != b[1]) return a[1] - b[1];
            if (a[0] != b[0]) return a[0] - b[0];
            return a[2] - b[2];
        })).add(new int[]{shop, price[1]});
    }

    public void drop(int shop, int movie) {
        int[] price = rentedMovies.get(movie).stream().filter(p -> p[0] == shop).findFirst().get();
        rentedMovies.get(movie).remove(price);
        moviePrices.computeIfAbsent(movie, k -> new TreeSet<>((a, b) -> {
            if (a[1] != b[1]) return a[1] - b[1];
            return a[0] - b[0];
        })).add(new int[]{shop, price[1]});
    }

    public List<List<Integer>> report() {
        List<List<Integer>> result = new ArrayList<>();
        while (result.size() < 5 && !cheapestRentedMovies.isEmpty()) {
            int[] movie = cheapestRentedMovies.poll();
            result.add(Arrays.asList(movie[0], movie[1]));
        }
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1912 (Design Movie Rental System)?

This page provides optimized solutions for LeetCode problem 1912 (Design Movie Rental System) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1912 (Design Movie Rental System)?

The time complexity for LeetCode 1912 (Design Movie Rental System) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1912 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1912 in Java, C++, or Python.

Back to LeetCode Solutions