This post is completed by 3 users

  • 1
 Add to List
Medium

515. Maximum distance from the nearest person

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 current. These two pointers will point at two occupied seats, previous to the occupied seat on the left and current 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. 

Steps:

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

Output:

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

Related Problems: