Scale Engineer

As Far from Land as Possible

Med
#1091Time: O(N^4), where N is the side length of the grid. Let L be the number of land cells and W be the number of water cells. The complexity is O(L * W). In the worst case, L and W can both be on the order of O(N^2), leading to an overall complexity of O(N^4). This is too slow for the given constraints.Space: O(N^2), to store the coordinates of all land and water cells.2 companies
Patterns
Dynamic Programming
Algorithms
Breadth-First Search
Data structures
ArrayMatrix
Companies
WixUiPath

Prompt

Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

 

Example 1:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: grid = [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: The cell (2, 2) is as far as possible from all the land with distance 4.

 

Constraints:

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 100
  • grid[i][j] is 0 or 1

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through every water cell in the grid. For each water cell, it then calculates the Manhattan distance to every land cell to find the nearest one. The maximum of these nearest distances is the result.

Algorithm

  • 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.

Walkthrough

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.

class Solution {    public int maxDistance(int[][] grid) {        int n = grid.length;        java.util.List<int[]> landCells = new java.util.ArrayList<>();        java.util.List<int[]> waterCells = new java.util.ArrayList<>();         for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                if (grid[i][j] == 1) {                    landCells.add(new int[]{i, j});                } else {                    waterCells.add(new int[]{i, j});                }            }        }         if (landCells.isEmpty() || waterCells.isEmpty()) {            return -1;        }         int maxDist = 0;        for (int[] water : waterCells) {            int minDist = Integer.MAX_VALUE;            for (int[] land : landCells) {                int dist = Math.abs(water[0] - land[0]) + Math.abs(water[1] - land[1]);                minDist = Math.min(minDist, dist);            }            maxDist = Math.max(maxDist, minDist);        }         return maxDist;    }}

Complexity

Time

O(N^4), where N is the side length of the grid. Let L be the number of land cells and W be the number of water cells. The complexity is O(L * W). In the worst case, L and W can both be on the order of O(N^2), leading to an overall complexity of O(N^4). This is too slow for the given constraints.

Space

O(N^2), to store the coordinates of all land and water cells.

Trade-offs

Pros

  • Conceptually simple and easy to follow.

Cons

  • Extremely inefficient, leading to a 'Time Limit Exceeded' error on larger grids.

Solutions

class Solution {public  int maxDistance(int[][] grid) {    int n = grid.length;    Deque<int[]> q = new ArrayDeque<>();    for (int i = 0; i < n; ++i) {      for (int j = 0; j < n; ++j) {        if (grid[i][j] == 1) {          q.offer(new int[]{i, j});        }      }    }    int ans = -1;    if (q.isEmpty() || q.size() == n * n) {      return ans;    }    int[] dirs = {-1, 0, 1, 0, -1};    while (!q.isEmpty()) {      for (int i = q.size(); i > 0; --i) {        int[] p = q.poll();        for (int k = 0; k < 4; ++k) {          int x = p[0] + dirs[k], y = p[1] + dirs[k + 1];          if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 0) {            grid[x][y] = 1;            q.offer(new int[]{x, y});          }        }      }      ++ans;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem