Best Seat

Tags

Best Seat

Category

Arrays

Difficulty

Medium

Problem Statement

You are given an array representing a row of seats, where 1 means occupied and 0 means empty. Find the seat index that gives the most space from the closest occupied seat on either side. The first and last seats are always occupied. If there are multiple best seats, return the one with the lowest index.

Intuition

The best seat is in the middle of the longest contiguous run of empty seats. By scanning the array for runs of zeros between ones, we can identify the longest gap and place the person at its center, maximizing the minimum distance to the nearest occupied neighbor.

Approach

  1. Initialize bestSeat = -1 and maxSpace = 0.
  2. Iterate through the array with a pointer i.
  3. When seats[i] == 0, find the end of the contiguous empty run (call it j).
  4. Compute the available space as j - i (length of the empty segment).
  5. If this space exceeds maxSpace, update maxSpace and set bestSeat = i + (j - i) / 2 (integer division gives the middle index, biased left).
  6. Move i to j and continue scanning.
  7. Return bestSeat.

Pseudocode

function bestSeat(seats):
    bestSeat = -1
    maxSpace = 0
    i = 0

    while i < length(seats):
        if seats[i] == 1:
            i += 1
            continue

        j = i
        while j < length(seats) and seats[j] == 0:
            j += 1

        availableSpace = j - i
        if availableSpace > maxSpace:
            maxSpace = availableSpace
            bestSeat = i + (j - i) / 2   // integer division

        i = j

    return bestSeat

Time & Space Complexity

  • Time: O(n) — single pass through the array; the inner loop does not revisit elements.
  • Space: O(1) — only a few variables are used.

Key Insights

  • The middle of a gap of length L gives a minimum distance of floor(L / 2) to the nearest occupied seat.
  • Integer division naturally handles both odd and even gap lengths, biasing toward the left seat when there is a tie.
  • The first and last seats being occupied guarantees every empty run is bounded on both sides.

Edge Cases

  • No empty seats (all 1s): return -1.
  • Only one empty seat: return its index.
  • Multiple gaps of the same maximum length: the first one encountered (lowest index) is chosen.
  • Two adjacent empty seats: the best seat is the left one (index bias from integer division).

Linked mentions