LeetCode 3140 - Consecutive Available Seats II

LeetCode Problem 3140

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to analyze a cinema seating table and identify the longest continuous block of available seats.

The input table is named Cinema and contains two columns:

Column	Meaning
seat_id	Unique seat number
free	Whether the seat is available, 1 means free and 0 means occupied

A consecutive sequence means that seat IDs increase continuously by 1, and every seat in that range is free.

For example, if seats 3, 4, and 5 are all free, then they form one consecutive available sequence of length 3.

The task is not simply to find all available seats. Instead, we must:

1. Group adjacent free seats into consecutive ranges.
2. Compute the length of each range.
3. Return only the longest range or ranges.
4. Output:

• the first seat ID in the range,
• the last seat ID in the range,
• the length of the range.

The result must be sorted by first_seat_id in ascending order.

The problem also guarantees an important property:

• There will be at most one longest consecutive sequence.
• If multiple sequences share the same maximum length, all of them must be returned.

This means we should still write a general solution that can handle ties correctly.

A few important edge cases immediately stand out:

• All seats may be occupied, producing no valid sequence.
• All seats may be free, producing one large sequence.
• A free sequence may contain only one seat.
• Multiple free sequences may have identical lengths.
• Seat IDs are auto incremented, so consecutive seat IDs correspond naturally to neighboring seats.

The key challenge is correctly detecting boundaries between consecutive groups of free seats.

Approaches

Brute Force Approach

A brute force solution would examine every free seat and try to expand outward to determine the full consecutive segment it belongs to.

For every seat marked as free:

1. Start from that seat.
2. Continue checking the next seat IDs one by one.
3. Stop when an occupied seat is found.
4. Record the segment length.
5. Repeat for all seats.

This approach is correct because every possible consecutive sequence is explored explicitly.

However, the problem is that many ranges are recomputed repeatedly. If there is a long free block of length k, then each seat inside that block may rescan much of the same sequence again.

For example:

1 1 1 1 1

Starting from each seat redundantly traverses the same range.

This leads to quadratic behavior in the worst case.

Optimal Approach

The better solution uses the classic "gaps and islands" technique with SQL window functions.

The key insight is that consecutive free seats can be grouped together using the difference between:

• the actual seat ID
• the row number among free seats

For consecutive numbers:

seat_id - row_number

remains constant.

Example:

seat_id	row_number	difference
3	1	2
4	2	2
5	3	2

Since the difference is identical, these rows belong to the same consecutive group.

Once groups are identified, we can:

1. Compute the minimum seat ID.
2. Compute the maximum seat ID.
3. Compute the count of seats.
4. Find the maximum count.
5. Return all groups matching that maximum.

This avoids repeated rescanning and processes the table efficiently.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Repeatedly rescans overlapping ranges
Optimal	O(n log n)	O(n)	Uses window functions and grouping efficiently

Algorithm Walkthrough

1. Filter the table to include only free seats.

Occupied seats cannot belong to any valid sequence, so they are removed immediately. 2. Assign a row number to each free seat ordered by seat_id.

This creates a sequential index among only the available seats. 3. Compute a grouping key using:

seat_id - row_number

Consecutive seat IDs produce the same difference value, which naturally groups adjacent free seats together. 4. Group rows by this computed key.

Every group now represents one consecutive block of available seats. 5. For each group, compute:

• MIN(seat_id) as the first seat
• MAX(seat_id) as the last seat
• COUNT(*) as the sequence length

6. Find the maximum sequence length among all groups.
7. Return every group whose length equals the maximum.
8. Sort the final result by first_seat_id.

Why it works

The critical invariant is that for consecutive integers:

seat_id - row_number

stays constant.

Whenever a gap appears, the seat ID increases but the row number only increments by one, causing the difference to change. This naturally separates consecutive runs into distinct groups.

Because every free seat belongs to exactly one such group, and every group corresponds to exactly one maximal consecutive sequence, the algorithm correctly identifies all longest ranges.

Python Solution

# Write your MySQL query statement below
WITH free_seats AS (
    SELECT
        seat_id,
        seat_id - ROW_NUMBER() OVER (ORDER BY seat_id) AS grp
    FROM Cinema
    WHERE free = 1
),
groups AS (
    SELECT
        MIN(seat_id) AS first_seat_id,
        MAX(seat_id) AS last_seat_id,
        COUNT(*) AS consecutive_seats_len
    FROM free_seats
    GROUP BY grp
),
max_group AS (
    SELECT MAX(consecutive_seats_len) AS max_len
    FROM groups
)
SELECT
    first_seat_id,
    last_seat_id,
    consecutive_seats_len
