LeetCode 620 - Not Boring Movies

The problem is asking us to query a database table called Cinema and return a filtered set of movies based on two conditions: the movie ID must be odd, and its description must not be "boring". The result must then be sorted in descending order by the movie's rating.

leetcodeeasydatabase

LeetCode Problem 620

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem is asking us to query a database table called Cinema and return a filtered set of movies based on two conditions: the movie ID must be odd, and its description must not be "boring". The result must then be sorted in descending order by the movie's rating.

In other words, for every row in the Cinema table, we check if the id is odd using a modulo operation (id % 2 = 1) and if the description is not equal to the string "boring". Only rows that satisfy both conditions are included in the output. The output is expected to retain all columns (id, movie, description, rating) but must be sorted so that higher-rated movies appear first.

Key constraints and clarifications include: id is unique, rating is a float in the range 0 to 10 with 2 decimal places, and there are no nulls mentioned in the schema. Important edge cases could include movies with odd IDs but "boring" descriptions, all IDs being even, or multiple movies having the same rating (tie-breaker is not specified, so default SQL ordering is sufficient).

Approaches

The brute-force approach is straightforward: scan the entire Cinema table row by row, filter rows that satisfy both conditions (odd id and description != "boring"), store the results in a temporary structure, and finally sort them by rating in descending order. This approach is correct but relies on full table scanning, which can be inefficient if the table is very large.

The optimal approach leverages SQL filtering and ordering directly. Using a WHERE clause, we can filter rows by id % 2 = 1 and description != 'boring', and then sort the result with ORDER BY rating DESC. SQL engines handle filtering and sorting efficiently with indices if available, so this is both concise and performant.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Scan all rows, filter manually, sort in application code
Optimal O(n log n) O(1) Use SQL WHERE + ORDER BY to push filtering and sorting to the database

Algorithm Walkthrough

  1. Start by writing a SELECT statement to retrieve all columns from the Cinema table. We want to preserve id, movie, description, and rating.
  2. Add a WHERE clause to filter rows. Use id % 2 = 1 to select only rows with odd IDs.
  3. Extend the WHERE clause to exclude movies with "boring" in the description. Combine with the first condition using AND.
  4. Add an ORDER BY rating DESC clause to sort the results by the rating column in descending order so that higher-rated movies appear first.
  5. Execute the SQL query. The database engine will efficiently apply filtering and sorting, returning only the rows that satisfy both conditions, sorted as required.

Why it works: Filtering with WHERE ensures only relevant rows are included, while ORDER BY guarantees the required sort order. The combination of these clauses produces the correct output in a single query without post-processing.

Python Solution

# Python solution is not directly applicable since this is a SQL problem
# If required for execution via Python DB API:
import sqlite3
from typing import List, Tuple

def not_boring_movies(conn: sqlite3.Connection) -> List[Tuple[int, str, str, float]]:
    query = """
    SELECT id, movie, description, rating
    FROM Cinema
    WHERE id % 2 = 1 AND description != 'boring'
    ORDER BY rating DESC
    """
    cursor = conn.cursor()
    cursor.execute(query)
    return cursor.fetchall()

The Python implementation uses a database connection to execute the SQL query. The query selects rows with odd IDs and non-boring descriptions and orders them by rating. The fetchall() call returns all rows as a list of tuples.

Go Solution

// Go solution using database/sql package
package main

import (
    "database/sql"
    _ "github.com/go-sql-driver/mysql"
)

type Movie struct {
    ID          int
    Movie       string
    Description string
    Rating      float64
}

func NotBoringMovies(db *sql.DB) ([]Movie, error) {
    query := `
    SELECT id, movie, description, rating
    FROM Cinema
    WHERE id % 2 = 1 AND description != 'boring'
    ORDER BY rating DESC
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var result []Movie
    for rows.Next() {
        var m Movie
        if err := rows.Scan(&m.ID, &m.Movie, &m.Description, &m.Rating); err != nil {
            return nil, err
        }
        result = append(result, m)
    }
    return result, nil
}

In Go, the solution defines a Movie struct and queries the database using db.Query. The filtering and sorting are handled by SQL. Rows are scanned into the struct slice, which is returned to the caller.

Worked Examples

Given the input:

+----+------------+-------------+--------+
| 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    |

Step 1: Filter odd IDs → rows with id 1, 3, 5.

Step 2: Exclude "boring" description → rows with id 1, 5.

Step 3: Sort by rating descending → row with id 5 first, then row with id 1.

Result:

+----+------------+-------------+--------+
| id | movie      | description | rating |
+----+------------+-------------+--------+
| 5  | House card | Interesting | 9.1    |
| 1  | War        | great 3D    | 8.9    |

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Filtering requires scanning all n rows, and sorting by rating is O(n log n)
Space O(1) SQL query produces result in database engine; minimal extra space required

Even though filtering is O(n), the dominant factor is sorting, which gives O(n log n). No additional data structures are needed beyond the query result.

Test Cases

# Basic example from problem statement
assert not_boring_movies(conn) == [(5, "House card", "Interesting", 9.1), (1, "War", "great 3D", 8.9)]

# All IDs even
# Should return empty
# Cinema: [(2, "Movie A", "good", 7.5), (4, "Movie B", "fun", 8.0)]
assert not_boring_movies(conn_even_ids) == []

# All descriptions boring
# Should return empty
# Cinema: [(1, "Movie A", "boring", 9.0), (3, "Movie B", "boring", 8.5)]
assert not_boring_movies(conn_boring) == []

# Mixed odd/even, multiple with same rating
# Cinema: [(1, "A", "fun", 9.0), (3, "B", "fun", 9.0)]
assert not_boring_movies(conn_tied_ratings) == [(1, "A", "fun", 9.0), (3, "B", "fun", 9.0)]
Test Why
Basic example Validates standard filtering and sorting
All IDs even Validates filtering by odd ID
All descriptions boring Validates filtering by description
Tied ratings Validates sorting behavior when ratings are equal

Edge Cases

One important edge case is when all movie IDs are even. In this scenario, filtering by id % 2 = 1 would result in zero rows. The SQL query correctly handles this by returning an empty result set.

Another edge case occurs when all descriptions are "boring". Even if some IDs are odd, they should not appear in the output. The description != 'boring' condition ensures these rows are excluded.

A third edge case is when multiple movies have the same rating. Since the problem does not specify tie-breaking beyond rating, any order among those with equal rating is acceptable. The ORDER BY rating DESC clause handles descending sort correctly, leaving the relative order of equal-rated movies up to the SQL engine, which is acceptable for this problem.