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.

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

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:
		anspointer = -float('inf')
		prvpointer = None
		for (i, seat) in enumerate(seats):
			if seat == 1:
				if prvpointer == None:
					anspointer = 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
			elif 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
			elif 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]))
			elif 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:
		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):
			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
		while i < len(seats) - 1:
			i = self.assign_weights(i, seats)
		return max(self.dists)

	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:
		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)
		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:

	def maxDistToClosest(self, seats: List[int]) -> int:
		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:
		n = len(seats)
		distance = [-1] * n
		left_neighbor = -float('inf')
		for seat in range(n):
			if seats[seat] == 1:
				left_neighbor = seat
			distance[seat] = seat - left_neighbor
		print(distance)
		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)
		print(distance)
		return max(distance)


class Solution:

	def maxDistToClosest(self, seats: List[int]) -> int:
		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
		end = 0
		(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


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
			elif 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
			elif 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:
		seat_max_space = 0
		max_dis = 0
		for (i, s) in enumerate(seats):
			if s == 0:
				j = i - 1
				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))
				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:
		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