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 * 104seats[i] is 0 or 1.In this approach, you perform a left-to-right scan to compute the distance to the nearest occupied seat on the left and a right-to-left scan to compute the distance to the nearest occupied seat on the right. For each empty seat, the result will be the minimum of these distances. The final solution is the maximum among these minimum distances.
The C solution uses two arrays to keep track of the minimum distances to the nearest person on the left and right. It initializes two separate passes over the seats array: the first pass computes the distance to the last occupied chair on the left, while the second pass computes the distance to the next occupied chair on the right. Finally, it calculates the maximum of the minimum distances for each seat.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the number of seats. We pass over the list twice.
Space Complexity: O(n) due to the use of additional arrays for storing distances.
This approach involves using a single pass over the seats array while utilizing two pointers. The first pointer stores the last filled seat position, and with each empty seat, the calculation is made based on its distance from the last filled position and the subsequent fill.
In this C solution, a single pass evaluates each seat while dynamically adjusting two pointers (prev for the last occupied position and future for the next occupied position) to compute potential seat distances.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) for a single traversal.
Space Complexity: O(1) since it uses a constant amount of space.
| Approach | Complexity |
|---|---|
| Two-Pass or Left-Right Scan | Time Complexity: O(n) where n is the number of seats. We pass over the list twice. |
| Single-Pass Using Two Pointers | Time Complexity: O(n) for a single traversal. |
maximize distance to closest person leetcode | leetcode 849 | array • Naresh Gupta • 6,174 views views
Watch 9 more video solutions →Practice Maximize Distance to Closest Person with our built-in code editor and test cases.
Practice on FleetCode