What is the time complexity of Design Movie Rental System?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Design Movie Rental System?

This problem uses Array, Hash Table, Design, Heap (Priority Queue), Ordered Set. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Design Movie Rental System?

Insight 1: Using appropriate data structures like HashMaps and Priority Queues (or Sets) are crucial for efficient search, insertion, and deletion operations. Insight 2: Maintaining separate data structures for unrented and rented movies simplifies the implementation of the search, rent, and drop functionalities.

Which companies ask LeetCode 1912. Design Movie Rental System in interviews?

This problem is frequently asked at Flipkart.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Design Movie Rental System - LeetCode 1912 Solution

Design Movie Rental System - Complete Solution Guide

Design Movie Rental System is LeetCode problem 1912, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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] = [shop i , movie i , price i ] indicates that there is a copy of movie movie i at shop shop i with a rental price of price i . Each shop carries at most one copy of a movie movie i . The system

Detailed Explanation

The problem requires designing a movie rental system with functionalities to search for the cheapest available movies in different shops, rent movies, return movies (drop), and report the cheapest rented movies. The system must efficiently manage the availability and rental status of movies across multiple shops. The system must handle ties in prices by prioritizing shops with smaller shop IDs and, for reporting, prioritizing also by movie ID. The number of results returned by search and report should be capped at 5.

Solution Approach

The solution uses HashMaps and Priority Queues (or Sets) to efficiently manage the movie rental system. A HashMap `unrented` stores the available movies at each shop, organized by movie ID. A Set `rented` stores the currently rented movies. A HashMap `prices` stores the price of each movie at each shop for quick access. The `search` function uses a priority queue to find the 5 cheapest shops with the given movie. The `rent` function removes the movie from the `unrented` HashMap and adds it to the `rented` Set. The `drop` function does the opposite. The `report` function uses a priority queue to find the 5 cheapest rented movies.

Step-by-Step Algorithm

Step 1: Initialization: Create HashMaps `unrented` (movie ID -> set of (price, shop)), `prices` ((shop, movie) -> price), and a Set `rented` ((price, shop, movie)). Populate these data structures based on the input `entries`.
Step 2: Search: Given a movie ID, check if it exists in the `unrented` HashMap. If not, return an empty list. Otherwise, use `heapq.nsmallest()` (or a PriorityQueue) to find the 5 cheapest (price, shop) tuples in the set associated with the movie ID in the `unrented` HashMap. Extract the shop IDs from these tuples and return them as a list.
Step 3: Rent: Given a shop and movie ID, retrieve the price from the `prices` HashMap. Remove the (price, shop) tuple from the set associated with the movie ID in the `unrented` HashMap. Add the (price, shop, movie) tuple to the `rented` Set.
Step 4: Drop: Given a shop and movie ID, retrieve the price from the `prices` HashMap. Remove the (price, shop, movie) tuple from the `rented` Set. Add the (price, shop) tuple to the set associated with the movie ID in the `unrented` HashMap.
Step 5: Report: Use `heapq.nsmallest()` (or a PriorityQueue) to find the 5 cheapest (price, shop, movie) tuples in the `rented` Set. Extract the (shop, movie) pairs from these tuples and return them as a list of lists.

Key Insights

Insight 1: Using appropriate data structures like HashMaps and Priority Queues (or Sets) are crucial for efficient search, insertion, and deletion operations.
Insight 2: Maintaining separate data structures for unrented and rented movies simplifies the implementation of the search, rent, and drop functionalities.
Insight 3: Utilizing the `heapq.nsmallest()` or a Priority Queue with a size limit can efficiently find the top 5 cheapest movies or shops, avoiding full sorting.
Insight 4: The key for price lookups should be a combination of (shop,movie) as that defines a unique entry with an associated price.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Design, Heap (Priority Queue), Ordered Set.

Companies

Asked at: Flipkart.

Design Movie Rental System | LeetCode 1912

Hard

Array Hash Table Design Heap (Priority Queue)Ordered Set

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.*;

class MovieRentingSystem {

    private Map<Integer, PriorityQueue<int[]>> unrented; // movie -> (price, shop)
    private Set<int[]> rented; // (price, shop, movie)
    private Map<String, Integer> prices; // (shop, movie) -> price

    public MovieRentingSystem(int n, int[][] entries) {
        unrented = new HashMap<>();
        rented = new HashSet<>();
        prices = new HashMap<>();

        for (int[] entry : entries) {
            int shop = entry[0];
            int movie = entry[1];
            int price = entry[2];

            unrented.computeIfAbsent(movie, k -> new PriorityQueue<>((a, b) -> {
                if (a[0] != b[0]) {
                    return a[0] - b[0];
                } else {
                    return a[1] - b[1];
                }
            })).offer(new int[]{price, shop});
            prices.put(shop + "," + movie, price);
        }
    }

    public List<Integer> search(int movie) {
        if (!unrented.containsKey(movie)) {
            return new ArrayList<>();
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>(unrented.get(movie)); // copy pq
        List<Integer> result = new ArrayList<>();
        int count = 0;

        PriorityQueue<int[]> temp = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else {
                return a[1] - b[1];
            }
        });
        
        while (!pq.isEmpty() && count < 5) {
            int[] curr = pq.poll();
            result.add(curr[1]);
            temp.offer(curr);
            count++;
        }
        
