Given a bench with n seats and few people sitting, You are going to sit on a vacant seat such that the distance between you and the nearest person to you is maximum. On the beach, the occupied seats are represented by 1 and vacant seats are represented by 0.

**Example:**

Input: [1, 0, 1, 0] Output: 1 Input: [1, 0, 0, 0, 1] Output: 2 (You take the seat at index 2) Input: [1, 0, 0, 1, 0, 0, 0] Output: 3 (You take the last seat)

**Approach:**

Idea is that a vacant seat will be at the maximum distance which is at the middle of two occupied seats. So we will use two pointers, ** previous** and

**. These two pointers will point at two occupied seats,**

*current***to the occupied seat on the left and**

*previous***will point to the occupied seat at the right. There are two other cases we need to handle, if these are vacant seats at beginning or at the end of the bench.**

*current***Steps:**

- Initialize
= -1, maxDistance = 0.*previous* - Iterate the beach from left to right, for
seat-*current*- If the
seat is empty, go to the next seat.*current* - If the
seat is not empty*current*- If
= -1, means this is the first occupied seat you have encountered. Do maxDistance =*previous*(no of vacant seats on the left).*current* - If
!=-1 then we have found two occupied seats, get the middle seats between*previous*and*previous*and update the maxDistance if needed.*current* - Do
=*previous*.*current*

- If

- If the
- Once iteration is completed, check if the last seat is vacant then get the distance from the last occupied seat to the last seat and update the maxDistance with this if needed.

**Complete Code:**

**Output:**

Given Bench:[1, 0, 0, 1, 0, 0, 0, 1, 0] Maximum distance for nearest person: 2