849. Maximize Distance to Closest Person - Detailed Explanation

Problem Statement

You are given an array of integers, seats, where:

• seats[i] = 1 indicates that the i-th seat is occupied.
• seats[i] = 0 indicates that the i-th seat is empty.

You want to choose an empty seat such that the distance to the closest person is maximized. Return the maximum distance to the closest person you can achieve by choosing an optimal seat.

Example 1

• Input: [1,0,0,0,1,0,1]
• Output: 2
• Explanation:
  The best place to sit is at index 2 (or index 3). If you choose index 2, the closest occupied seats are at index 0 and index 4. The distances are 2 and 2 respectively, so the minimum distance is 2.

Example 2

• Input: [1,0,0,0]
• Output: 3
• Explanation:
  The row starts with an occupied seat at index 0 and then three empty seats. Sitting at the last seat (index 3) gives a distance of 3 from the occupied seat at index 0.

Example 3

• Input: [0,1]
• Output: 1
• Explanation:
  The only empty seat is at index 0, and the nearest person is at index 1, so the maximum distance is 1.

Constraints

• 2 <= seats.length <= 20,000
• seats[i] is either 0 or 1.
• There is at least one empty seat and at least one occupied seat.

Hints to Guide Your Approach

1. Consider the Gaps:
   Look at the segments (or gaps) of consecutive empty seats. The maximum distance you can achieve is determined by:

   • The gap at the beginning of the array (if the row starts with empty seats).
   • The gap at the end of the array (if the row ends with empty seats).
   • The gaps in between two occupied seats (for which you’d want to sit in the middle).

2. One-Pass Strategy:
   As you iterate through the array, track the index of the last occupied seat. Use this information to compute the distance for the gap between the current occupied seat and the previous one. Don’t forget to check the gap at the very end of the row after your iteration.

Approaches to Solve the Problem

Approach 1: Brute Force

Explanation

• Idea:
  For each empty seat, determine the distance to the closest occupied seat by scanning to the left and right.

• Steps:

  1. For every seat that is empty (0), scan leftward until you find an occupied seat.
  2. Similarly, scan rightward until you find an occupied seat.
  3. The effective distance for that seat is the minimum of the two distances.
  4. Track the maximum among all empty seats.

• Complexity Analysis:

  • Time Complexity: O(n²) in the worst-case scenario (if many seats are empty).
  • Space Complexity: O(1)

• Pitfalls:
  This approach might be too slow when the number of seats is large (up to 20,000).

Approach 2: One-Pass Optimal Approach

Explanation

• Idea:
  Instead of scanning from each empty seat, use a single pass through the array to calculate the maximum gap.

• Steps:

  1. Initialize:
     • Set a pointer prev to track the index of the last occupied seat (start with prev = -1).
     • Initialize max_distance to 0.
  2. Iterate through the array:
     • When you encounter an occupied seat:
       • Left Gap: If prev == -1, it means this is the first occupied seat. The maximum distance for seats before it is the index value (i.e., i).
       • Middle Gap: Otherwise, the maximum distance you can get in the gap between prev and the current occupied seat is half of the gap: (i - prev) // 2.
     • Update prev to the current index.
  3. Right Gap:
     • After the loop, check the gap from the last occupied seat to the end of the array ((n - 1 - prev)), and update max_distance accordingly.

• Complexity Analysis:

  • Time Complexity: O(n) – a single pass through the array.
  • Space Complexity: O(1)

Visual Example

Consider the array: [1,0,0,0,1,0,1]

• Step 1:
  prev = -1, max_distance = 0

• Iteration:

  • At index 0: seats[0] = 1

    • Since prev = -1, update max_distance = 0 (distance from the start is 0).
    • Set prev = 0.

  • At indices 1, 2, 3: seats[1,2,3] = 0 (skip them until the next occupied seat).

  • At index 4: seats[4] = 1

    • Calculate gap: i - prev = 4 - 0 = 4
    • Distance if sitting in the middle: 4 // 2 = 2
    • Update max_distance = max(0, 2) = 2
    • Set prev = 4.

  • At index 5: seats[5] = 0 (skip).

  • At index 6: seats[6] = 1

    • Calculate gap: 6 - 4 = 2
    • Distance in the middle: 2 // 2 = 1
    • max_distance remains 2.
    • Set prev = 6.

• After the Loop:
  Check gap from index 6 to end: n - 1 - prev = 6 - 6 = 0.
  So, the final answer is 2.

Code Implementations

Python Code

Below is the Python implementation using the optimal one-pass approach. A brute force version can be implemented similarly, but it is not efficient for larger inputs.