LeetCode 603: Consecutive Available Seats Solution in Python – A Step-by-Step Guide

What Is LeetCode 603: Consecutive Available Seats?

In LeetCode 603: Consecutive Available Seats, you’re given a cinema table with columns seat_id (unique seat number) and free (1 for available, 0 for taken), representing seats in a single row. Your task is to determine if there are k consecutive available seats. For example, if seats 1, 2, 3 are free (1) and seat 4 is taken (0), you can find 3 consecutive free seats. This problem tests your ability to handle sequential data, often framed as an SQL query, but we’ll solve it in Python with a coding twist.

Problem Statement

• Input: A list of records (or table rows) with [seat_id, free], and an integer k.
• Output: Boolean—True if there are k consecutive free seats, False otherwise.
• Rules:
• Seats are numbered sequentially (1, 2, 3, …).
• free = 1 means available; free = 0 means occupied.

Constraints

• Table has at least 1 row.
• 1 <= seat_id <= 10⁵.
• 1 <= k <= number of seats.
• free is 0 or 1.

Examples

• Input:
``` seat_id | free 1 | 1 2 | 0 3 | 1 4 | 1 5 | 1 ```

k = 3

• Output: True (Seats 3, 4, 5 are free)

seat_id | free 1 | 1 2 | 1 3 | 0k = 3

• Output: False (No 3 consecutive free seats)

These examples set the stage—let’s find those seats!

Understanding the Problem: Finding Consecutive Free Seats

To solve LeetCode 603: Consecutive Available Seats in Python, we need to process a list of seat records and check if there’s a stretch of k consecutive seats where free = 1. A naive approach might scan every possible k-length segment, but we can do better. We’ll use:

• Best Solution (Union-Find): O(n * α(n)) time, O(n) space—fast and scalable for dynamic grouping.
• Alternative Solution (Iteration with Counting): O(n) time, O(1) space—simple but less flexible.

Let’s dive into the union-find solution, breaking it down for beginners.

Best Solution: Union-Find for Dynamic Seat Tracking

Why This Is the Best Solution

The union-find approach shines for LeetCode 603 because it’s efficient—O(n * α(n)) time, where α is the near-constant inverse Ackermann function—and dynamically groups consecutive free seats. It’s perfect for tracking clusters and checking their sizes, making it adaptable if the problem evolves (e.g., multiple queries). It’s like linking empty seats into chains and measuring them!

How It Works

Think of this as connecting free seats into groups:

• Step 1: Initialize Union-Find:
• Use a parent array where each free seat points to its group’s root.
• Track group sizes with a size array.
• Step 2: Union Free Seats:
• Sort seats by ID.
• For each free seat, union it with the previous free seat if consecutive.
• Step 3: Check Sizes:
• After grouping, check if any group has size >= k.
• Step 4: Return Result:
• Return True if a valid group exists, False otherwise.

It’s like chaining empty seats and counting the links!

Step-by-Step Example

Example:

Copy codeseat_id | free
1       | 1
2       | 0
3       | 1
4       | 1
5       | 1

k = 3

• Initialize: parent = [-1, -1, -1, -1, -1], size = [0, 0, 0, 0, 0].
• Sort: Already sorted by seat_id.
• Process Free Seats:
• Seat 1 (free): parent[0] = 0, size[0] = 1.
• Seat 2 (taken): Skip.
• Seat 3 (free): parent[2] = 2, size[2] = 1.
• Seat 4 (free): Consecutive with 3, union(2, 3), parent[2] = 2, size[2] = 2.
• Seat 5 (free): Consecutive with 4, union(2, 3), parent[3] = 2, size[2] = 3.
• Check: size[2] = 3 >= k, True.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def consecutiveSeats(self, seats: List[List[int]], k: int) -> bool:
        # Step 1: Sort by seat_id (assuming input may not be sorted)
        seats.sort(key=lambda x: x[0])
        n = len(seats)

        # Step 2: Initialize union-find
        parent = [-1] * n  # -1 means not grouped yet
        size = [0] * n     # Size of each group

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])  # Path compression
            return parent[x]

        def union(x, y):
            root_x = find(x)
            root_y = find(y)
            if root_x != root_y:
                parent[root_y] = root_x
                size[root_x] += size[root_y]

        # Step 3: Group consecutive free seats
        for i in range(n):
            if seats[i][1] == 1:  # Free seat
                parent[i] = i     # Set as its own root
                size[i] = 1       # Initial size
                # Union with previous free seat if consecutive
                if i > 0 and seats[i-1][1] == 1 and seats[i][0] == seats[i-1][0] + 1:
                    union(i-1, i)

        # Step 4: Check for k consecutive seats
        for i in range(n):
            if size[i] >= k:
                return True

        return False