FROM groups
WHERE consecutive_seats_len = (
    SELECT max_len
    FROM max_group
)
ORDER BY first_seat_id;

The first common table expression filters the table to include only available seats and computes the grouping key using ROW_NUMBER().

The second common table expression aggregates seats belonging to the same consecutive sequence. It calculates the starting seat, ending seat, and sequence length.

The third common table expression determines the maximum sequence length across all groups.

Finally, the main query returns only those groups whose length matches the maximum length.

The ordering requirement is satisfied using ORDER BY first_seat_id.

Go Solution

// There is no Go solution for SQL database problems on LeetCode.
// The expected submission is a MySQL query.

Unlike algorithmic problems where LeetCode expects executable code in multiple languages, database problems require only an SQL query submission. Therefore, no Go implementation is applicable for this problem.

Worked Examples

Example 1

Input:

seat_id	free
1	1
2	0
3	1
4	1
5	1

Step 1: Filter Free Seats

| seat_id |

|---|---|

| 1 |

| 3 |

| 4 |

| 5 |

Step 2: Compute Row Numbers

seat_id	row_number
1	1
3	2
4	3
5	4

Step 3: Compute Group Key

seat_id	row_number	grp
1	1	0
3	2	1
4	3	1
5	4	1

Seats 3, 4, and 5 share the same group key, so they form one consecutive block.

Step 4: Aggregate Groups

grp	first_seat_id	last_seat_id	length
0	1	1	1
1	3	5	3

Step 5: Find Maximum Length

Maximum length is 3.

Final Output

first_seat_id	last_seat_id	consecutive_seats_len
3	5	3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Window ordering and grouping require sorting
Space	O(n)	Intermediate grouped results are stored

The dominant cost comes from sorting rows by seat_id for the window function. Grouping and aggregation then process each row once. The intermediate common table expressions also require additional storage proportional to the number of rows.

Test Cases

# Example case
# Longest consecutive sequence in the middle
cinema = [
    (1, 1),
    (2, 0),
    (3, 1),
    (4, 1),
    (5, 1),
]

# All seats occupied
# Should return empty result
cinema = [
    (1, 0),
    (2, 0),
    (3, 0),
]

# All seats free
# Entire table is one sequence
cinema = [
    (1, 1),
    (2, 1),
    (3, 1),
    (4, 1),
]

# Multiple sequences with same length
# Both sequences should be returned
cinema = [
    (1, 1),
    (2, 1),
    (3, 0),
    (4, 1),
    (5, 1),
]

# Single free seat
# Length should be 1
cinema = [
    (1, 0),
    (2, 1),
    (3, 0),
]

# Consecutive block at beginning
cinema = [
    (1, 1),
    (2, 1),
    (3, 0),
    (4, 0),
]

# Consecutive block at end
cinema = [
    (1, 0),
    (2, 0),
    (3, 1),
    (4, 1),
]

# Alternating free and occupied seats
# Every sequence length is 1
cinema = [
    (1, 1),
    (2, 0),
    (3, 1),
    (4, 0),
    (5, 1),
]

Test Summary

Test	Why
Example input	Validates standard consecutive grouping
All occupied	Ensures empty result handling
All free	Ensures full table grouping works
Multiple equal groups	Verifies tie handling
Single free seat	Tests minimum valid sequence
Block at beginning	Verifies leading boundary handling
Block at end	Verifies trailing boundary handling
Alternating seats	Tests repeated short groups

Edge Cases

All Seats Occupied

If every seat has free = 0, then there are no valid consecutive sequences.

A buggy implementation might incorrectly return a zero length range or fail during aggregation. This solution handles the case naturally because the filtered free_seats table becomes empty, producing no groups and therefore no output rows.

All Seats Free

If every seat is available, the entire table forms one large consecutive sequence.

This case validates that the grouping logic does not accidentally split consecutive seats unnecessarily. Since the difference seat_id - row_number remains constant for all rows, the algorithm correctly produces a single group.

Multiple Maximum Length Sequences

Although the statement says there will be at most one longest sequence, it also specifies that ties should be included if they exist.

A naive implementation might use LIMIT 1 after sorting by length, which would incorrectly discard other valid sequences. This solution instead computes the maximum length separately and returns all groups matching that value.