How hard is LeetCode 849. Maximize Distance to Closest Person?

LeetCode 849. Maximize Distance to Closest Person is rated Medium on LeetCode.

What is the time complexity of LeetCode 849. Maximize Distance to Closest Person?

The Python solution on this page runs in O(n), where n is the length of the array \textit{seats}.

What is the space complexity of LeetCode 849. Maximize Distance to Closest Person?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 849. Maximize Distance to Closest Person cover?

LeetCode 849. Maximize Distance to Closest Person is tagged Array on LeetCode.

Maximize Distance to Closest Person — LeetCode 849 Python Solution

MediumArray

Problem: #849
Reading time: 2 min
Source: leetcode.com

The problem

You are given an array representing a row of seats where seats[i] = 1 represents a person sitting in the ith seat, and seats[i] = 0 represents that the ith seat is empty (0-indexed). There is at least one empty seat, and at least one person sitting.

Example

Input: seats = [1,0,0,0,1,0,1]
Output: 2
Explanation: If Alex sits in the second open seat (i.e. seats[2]), then the closest person has distance 2.

Python solution

Python

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        first = last = None
        d = 0
        for i, c in enumerate(seats):
            if c:
                if last is not None:
                    d = max(d, i - last)
                if first is None:
                    first = i
                last = i
        return max(first, len(seats) - last - 1, d // 2)

Complexity

Measure	Complexity
Time	O(n), where n is the length of the array \textit{seats}
Space	O(1) auxiliary

Frequently asked questions

How hard is LeetCode 849. Maximize Distance to Closest Person?: LeetCode 849. Maximize Distance to Closest Person is rated Medium on LeetCode.
What is the time complexity of LeetCode 849. Maximize Distance to Closest Person?: The Python solution on this page runs in O(n), where n is the length of the array \textit{seats}.
What is the space complexity of LeetCode 849. Maximize Distance to Closest Person?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 849. Maximize Distance to Closest Person cover?: LeetCode 849. Maximize Distance to Closest Person is tagged Array on LeetCode.