Student Seating - Assign Seats Maximizing Distance from Existing Students

Question

## Problem

A row of `n` seats is represented as a binary array where `1 = occupied`, `0 = empty`. A new student wants to sit as far as possible from the nearest occupied seat.

Return the maximum distance achievable and the index of the optimal seat. If multiple seats achieve the same distance, return the smallest index.

```python
def best_seat(seats: list[int]) -> tuple[int, int]:
    # returns (max_distance, seat_index)
```

## Example

```
seats = [1, 0, 0, 0, 1, 0, 1]
best_seat(seats) -> (2, 2)
# index 2 is distance 2 from index 0 and distance 2 from index 4
# index 5 is distance 1 from index 4 and index 6
```

Assume at least one seat is occupied and at least one is empty.

## Follow-ups

1. What if the seats are arranged in a 2D grid instead of a row?
2. Extend to seat `k` students sequentially, each choosing the best available seat after the previous one sits down.
3. How does the solution change if seats at the ends of the row are treated as walls (distance 0 to boundary)?
4. Write a SQL query to find the best seat if the seating data is stored in a table `seats(id, occupied)`.

Student Seating - Assign Seats Maximizing Distance from Existing Students

Question Details

Full Details

Topics

More from Google