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.
1import java.util.Arrays;
2
3public class MaxDistance {
4 public int maxDistToClosest(int[] seats) {
5 int n = seats.length;
6 int[] left = new int[n], right = new int[n];
7 Arrays.fill(left, n);
8 Arrays.fill(right, n);
9
10 for (int i = 0, last = -1; i < n; ++i) {
11 if (seats[i] == 1) last = i;
12 else if (last != -1) left[i] = i - last;
13 }
14
15 for (int i = n - 1, last = -1; i >= 0; --i) {
16 if (seats[i] == 1) last = i;
17 else if (last != -1) right[i] = last - i;
18 }
19
20 int maxDist = 0;
21 for (int i = 0; i < n; ++i) {
22 if (seats[i] == 0) {
23 maxDist = Math.max(maxDist, Math.min(left[i], right[i]));
24 }
25 }
26
27 return maxDist;
28 }
29
30 public static void main(String[] args) {
31 MaxDistance solution = new MaxDistance();
32 int[] seats = {1, 0, 0, 0, 1, 0, 1};
33 System.out.println(solution.maxDistToClosest(seats));
34 }
35}This Java solution is similar in nature, using two arrays to calculate distances from left and right before determining the maximum distance for Alex's optimal 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
public class Solution {
public int MaxDistToClosest(int[] seats) {
int prev = -1, future = 0, maxDist = 0;
for (int i = 0; i < seats.Length; ++i) {
if (seats[i] == 1) {
prev = i;
} else {
while (future < seats.Length && (seats[future] == 0 || future < i)) {
future++;
}
int leftDist = (prev == -1) ? seats.Length : i - prev;
int rightDist = (future == seats.Length) ? seats.Length : future - i;
int minDist = Math.Min(leftDist, rightDist);
maxDist = Math.Max(maxDist, minDist);
}
}
return maxDist;
}
public static void Main(string[] args) {
int[] seats = { 1, 0, 0, 0, 1, 0, 1 };
Solution sol = new Solution();
Console.WriteLine(sol.MaxDistToClosest(seats));
}
}The C# solution mirrors these techniques within the language's syntax, generally computing distances within a single linear pass.