Sponsored
Sponsored
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.
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.
1#include <vector>
2#include <algorithm>
3#include <iostream>
4
5using namespace std;
6
7class Solution {
8public:
9 int maxDistToClosest(vector<int>& seats) {
10 int n = seats.size();
11 vector<int> left(n, n), right(n, n);
12
13 // Left to right pass
14 for (int i = 0, last = -1; i < n; ++i) {
15 if (seats[i] == 1) last = i;
16 else if (last != -1) left[i] = i - last;
17 }
18
19 // Right to left pass
20 for (int i = n - 1, last = -1; i >= 0; --i) {
21 if (seats[i] == 1) last = i;
22 else if (last != -1) right[i] = last - i;
23 }
24
25 // Calculate max of min distances
26 int maxDist = 0;
27 for (int i = 0; i < n; ++i) {
28 if (seats[i] == 0) {
29 int dist = min(left[i], right[i]);
30 maxDist = max(maxDist, dist);
31 }
32 }
33
34 return maxDist;
35 }
36};
37
38int main() {
39 vector<int> seats = {1, 0, 0, 0, 1, 0, 1};
40 Solution sol;
41 cout << sol.maxDistToClosest(seats) << endl;
42 return 0;
43}The C++ solution implements a similar strategy to the C solution, using vectors to store distances from the left and right sides. It computes the maximum distance by iterating over all the empty seats and taking the minimum of the left and right distances for each seat.
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.
Time Complexity: O(n) for a single traversal.
Space Complexity: O(1) since it uses a constant amount of space.
1
This JavaScript version performs the task in a straightforward, efficient approach using minimal state management.