        unrented.put(movie,new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else {
                return a[1] - b[1];
            }
        }));
        unrented.get(movie).addAll(temp);
        
        return result;
    }

    public void rent(int shop, int movie) {
        int price = prices.get(shop + "," + movie);
        unrented.get(movie).removeIf(arr -> arr[0] == price && arr[1] == shop);
        int[] rentedMovie = {price, shop, movie};
        rented.add(rentedMovie);
    }

    public void drop(int shop, int movie) {
        int price = prices.get(shop + "," + movie);
        rented.removeIf(arr -> arr[0] == price && arr[1] == shop && arr[2] == movie);
        unrented.get(movie).offer(new int[]{price, shop});
    }

    public List<List<Integer>> report() {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else if (a[1] != b[1]) {
                return a[1] - b[1];
            } else {
                return a[2] - b[2];
            }
        });

        pq.addAll(rented);

        List<List<Integer>> result = new ArrayList<>();
        int count = 0;
        while (!pq.isEmpty() && count < 5) {
            int[] curr = pq.poll();
            result.add(Arrays.asList(curr[1], curr[2]));
            count++;
        }

        return result;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1912: Design Movie Rental System - Detailed explanation and solution approaches.

Topics

Array Hash Table Design Heap (Priority Queue)Ordered Set

Companies

Flipkart

Stats

Difficulty:Hard

Languages:4

Companies:1

Problem #:1912

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Initialization: Create HashMaps `unrented` (movie ID -> set of (price, shop)), `prices` ((shop, movie) -> price), and a Set `rented` ((price, shop, movie)). Populate these data structures based on the input `entries`.
2
Step 2: Search: Given a movie ID, check if it exists in the `unrented` HashMap. If not, return an empty list. Otherwise, use `heapq.nsmallest()` (or a PriorityQueue) to find the 5 cheapest (price, shop) tuples in the set associated with the movie ID in the `unrented` HashMap. Extract the shop IDs from these tuples and return them as a list.
3
Step 3: Rent: Given a shop and movie ID, retrieve the price from the `prices` HashMap. Remove the (price, shop) tuple from the set associated with the movie ID in the `unrented` HashMap. Add the (price, shop, movie) tuple to the `rented` Set.
4
Step 4: Drop: Given a shop and movie ID, retrieve the price from the `prices` HashMap. Remove the (price, shop, movie) tuple from the `rented` Set. Add the (price, shop) tuple to the set associated with the movie ID in the `unrented` HashMap.
5
Step 5: Report: Use `heapq.nsmallest()` (or a PriorityQueue) to find the 5 cheapest (price, shop, movie) tuples in the `rented` Set. Extract the (shop, movie) pairs from these tuples and return them as a list of lists.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The initialization time complexity is O(k) to insert the entries into hash maps. Search and Report use heapq.nsmallest, which has a time complexity of O(n + k log k), where n is the total number of movies/shops to choose from, and k is the number we want to choose (5 in this case). Since k is capped at 5, search and report is approximately O(min(n, 5)) . Rent and Drop operations involve removing elements from and adding elements to sets, with an average time complexity of O(log n).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Sorting before search/report

Instead of using `heapq.nsmallest()` or Priority Queues, sort the list of unrented copies each time `search` or `report` is called and take the first 5 elements.

Time: O(n log n) for search and report where n is the number of unrented movies for search or rented movies for report.Space: O(n) for temporary storage.

Trade-offs: This approach is less efficient than using `heapq.nsmallest()` or Priority Queues because it always sorts the entire list, even if only the top 5 elements are needed. It is simpler to implement, but not suitable for large datasets.

✨

Key Insights

1Insight 1: Using appropriate data structures like HashMaps and Priority Queues (or Sets) are crucial for efficient search, insertion, and deletion operations.
2Insight 2: Maintaining separate data structures for unrented and rented movies simplifies the implementation of the search, rent, and drop functionalities.
3Insight 3: Utilizing the `heapq.nsmallest()` or a Priority Queue with a size limit can efficiently find the top 5 cheapest movies or shops, avoiding full sorting.
4Insight 4: The key for price lookups should be a combination of (shop,movie) as that defines a unique entry with an associated price.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Edge Cases

Edge case 1: A movie is not available in any shop. The `search` function should return an empty list.
Edge case 2: There are fewer than 5 unrented movies for the `search` function or fewer than 5 rented movies for the `report` function. The code correctly handles this by returning all available movies/shops.
Edge case 3: Renting or dropping a movie that doesn't exist. The problem statement guarantees this won't happen.
Edge case 4: Ties in price during search and report. The implementation uses tuples that naturally handle the tie-breaking conditions of prioritizing shop ID and movie ID.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not using appropriate data structures, leading to inefficient search and update operations. For example, using lists instead of HashMaps or Priority Queues.

✗Common mistake 2: Not correctly handling ties in price for the `search` and `report` functions.

✗Common mistake 3: Failing to handle the edge cases where there are fewer than 5 unrented or rented movies.

✗Common mistake 4: Incorrectly removing/adding elements to rented/unrented structures leading to inconsistent state.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: E-commerce platforms can use this algorithm to display the cheapest products from different vendors.

🏦Real-world scenario 2: Ride-sharing apps can use this algorithm to find the closest and cheapest available drivers.

🎮Real-world scenario 3: Resource allocation in cloud computing, assigning tasks to servers based on availability and cost.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

It's okay to not finish hard problems in interviews. Show your problem-solving process.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 21, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Design Movie Rental System"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?