https://leetcode.com/problems/maximize-distance-to-closest-person

What we need to do in this problem is to find the person with maximum distance to closest person. Imagine, that we have something like: 000100000111000100001000000. Then we need to look at groups of zeroes we have and:

  1. For the very left and for the very right groups fo zeroes we need to evaluate size of this groups: for example here we have 3 zeroes for the left group and 6 zeroes for the right group.
  2. For the groups of zeroes in the middle, the distance to closest person is (k + 1)//2, where k is number of zeroes in this group. For example for group of 5 zeroes we have 1000001, and the optimal way is to put person in the middle: 1001001. If we have 4 zeroes: 100001, we can put person in one of the two places in the middle: 101001 or 100101.

What we need to do now is just use python groupby function and for each group evaluate the optimal position.

Complexity: Time complexity is O(n) to use groupby, which iterate over our data. Space complexity is also `O(n).

class Solution:
    def maxDistToClosest(self, seats):
        out = max(seats[::-1].index(1), seats.index(1))
        for seat, group in groupby(seats):
            if seat: continue
            out = max(out, (len(list(group))+1)//2)

        return out

If you like the solution, you can upvote it on leetcode discussion section: Problem 0849