• Line 4: Sort seats by ID (ensures order).
• Lines 7-9: Setup:
• parent: Tracks group roots.
• size: Tracks group sizes.
• Lines 11-15: find: Finds root with path compression.
• Lines 17-22: union: Merges groups, updates size.
• Lines 25-31: Group free seats:
• Set root and size for free seats.
• Union with previous if consecutive.
• Lines 34-36: Check for k or more.
• Time Complexity: O(n * α(n))—near-linear with union-find.
• Space Complexity: O(n)—arrays for tracking.

This is like a seat linker—group and check fast!

Alternative Solution: Iteration with Counting

Why an Alternative Approach?

The iteration approach scans the seats once, counting consecutive free seats—O(n) time, O(1) space. It’s simpler and uses minimal memory, making it intuitive for beginners, though less flexible for dynamic scenarios. It’s like walking down the row, counting empty seats as you go!

How It Works

Picture this as a seat-by-seat check:

• Step 1: Sort seats by ID.
• Step 2: Iterate, counting consecutive free seats.
• Step 3: Reset count when a taken seat appears.
• Step 4: Return True if count ever hits k.

It’s like tallying empty seats on the fly!

Step-by-Step Example

Example:

Copy codeseat_id | free
1       | 1
2       | 0
3       | 1
4       | 1
5       | 1

k = 3

• Count:
• Seat 1: 1 free.
• Seat 2: 0, reset to 0.
• Seat 3: 1 free.
• Seat 4: 2 free.
• Seat 5: 3 free, >= k.
• Output: True.

Code for Iteration Approach

Copy codeclass Solution:
    def consecutiveSeats(self, seats: List[List[int]], k: int) -> bool:
        seats.sort(key=lambda x: x[0])
        count = 0

        for i in range(len(seats)):
            if seats[i][1] == 1:
                count += 1
                if count >= k:
                    return True
            else:
                count = 0  # Reset on taken seat

        return False

• Line 4: Initialize count.
• Lines 6-11: Iterate:
• Increment for free seats.
• Reset for taken seats.
• Check if k is reached.
• Time Complexity: O(n)—single pass.
• Space Complexity: O(1)—just a counter.

It’s a simple seat sweep!

Comparing the Two Solutions

• Union-Find (Best):
• Pros: O(n * α(n)) time, O(n) space, flexible for extensions.
• Cons: Union-find logic.
• Iteration (Alternative):
• Pros: O(n) time, O(1) space, super simple.
• Cons: Less adaptable.

Iteration wins for simplicity, union-find for scalability.

Additional Examples and Edge Cases

• Input: [[1,1], [2,1]], k = 2
• Output: True.
• Input: [[1,1], [2,0], [3,1]], k = 2
• Output: False.

Both handle these well.

Complexity Breakdown

• Union-Find: Time O(n * α(n)), Space O(n).
• Iteration: Time O(n), Space O(1).

Iteration is leaner.

Key Takeaways

• Union-Find: Dynamic grouping—smart!
• Iteration: Simple counting—clear!
• Sequences: Consecutive checks are fun.
• Python Tip: Lists rule—see Python Basics.

Final Thoughts: Grab Those Seats

LeetCode 603: Consecutive Available Seats in Python is a cool sequence puzzle. Union-find offers power and flexibility, while iteration keeps it light and easy. Want more? Try LeetCode 128: Longest Consecutive Sequence or LeetCode 674: Longest Continuous Increasing Subsequence. Ready to find your spot? Head to Solve LeetCode 603 on LeetCode and check those seats today!