{x}
blog image

Not Boring Movies

Table: Cinema

+----------------+----------+
| Column Name    | Type     |
+----------------+----------+
| id             | int      |
| movie          | varchar  |
| description    | varchar  |
| rating         | float    |
+----------------+----------+
id is the primary key (column with unique values) for this table.
Each row contains information about the name of a movie, its genre, and its rating.
rating is a 2 decimal places float in the range [0, 10]

 

Write a solution to report the movies with an odd-numbered ID and a description that is not "boring".

Return the result table ordered by rating in descending order.

The result format is in the following example.

 

Example 1:

Input: 
Cinema table:
+----+------------+-------------+--------+
| id | movie      | description | rating |
+----+------------+-------------+--------+
| 1  | War        | great 3D    | 8.9    |
| 2  | Science    | fiction     | 8.5    |
| 3  | irish      | boring      | 6.2    |
| 4  | Ice song   | Fantacy     | 8.6    |
| 5  | House card | Interesting | 9.1    |
+----+------------+-------------+--------+
Output: 
+----+------------+-------------+--------+
| id | movie      | description | rating |
+----+------------+-------------+--------+
| 5  | House card | Interesting | 9.1    |
| 1  | War        | great 3D    | 8.9    |
+----+------------+-------------+--------+
Explanation: 
We have three movies with odd-numbered IDs: 1, 3, and 5. The movie with ID = 3 is boring so we do not include it in the answer.

Solution Explanation for LeetCode Problem 620: Not Boring Movies

This problem requires retrieving data from a database table (Cinema) based on specific criteria and sorting the results. The goal is to select movies with odd IDs and descriptions that aren't "boring", and then order them by rating in descending order.

Approach

The solution uses standard SQL query techniques to achieve this:

  1. Filtering: The WHERE clause filters the rows based on two conditions:

    • id & 1 = 1: This checks if the ID is odd. The bitwise AND operator (&) with 1 will result in 1 only if the least significant bit of id is 1 (indicating an odd number).
    • description != 'boring': This condition excludes movies with the description "boring".

  2. Sorting: The ORDER BY clause sorts the filtered rows in descending order based on the rating column.

SQL Code (MySQL)

SELECT *
FROM Cinema
WHERE description != 'boring' AND id & 1 = 1
ORDER BY rating DESC;

This query directly implements the filtering and sorting steps described above. Note that we use rating in the ORDER BY clause instead of 4 (as in the original provided solution), which is more readable and less prone to errors if the table schema changes.

Time and Space Complexity Analysis

  • Time Complexity: The time complexity of this SQL query is dominated by the sorting operation. The exact complexity depends on the database's implementation of sorting (e.g., merge sort, quicksort), but it's generally considered to be O(N log N), where N is the number of rows in the Cinema table. The filtering operation is typically O(N) in the worst case.

  • Space Complexity: The space complexity depends on the amount of intermediate data the database system needs to store during the filtering and sorting processes. In most cases, this would be proportional to the size of the input, so O(N) in the worst case. The output space complexity is proportional to the number of rows in the final result set.

Alternative Solutions (Conceptual)

While the provided SQL query is efficient and concise, other approaches could be used depending on the database system:

  • Using CASE statements: You could replace id & 1 = 1 with a CASE statement for better readability if the bitwise operation is not preferred. However, this usually doesn't affect the performance significantly.

  • Subqueries: Although not necessary for this specific problem, a subquery could be used to first filter the rows based on one condition and then filter the result of the subquery based on the second condition. However, this approach is less efficient than combining the conditions in the WHERE clause.

In summary, the provided SQL solution is efficient and directly addresses the problem requirements. The time and space complexity are typical for database query operations involving filtering and sorting.