MediumArrayUpdated Sep 2026

849. Maximize Distance to Closest Person

Asked at Adobe, Roblox

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

2

Problem

You are given an array seats that describes one row of seats. seats[i] = 1 means a person is already sitting in seat i. seats[i] = 0 means seat i is empty. There is always at least one empty seat and at least one occupied seat.

Alex wants to pick one empty seat to sit in. His distance to the closest person is the number of seats between him and the nearest occupied seat. He wants this distance to be as large as possible.

Return that largest possible distance. Note that the two ends of the row are open: if Alex sits at the very first or very last seat, only the people on one side matter.

Pick the empty seat with the farthest nearest person

seats10001010123456personpersonSitting at index 2 gives distance 2 to the nearest person
Seat 2 is the best choice: the closest person is 2 seats away, while every other empty seat has a person right next to it.

Constraints

  • ●2 <= seats.length <= 2 * 10^4
  • ●seats[i] is 0 or 1
  • ●At least one seat is empty
  • ●At least one seat is occupied

Examples

Example 1
Inputseats = [1,0,0,0,1,0,1]
Output2
WhySeat 2 is 2 seats away from the person at seat 0 and 2 seats away from the person at seat 4, so the closest person is at distance 2. Every other empty seat has a person only 1 seat away.
Example 2
Inputseats = [1,0,0,0]
Output3
WhyAlex takes the last seat, index 3. The only person is at index 0, which is 3 seats away. No other empty seat can do better.
Example 3
Inputseats = [0,1]
Output1
WhyThe only empty seat is index 0, and the person at index 1 is 1 seat away.

Asked At

2 companies
CompanyDifficulty
AdobeMediumView all Adobe questions →
RobloxMediumView all Roblox questions →

How to Think About It

1

Brute force: for each empty seat, scan left and right to find the nearest occupied seat, and track the maximum distance.

2

Optimize with a single pass by tracking the last occupied seat seen so far.

3

Handle three cases: empty seats before the first person, empty seats between two people, and empty seats after the last person.

4

For leading/trailing empty seats, the distance is the count of consecutive zeros from the edge.

5

For empty seats between two people, the distance to the closest person is half the gap (integer division).

Optimal Approach

Track the index of the last person seen. For leading zeros, set last to -1 so the distance calculation works correctly. For each empty seat, compute the distance to the nearest person by considering both the previous person (last) and the next person (found by looking ahead). Alternatively, do two passes: one left-to-right recording the distance to the nearest person on the left, and one right-to-left for the nearest on the right, taking the minimum at each seat. O(n) time, O(1) space.

Track the last person seen

seatsgap 4 → 4//2 = 210001010123456Step 1 — between two people, the best seat is in the middle, sothe distance is gap // 2seatstrailing zeros = 010001010123456Step 2 — after the last person, the distance is the number oftrailing empty seatsleading zeros → ibetween people → (i - last) // 2trailing zeros → n - 1 - lastanswer = max of all three
For each gap we take half the gap length; the two open ends use the full run of zeros.
ComplexityTime O(n)Space O(1)One left-to-right pass over the seats, keeping only the index of the last person seen.

What Trips People Up in Real Interviews

1

Clarify: seats are a straight row, not circular — edge seats only have one neighbor.

2

Edge case: [1,0,0,0] — the closest person is at index 0, answer is 3.

3

Edge case: [0,0,1] — closest person is at index 2, answer is 2.

4

Edge case: [0,1,0,0,1,0] — the middle empty seat between two people at distance 2 from each, answer is 2.

5

The problem can also be solved with two passes (left-to-right then right-to-left) which is cleaner for interviews.

Solution Code

O(n) time
def maxDistToClosest(seats):
    n = len(seats)
    last = -1
    result = 0
    for i in range(n):
        if seats[i] == 1:
            if last == -1:
                result = max(result, i)
            else:
                result = max(result, (i - last) // 2)
            last = i
    result = max(result, n - 1 - last)
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Maximize Distance to Closest Person problem?

You are given an array seats where seats[i] = 1 represents a person sitting in the i-th seat and seats[i] = 0 represents an empty seat. There is at least one empty seat and at least one person sitting. Find the maximum distance to the closest person from any empty seat. The distance is the number of seats between them.

How do you solve Maximize Distance to Closest Person?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Maximize Distance to Closest Person?

Maximize Distance to Closest Person is asked at Adobe, Roblox. It is a medium difficulty problem.

What are common mistakes on Maximize Distance to Closest Person?
  • Clarify: seats are a straight row, not circular — edge seats only have one neighbor.
  • Edge case: [1,0,0,0] — the closest person is at index 0, answer is 3.
  • Edge case: [0,0,1] — closest person is at index 2, answer is 2.
  • Edge case: [0,1,0,0,1,0] — the middle empty seat between two people at distance 2 from each, answer is 2.
  • The problem can also be solved with two passes (left-to-right then right-to-left) which is cleaner for interviews.