Maximize Distance to Closest Person

Medium
1837.

Maximize Distance to Closest Person

Maximize Distance to Closest Person is a medium coding problem on arrays and two pointers, asked in Amazon, Google and Microsoft interviews.

A row of seats is given as an array seats, where seats[i] = 1 means seat i is taken and seats[i] = 0 means it is empty. At least one seat is empty and at least one is taken.

Alex wants to sit in an empty seat that is as far as possible from the nearest person. Return that largest possible distance to the closest person.

Example 1

Input
seats = [0,0,1,0,0,0,0,0,1]
Output
3
Explanation
In the middle gap of five empty seats, the centre seat (index 5) is 3 away from both neighbours. The leading gap only gives 2.

Example 2

Input
seats = [1,0,0,0,0]
Output
4
Explanation
The last seat is 4 away from the only person.

Example 3

Input
seats = [1,0]
Output
1

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} seats
 * @return {number}
 */
var maxDistToClosest = function(seats) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximize Distance to Closest Person — Problem & Solution

Maximize Distance to Closest Person solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximize Distance to Closest Person is a medium coding problem on arrays and two pointers, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Arrays, Two Pointers
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A row of seats is given as an array seats, where seats[i] = 1 means seat i is taken and seats[i] = 0 means it is empty. At least one seat is empty and at least one is taken.

Alex wants to sit in an empty seat that is as far as possible from the nearest person. Return that largest possible distance to the closest person.

Example 1

Input: seats = [0,0,1,0,0,0,0,0,1]
Output: 3
Explanation: In the middle gap of five empty seats, the centre seat (index 5) is 3 away from both neighbours. The leading gap only gives 2.

Example 2

Input: seats = [1,0,0,0,0]
Output: 4
Explanation: The last seat is 4 away from the only person.

Example 3

Input: seats = [1,0]
Output: 1

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

Hints for Maximize Distance to Closest Person

  1. Hint 1

    The empty seats form gaps between people. Treat a gap between two people differently from a gap at either end of the row.

  2. Hint 2

    In an interior gap of k empty seats, the best seat is in the middle, at distance (k + 1) / 2 (integer division).

  3. Hint 3

    At the ends there is nobody on one side, so a leading or trailing gap of k seats gives distance k.

How to solve Maximize Distance to Closest Person

Only the lengths of the runs of empty seats matter: an interior run of k seats offers ceil(k / 2), and a run touching either end of the row offers k.

Approach

  1. Find the first and last occupied seats first and last.
  2. Start with best = max(first, n - 1 - last) — the edge gaps.
  3. Walk the occupied seats in order; for consecutive people at p and q, update best = max(best, (q - p) / 2).
  4. Return best.

Why it works

For a seat in an interior gap between people at p and q, the distance to the closest person is min(i - p, q - i), maximised at the middle with value floor((q - p) / 2), which equals ceil(k / 2) for k = q - p - 1 empty seats. In an edge gap only one person is near, so the far end of the gap is best, at distance equal to the gap length.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Edge gaps are not halved: [1,0,0,0,0] answers 4, not 2.
  • For an interior gap use the distance between the two people, (q - p) / 2, not the number of empty seats divided by two.

Reference solution

Python

from typing import List

def maxDistToClosest(seats: List[int]) -> int:
    n = len(seats)
    prev = -1
    best = 0
    for i, s in enumerate(seats):
        if s == 1:
            best = max(best, i if prev < 0 else (i - prev) // 2)
            prev = i
    return max(best, n - 1 - prev)

Java

public static int maxDistToClosest(int[] seats) {
    int n = seats.length, prev = -1, best = 0;
    for (int i = 0; i < n; i++) {
        if (seats[i] != 1) continue;
        best = Math.max(best, prev < 0 ? i : (i - prev) / 2);
        prev = i;
    }
    return Math.max(best, n - 1 - prev);
}

C++

int maxDistToClosest(vector<int>& seats) {
    int n = seats.size(), prev = -1, best = 0;
    for (int i = 0; i < n; i++) {
        if (seats[i] != 1) continue;
        best = max(best, prev < 0 ? i : (i - prev) / 2);
        prev = i;
    }
    return max(best, n - 1 - prev);
}

JavaScript

var maxDistToClosest = function(seats) {
    var n = seats.length, prev = -1, best = 0;
    for (var i = 0; i < n; i++) {
        if (seats[i] !== 1) continue;
        best = Math.max(best, prev < 0 ? i : Math.floor((i - prev) / 2));
        prev = i;
    }
    return Math.max(best, n - 1 - prev);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Two Pointers Technique