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.
Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized. 
Return that maximum distance to the closest person.
 
Example 1:

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.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

Example 2:
Input: seats = [1,0,0,0]
Output: 3
Explanation: 
If Alex sits in the last seat (i.e. seats[3]), the closest person is 3 seats away.
This is the maximum distance possible, so the answer is 3.

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

 
Constraints:

2 <= seats.length <= 2 * 104
seats[i] is 0 or 1.
At least one seat is empty.
At least one seat is occupied.

Difficulty: interview

Starter code:

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        

Solutions:
class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        ans = 0 
        for seat, group in itertools.groupby(seats):
            if not seat:
                k = len(list(group))
                ans = max(ans, (k+1)//2)
        return max(ans, seats.index(1),seats[::-1].index(1))
        


class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        
        
#         runzero, maxzero = 0,0
        
#         for i, seat in enumerate(seats):
            
#             if seat==0:
#                 runzero += 1
#                 maxzero = max(maxzero, runzero)
#             else:
#                 runzero=0
                
#         ans = (maxzero+1)//2
#         startmax = seats.index(1)
#         endmax = seats[::-1].index(1)
#         return max(ans, startmax, endmax)

        anspointer = -float('inf')
        prvpointer = None
        
        for i, seat in enumerate(seats):
            
            if seat==1:
                if prvpointer == None:
                    anspointer = i
                    # prvpointer = i
                else:
                    anspointer = max(anspointer, (i-prvpointer)//2)
                
                prvpointer = i
        
        anspointer = max(anspointer, len(seats)-1-prvpointer)
        
        return anspointer

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        n = len(seats)
        left, right = [-1]*n, [-1]*n
        leftMost, rightMost = float('-inf'), float('inf')
        for i in range(n):
            if seats[i] == 1:   leftMost = i
            left[i] = leftMost
            if seats[n-1-i] == 1:   rightMost = n-1-i
            right[n-1-i] = rightMost
        print()
        maxDistance = 0
        for i in range(n):
            if seats[i] == 1:   continue
            distance = min(i-left[i], right[i]-i)
            maxDistance = max(maxDistance, distance)
        
        return maxDistance

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        lToR = [0 for _ in range(len(seats))]
        rToL = [0 for _ in range(len(seats))]
        for i in range(len(seats)):
            if seats[i] == 1:
                lToR[i] = -1 
                continue
            if i == 0:
                if seats[i] == 0:
                    lToR[i] = 1
            else:
                if seats[i-1] != 1:
                    lToR[i] = lToR[i-1]+1
                else:
                    lToR[i] = 1
        for i in range(len(seats)-1, -1, -1):
            if seats[i] == 1:
                rToL[i] = -1 
                continue
            if i == len(seats)-1:
                if seats[i] == 0:
                    rToL[i] = 1
            else:
                if seats[i+1] != 1:
                    rToL[i] = rToL[i+1]+1
                else:
                    rToL[i] = 1
        res = 1
        for i in range(len(seats)):
            if i == 0 or i == len(seats)-1:
                if lToR[i] != -1 and rToL[i] != -1:
                    res = max(res,max(lToR[i],rToL[i]))
            else:
                if lToR[i] != -1 and rToL[i] != -1:
                    res = max(res,min(lToR[i],rToL[i]))
        return res
'''
class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        if not seats: return 0
        res = 0
        que = deque()
        que.append(-1)
        for index, seat in enumerate(seats):
            if seat == 1: que.append(index)
            if len(que) == 2:
                if que[0] == -1:
                    res = max(res, que[1])
                else:
                    res = max(res, (que[1]-que[0])//2)
                que.popleft()
        res = max(res, len(seats)-1-que[0])
        return res
'''
                    
        
'''
class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        res = 0
        que = deque()
        que.append(-1)
        #start, end = 0, 0
        
        for index, seat in enumerate(seats):
            if seat == 1: que.append(index)
            if len(que) == 2:
                if que[0] == -1:
                    res = max(res, que[1])
                else:
                    res = max(res, (que[1]-que[0])//2)
                que.popleft()
                    
        res = max(res, len(seats)-1-que[0])
        return res
'''
        
 
                
        
        
                
                
            
                    
       
  
            


class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        
        N = len(seats)
        
        left = [0 for _ in range(N)]
        right = [0 for _ in range(N)]
        
        for i in range(N):
 
            if seats[i]==1:
                left[i]=i
                continue
            
            if i==0:
                left[i]=-1
                continue
            
                
            left[i] = left[i-1]
            
        for i in range(N-1,-1,-1):
        
            if seats[i]==1:
                right[i]=i
                continue
            
            if i==(N-1):
                right[i]=-1
                continue
                
            right[i]=right[i+1]
        
        print((right,left))
        maxDistance = 0
        
        for pos in range(N):
            
            if seats[pos]==0:
                if left[pos]==-1 or right[pos]==-1:
                    if left[pos]==-1:
                        distance = right[pos]-pos
                    else:
                        distance = pos-left[pos]
                else:
                    distance = min(right[pos]-pos,pos-left[pos])
                
                maxDistance = max(maxDistance,distance)
                
        return maxDistance
                        
                
                


class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        seated = [i for i, elem in enumerate(seats) if elem == 1]
        empties = [i for i, elem in enumerate(seats) if elem == 0]
        
        s_p, e_p = 0, 0
        min_dist = 0
        while e_p < len(empties):
            # make the determination:
            while (s_p < len(seated) - 1) and empties[e_p] > seated[s_p]:
                s_p += 1
            if s_p > 0:
                tmp_dist = min(abs(empties[e_p] - seated[s_p - 1]), 
                               abs(empties[e_p] - seated[s_p]))
            else:
                tmp_dist = abs(empties[e_p] - seated[s_p])
            if tmp_dist > min_dist:
                min_dist = tmp_dist
            e_p += 1
        return min_dist

class Solution:
    def maxDistToClosest(self, seats) -> int:
        self.dists = [0 for i in range(len(seats))]
        i = 0
        # loop thru seats, assign weights as they come. update i to next seat found
        while i < len(seats)-1:
            i = self.assign_weights(i,seats)
        # print(self.dists)
        return max(self.dists)
    # from left seat, search for next seat and assign weights
    def assign_weights(self,start, seats):
        if start == 0 and seats[start] != 1:
            l_seat = math.inf
        else:
            l_seat = start
        temp = start + 1
        while temp < len(seats) and seats[temp] != 1:
            temp+=1
        
        if temp == len(seats):
            r_seat = math.inf
        else:
            r_seat = temp

        for i in range(start,min(len(seats),r_seat)):
            l_dist = abs(l_seat-i)
            r_dist = r_seat - i 
            self.dists[i] = min(l_dist,r_dist)

        return r_seat


class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        if len(seats) == 0 or min(seats) == 1:
            return 0
        
        
        left = [len(seats)] * len(seats)
        right = [len(seats)] * len(seats)
        latest = -1
        for i in range(len(seats)):
            if seats[i] == 1:
                latest = i
            if latest >= 0:
                left[i] = i - latest
            
        latest = len(seats)
        for i in reversed(range(len(seats))):
            if seats[i] == 1:
                latest = i
            if latest < len(seats):
                right[i] = latest - i
            
        ans = 0
        for i in range(len(seats)):
            ans = max(ans, min(left[i], right[i]))
            
        print(left, right)
            
        return ans

from collections import defaultdict
class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        N=len(seats)
        front=defaultdict(int)
        hind=defaultdict(int)
            
        frontI=float('-inf')
        hindI=float('inf')
        for n in range(N):
            if seats[n]==1:
                frontI=n
            front[n]=frontI
        for n in range(N)[::-1]:
            if seats[n]==1:
                 hindI=n
            hind[n]=hindI
        res=0  

        for n in range(N):
            if seats[n]==0:
                res=max(res, min(n-front[n],hind[n]-n))
        return res
                
            
            
            
        
        

        
        


class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        prev_s = [None for _ in seats]
        next_s = [None for _ in seats]
        last_1 = -float('INF')
        next_1 = float('INF')
        for i in range(len(seats)):
            if seats[i] == 1:
                last_1 = i
            else:
                prev_s[i] = last_1
        
        for i in range(len(seats) - 1, -1, -1):
            if seats[i] == 1:
                next_1 = i
            else:
                next_s[i] = next_1
        
        print(prev_s, next_s)
        closest_max = -1
        for i in range(len(seats)):
            if prev_s[i] != None and next_s[i] != None:
                print(prev_s[i], next_s[i])
                closest_max = max(closest_max, min(i - prev_s[i], next_s[i] - i))
        return closest_max

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        # Goal is to maximize 0's on each side of i
        # so first option that immediatly comes to mind is to run through the list
        # checking every positon, and then its distance, saving the seat with the maximized distance
        # This is really slow
        # to speed it up, i can only check seats that are farther from most recent seat than best yet
        # so in the first example
        
        # [1,0,0,0,1,0,1]
        # 0 continue
        # 1, check its 1 away, save its values
        # 2 check its two away, save its values
        # 3 its 3 away check its values, do not save
        # 4 continue
        # 5 1 is most recent continue
        # 6 conitnue
        
        # still n^2 but faster than checking EVERY possibiliy
        
        # Go through once, saving the position of every person initially.
        
        # So here we just have to loop through and find the max difference between. Then return the mid value
        # This algorithm is much faster
        
        # Edge case of best seat being on far right and far left
        # first find distance of first person from beginning, then afyer 
        
        # 0, 4, 6
        # best = people[0]
        # pos = 0
        # distance = (people[i] - people[i-1])//2
        # if distance > best:
        #   best = distance
        #   
        # [0, 0, 1]
        prev = -1
        best = 0
        for i in range(0, len(seats)):
            if seats[i] == 1:
                if prev == -1:
                    distance = i
                else:
                    distance = (i - prev)//2
                best = max(best, distance)
                prev = i
        best = max(best, len(seats) - prev-1)
        
#         best = people[0]
        
#         for i in range(1, len(people)):
#             distance = (people[i] - people[i-1])//2
#             best = max(best, distance)
        
#         best = max(best, len(seats) - people[-1]-1)
        return best
            


class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        
        s = seats
        
        first = 0 
        second = 0
        second_index = 0
        output = []
        Set = False
        count = 0 
        
        for i in range(len(s)):
            if s[i] != 1:
                if(Set ==  False):
                    count = count + 1
                
                continue
            else:
                Set = True
                for j in range(i+1 , len(s)):
                    if(s[j] != 1):
                        second_index = j
                        continue
                    else:
                        second_index = j
                        print((second_index , i ))
                        break
                        
                diff = second_index - i 
                
                if( second_index == len(s) - 1 and s[second_index] == 0):
                    output.append(diff)
                    
                output.append(count)
                    
                
                
                if(diff %2 == 0 ):
                    output.append(int(diff/2))
                else:
                    output.append(int(diff/2))
                        
        return max(output)
                        


class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        count0, mmax, dist, start = 0, 0, 0, True
        for i, e in enumerate(seats):
            if e == 0:
                count0 += 1
                if i == len(seats)-1:
                    dist = count0
            else:
                if count0 > 0:
                    if start:
                        dist = count0
                    else:
                        dist = (count0+1)//2
                count0 = 0
                start = False
            mmax = max(dist, mmax)
        return mmax

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        
        max_distance = 0
        for i, seat in enumerate(seats):
            if seat == 1:
                pass
            
            else:
                left = right = i
                location = [0, 0]
                while 0 <= left < len(seats):
                    if seats[left] != 1:
                        location[0] += 1
                        left -= 1
                    else:
                        break
                        
                
                while 0 <= right < len(seats):
                    if seats[right] != 1:
                        location[1] += 1
                        right += 1
                    else:
                        break
                        
                if i == 0 or i == len(seats) - 1:
                    distance = max(location[0], location[1])
                else:
                    distance = min(location[0], location[1])
                        
                if distance > max_distance:
                    max_distance = distance
                        
                
                
                
        print(max_distance)
        return max_distance
                    


class Solution:
    # Time: O(len(seats))
    # Space: O(1)
    def maxDistToClosest(self, seats: List[int]) -> int:
        # two pointers
        s = -1
        distMax = 0
        
        while s < len(seats) - 1:
            print('s: ', s)
            for e in range(s+1, len(seats)):
                print('e: ', e)
                if seats[e] == 1:
                    if s == -1:
                        distMax = max(distMax, e)
                    else:
                        distMax = max(distMax, (e-s)//2)
                    s = e
                    break
                elif e == len(seats)-1:
                    distMax = max(distMax, len(seats)-1-s)
                    s = e
                    
        return distMax

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        '''
        need to find the distance of the closest neighbor at each seat
        need to find distance to left and right neighbor at each seat 
        get the min of the two
        '''
        n = len(seats)
        distance = [-1] * n
        # calc distance to left neighbor
        left_neighbor = -float('inf')
        for seat in range(n):
            if seats[seat] == 1:
                left_neighbor = seat
            distance[seat] = seat - left_neighbor
        print(distance)
        # calc distance to right neighbor
        right_neighbor = float('inf')
        answer = 0
        for seat in range(n-1,-1,-1):
            if seats[seat] == 1:
                right_neighbor = seat
            distance[seat] = min(distance[seat], right_neighbor - seat)
            # if distance[seat] > distance[answer]:
            #     answer = seat
        print(distance)
        return max(distance)


class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        '''
        [1,0,0,0,1,0,1]
        
        left = [0,0,0,0,4,4,6]
        right [0,4,4,4,4,6,6]
        
        '''
        
        
        n = len(seats)
        left, right = [n] * len(seats), [n] * len(seats)
            
        for i in range(0, len(seats)):
            if seats[i] == 1:
                left[i] = 0 
            elif i > 0 and seats[i] == 0:
                left[i] =  left[i-1] + 1 
            
        for i in range(len(seats)-1, -1, -1):
            if seats[i] == 1:
                right[i] = 0 
            elif i < len(seats) - 1 and seats[i] == 0:
                right[i] = right[i+1] + 1 

        maxDistance = float('-inf')
        for i, seat in enumerate(seats):
            if seat == 0:
                maxDistance = max(maxDistance, min(left[i], right[i]))
        return maxDistance

class Solution:
    def maxDistToClosest(self, arr):
        n = len(arr)
        start = 0 # start index of group of consecutive 0s
        end = 0 # end index of group of consecutive 0s
        
        maxdist, dist = 0, 0

        i = 0
        while (i < n):

            while (i < n and arr[i] == 1):
                i += 1
            start = i

            while (i < n and arr[i] == 0):
                i += 1
            end = i - 1

            if(start==0):
                dist = end+1
            elif(end==n-1):
                dist = n-1 - start + 1
            else:
                dist = (end-start)//2 + 1
            maxdist=max(maxdist,dist)

        return maxdist

'''
[inf,0]
[1,0]
'''

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        index=float('inf')
        left=[]
        for i in range(len(seats)):
            val=seats[i]
            if val==1:
                index=i
                left.append(0)
            elif index==float('inf'):
                left.append(float('inf'))
            else:
                left.append(abs(i-index))
        index=float('inf')
        for i in range(len(seats)-1,-1,-1):
            val=seats[i]
            if val==1:
                index=i
                seats[i]=0
            elif index==float('inf'):
                seats[i]=float('inf')
            else:
                seats[i]=abs(i-index)
        out=float('-inf')
        for i in range(len(seats)):
            temp=min(left[i],seats[i])
            out=max(out,temp)
        return out
        


class Solution:
    def maxDistToClosest(self, seats) -> int:
        max_len = 0
        _cnt = 0
        for v in seats:
            if v == 0:
                _cnt += 1
            if v == 1:
                max_len = max(max_len, _cnt)
                _cnt = 0
        max_dist = (max_len+1) // 2
        return max(max_dist, seats.index(1), seats[::-1].index(1))

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

from bisect import bisect

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        occupied_indexes = []
        empty_indexes = []
        for i, is_occupied in enumerate(seats):
            if is_occupied:
                occupied_indexes.append(i)
            else:
                empty_indexes.append(i)
                
        num_occupied = len(occupied_indexes)
        max_distance = 1
        coi = 0
        for empty_index in empty_indexes:
            
            while coi < num_occupied and occupied_indexes[coi] < empty_index:
                coi += 1
            ridx = coi
            lidx = ridx - 1
            
            lmd = rmd = float('inf')
            if lidx >= 0:
                lmd = empty_index - occupied_indexes[lidx]
            if ridx < num_occupied:
                rmd = occupied_indexes[ridx] - empty_index
            max_distance = max(max_distance, min(lmd, rmd))
        return max_distance
                


class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        left = []
        right = []
        n = len(seats)
        leftlast = None
        rightlast = None
        for i in range(n):
            if seats[i] == 1:
                left.append(0)
                leftlast = i
            else:
                if leftlast is None:
                    left.append(float('inf'))
                else:
                    left.append(i - leftlast)
            if seats[n-i-1] == 1:
                right.append(0)
                rightlast = n-i-1
            else:
                if rightlast is None:
                    right.append(float('inf'))
                else:
                    right.append(rightlast - n + i + 1)
                
        res = 0
        for i in range(n):
            res = max(res, min(right[n-i-1], left[i]))
        return res
                
            
            


class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        res, last, n = 0, -1, len(seats)
        for i in range(n):
            if seats[i]:
                res = max(res, i if last < 0 else (i - last) // 2)
                last = i
        return int(max(res, n - last - 1))

class Solution:
    
    def maxDistToClosest(self, seats: List[int]) -> int:
        seat_max_space = 0
        max_dis = 0
        for i, s in enumerate(seats):
            if s == 0:
                # print(\"DRR\", i, s)
                j = i -1
                #search left
                min_left = j
                left_seat_found = False
                while j >= 0:
                    if seats[j] == 1:
                        min_left = j
                        left_seat_found = True
                        break
                    j -= 1
                k = i
                min_right = k +1
                right_seat_found = False
                while k < len(seats):
                    if seats[k] == 1:
                        min_right = k
                        right_seat_found = True
                        break
                    k += 1
                if right_seat_found is False and left_seat_found is False:
                    return len(seats) -1
                if right_seat_found is False:
                    min_right = min_left
                if left_seat_found is False:
                    min_left = min_right
                closer = abs(min(i - min_left, min_right -i))
                # print(i, min_left ,min_right , closer )
                seat_max_space = max(seat_max_space, closer)
        print(seat_max_space)
        return seat_max_space


class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        '''res=0
        for i in range(len(seats)):
            if seats[i]==1:
                continue
            if sum(seats[:i])==0:
                left=0
            else:
                left=i-1
                while seats[left]!=1:
                    left-=1
            if sum(seats[i+1:])==0:
                right=len(seats)-1
            else:
                right=i+1                
                while seats[right]!=1:
                    right+=1
            if i-left!=0 and right-i!=0:
                res=max(res,min(i-left,right-i))
            if i-left==0:
                res=max(res,right-i)
            if right-i==0:
                res=max(res,i-left)
                    
        return(res)'''
        people = (i for i, seat in enumerate(seats) if seat)
        prev, future = None, next(people)

        ans = 0
        for i, seat in enumerate(seats):
            if seat:
                prev = i
            else:
                while future is not None and future < i:
                    future = next(people, None)

                left = float('inf') if prev is None else i - prev
                right = float('inf') if future is None else future - i
                ans = max(ans, min(left, right))

        return ans


class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        left, right = -1, 0
        result = 0
        
        for right in range(len(seats)):
            if seats[right] == 0:
                continue
                
            if seats[right] == 1:               
                if left == -1:
                    result = right
                else:
                    result = max((right - left)//2, result)
                left = right
        
        if not seats[right]:
            result = max(result, right - left)
        
        return result
            
                    
            
            
            
            


class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        
        s, max_dist = -1, 0
        n = len(seats)
        
        for e in range(n):
            if not seats[e]: continue 
                
            if s == -1:
                max_dist = max(max_dist, e)
            else:
                max_dist = max(max_dist, floor((e-s)/2))

            s = e
            
        if seats[n-1] == 0:
            max_dist = max(max_dist, n-1-s)
            
        return max_dist     


class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        c = 0
        ans = 0 
        for i in range(len(seats)):
            if seats[i]:
                if ans == 0 and c > 0 and c == i:
                    ans = c
                elif (c+1)//2 > ans:
                    ans = (c+1)//2
                c = 0
            else:
                c += 1
        ans = max(c, ans)
        return ans
                


class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        l_0 = 0
        begin_end_0 = -1
        curr = 0
        n = len(seats)
        for i, num in enumerate(seats):
            if num==0:
                curr += 1
                l_0 = max(curr, l_0)
            else:
                curr = 0
            if i == n-1 or i - curr + 1 == 0:
                begin_end_0 = max(begin_end_0,curr)
        return max(begin_end_0, (l_0-1)//2+1)


class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        n = len(seats)
        dips = [0 for _ in range(n)]
        dist = n
        for i in range(n):
            if seats[i] == 1:
                dist = 0
            else:
                dips[i] = dist
            dist += 1
        print(dist, dips)
        dist = n
        
        minimum = 0
        for i in range(n-1, -1, -1):
            if seats[i] == 1:
                dist = 0
            else:
                if dips[i] > dist:
                    dips[i] = dist
                if dips[i] > minimum:
                    minimum = max(minimum, dips[i])
            dist += 1   
        return minimum