Solution Explanation for Consecutive Available Seats

The problem requires finding consecutive available seats in a cinema table. The table has seat_id and free (boolean) columns. We need to return the seat_ids of all consecutive available seats, ordered ascendingly. The solutions presented use SQL.

Solution Approaches and Code

Three different SQL approaches are provided:

Solution 1: Self-Join

This approach uses a self-join to find consecutive available seats. It joins the Cinema table with itself, comparing each row with the next one.

• Logic: The join condition ABS(a.seat_id - b.seat_id) = 1 checks for adjacent seats. a.free AND b.free ensures both seats are available. The DISTINCT keyword avoids duplicates if a seat is part of multiple consecutive groups.

• MySQL Code:

SELECT DISTINCT a.seat_id
FROM
    Cinema AS a
    JOIN Cinema AS b ON ABS(a.seat_id - b.seat_id) = 1 AND a.free AND b.free
ORDER BY 1;

• Time Complexity: O(N^2) in the worst case due to the self-join, where N is the number of seats. The actual performance depends on the database's optimization.

Solution 2: Window Function (LAG/LEAD)

This solution leverages window functions (LAG and LEAD) to access the previous and next rows' free status.

• Logic: LAG(free) OVER (ORDER BY seat_id) gets the free value of the previous seat. LEAD(free) OVER (ORDER BY seat_id) gets the free value of the next seat. The query then checks if the current seat and either the previous or next seat are free (a = 2 or b = 2).

• MySQL Code:

WITH
    T AS (
        SELECT
            seat_id,
            (free + (LAG(free) OVER (ORDER BY seat_id))) AS a,
            (free + (LEAD(free) OVER (ORDER BY seat_id))) AS b
        FROM Cinema
    )
SELECT seat_id
FROM T
WHERE a = 2 OR b = 2;

• Time Complexity: O(N) because window functions generally have linear time complexity.

Solution 3: Window Function (SUM() OVER())

Similar to Solution 2, but using SUM() OVER() for a more concise approach.

• Logic: This sums the free column (treating 1 as true and 0 as false) within a window of the current and adjacent rows. If the sum (cnt) is greater than 1, it means at least two consecutive seats are free.

• MySQL Code:

WITH
    T AS (
        SELECT
            *,
            SUM(free = 1) OVER (
                ORDER BY seat_id
                ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING
            ) AS cnt
        FROM Cinema
    )
SELECT seat_id
FROM T
WHERE free = 1 AND cnt > 1
ORDER BY 1;

• Time Complexity: O(N), similar to Solution 2.

Conclusion

Solutions 2 and 3 using window functions are generally preferred over the self-join approach (Solution 1) because of their better time complexity. Window functions are optimized for such operations and usually provide better performance in databases that support them. The choice between solutions 2 and 3 depends on personal preference; both achieve the same result efficiently.