As Far from Land as Possible

• Create a list landCells and a list waterCells.
• Iterate through the grid from (0,0) to (n-1, n-1):
  • If grid[i][j] == 1, add (i, j) to landCells.
  • Else, add (i, j) to waterCells.
• If landCells or waterCells is empty, return -1.
• Initialize maxDist = 0.
• For each water cell in waterCells:
  • Initialize minDist = Integer.MAX_VALUE.
  • For each land cell in landCells:
    • Calculate dist = |water.x - land.x| + |water.y - land.y|.
    • Update minDist = min(minDist, dist).
  • Update maxDist = max(maxDist, minDist).
• Return maxDist.

First, we collect the coordinates of all land cells and all water cells into two separate lists. We handle the edge cases where there are no land cells or no water cells, returning -1 as required. We then iterate through each water cell. For each water cell, we initialize its minimum distance to a land cell to infinity. Inside this loop, we have another loop that iterates through all land cells. We calculate the Manhattan distance between the current water cell and the current land cell. We update the minimum distance for the current water cell if the newly calculated distance is smaller. After checking all land cells, we have the shortest distance from the current water cell to any land. We then update our overall maximum distance found so far. After iterating through all water cells, the overall maximum distance is our answer.

1class Solution {2    public int maxDistance(int[][] grid) {3        int n = grid.length;4        java.util.List<int[]> landCells = new java.util.ArrayList<>();5        java.util.List<int[]> waterCells = new java.util.ArrayList<>();6 7        for (int i = 0; i < n; i++) {8            for (int j = 0; j < n; j++) {9                if (grid[i][j] == 1) {10                    landCells.add(new int[]{i, j});11                } else {12                    waterCells.add(new int[]{i, j});13                }14            }15        }16 17        if (landCells.isEmpty() || waterCells.isEmpty()) {18            return -1;19        }20 21        int maxDist = 0;22        for (int[] water : waterCells) {23            int minDist = Integer.MAX_VALUE;24            for (int[] land : landCells) {25                int dist = Math.abs(water[0] - land[0]) + Math.abs(water[1] - land[1]);26                minDist = Math.min(minDist, dist);27            }28            maxDist = Math.max(maxDist, minDist);29        }30 31        return maxDist;32    }33}

• Initialize a queue and add the coordinates of all land cells (1) from the grid.
• Check for edge cases: if the queue is empty (no land) or its size is n*n (all land), return -1.
• Initialize distance = -1.
• While the queue is not empty:
  • Increment distance.
  • Get the number of nodes at the current level, levelSize = queue.size().
  • For i from 0 to levelSize - 1:
    • Dequeue a cell (r, c).
    • For each of its four neighbors (nr, nc):
      • If the neighbor is within bounds and is a water cell (grid[nr][nc] == 0):
        • Mark the neighbor as visited by setting grid[nr][nc] = 1.
        • Enqueue the neighbor (nr, nc).
• Return distance.

This method is known as a Multi-Source BFS. We treat all land cells as the initial sources for our search. First, we iterate through the grid and add the coordinates of all land cells (1s) to a queue. These cells are at distance 0 from the nearest land (themselves). We handle the edge cases: if there are no land cells (queue is empty) or no water cells (all cells are land), we return -1. We then start the BFS process. The search proceeds in levels. In each level, we process all the cells currently in the queue. For each cell we dequeue, we explore its four neighbors (up, down, left, right). If a neighbor is a water cell (0) and has not been visited yet, we mark it as visited (e.g., by changing its value in the grid to 1) and add it to the queue for the next level's processing. The distance is tracked by the levels of the BFS. We start with a distance of -1 and increment it for each level we process. The final distance value after the BFS completes is the maximum distance from any water cell to the nearest land. The BFS guarantees that we find the shortest path from any source. Since we start from all land cells, the distance at which we reach a water cell (r, c) is its shortest distance to any of the land cells. The last cell to be visited is, by definition, the farthest one.

1class Solution {2    public int maxDistance(int[][] grid) {3        int n = grid.length;4        java.util.Queue<int[]> queue = new java.util.LinkedList<>();5        6        // Add all land cells to the queue7        for (int i = 0; i < n; i++) {8            for (int j = 0; j < n; j++) {9                if (grid[i][j] == 1) {10                    queue.offer(new int[]{i, j});11                }12            }13        }14        15        // Edge cases: no land or all land16        if (queue.isEmpty() || queue.size() == n * n) {17            return -1;18        }19        20        int distance = -1;21        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};22        23        while (!queue.isEmpty()) {24            distance++;25            int levelSize = queue.size();26            for (int i = 0; i < levelSize; i++) {27                int[] cell = queue.poll();28                int r = cell[0];29                int c = cell[1];30                31                for (int[] dir : directions) {32                    int newR = r + dir[0];33                    int newC = c + dir[1];34                    35                    if (newR >= 0 && newR < n && newC >= 0 && newC < n && grid[newR][newC] == 0) {36                        grid[newR][newC] = 1; // Mark as visited37                        queue.offer(new int[]{newR, newC});38                    }39                }40            }41        }42        43        return distance;44    }45}