25. As Far from Land as Possible

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.

Solution: (Brute Force)

Approach: Finding the nearest land to each water cell Finding the maximum of all nearest distance

class Solution
{
public:
    int dfs(vector<vector<int>> &grid, int x, int y)
    {
        int near = INT_MAX;
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                if (grid[i][j] == 1)
                {
                    int dist = abs(x - i) + abs(y - j);
                    near = min(near, dist);
                }
            }
        }
        return near;
    }
    
    int maxDistance(vector<vector<int>> &grid)
    {
        int res = INT_MIN;
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                if (grid[i][j] == 0)
                {
                    int dist = dfs(grid, i, j);
                    res = max(res, dist);
                }
            }
        }
        if(res == INT_MAX || res == INT_MIN){
            return -1;
        }
        return res;
    }
};

Time Complexity: O(n^2 * n^2)

Solution: (BFS)

Approach: Starting BFS from land cell and increasing distance

image

class Solution
{
public:
    void bfs(vector<vector<int>> &grid, queue<pair<int, int>> &q)
    {
        vector<int> dir{0, 1, 0, -1, 0};
        int n = grid.size();

        while (!q.empty())
        {
            int i = q.front().first;
            int j = q.front().second;
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = i + dir[k];
                int y = j + dir[k + 1];
                if (x >= 0 && y >= 0 && x < n && y < n && grid[x][y] == 0)
                {
                    grid[x][y] = grid[i][j] + 1;
                    q.push({x, y});
                }
            }
        }
        return;
    }
    
    int maxDistance(vector<vector<int>> &grid)
    {

        queue<pair<int, int>> q;
        int n = grid.size();
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                if (grid[i][j] == 1)
                {
                    q.push({i, j});
                }
            }
        }

        if (q.size() == 0 || q.size() == n * n)
        {
            return -1;
        }

        bfs(grid, q);

        int res = INT_MIN;
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                if (grid[i][j] > res)
                {
                    res = grid[i][j];
                }
            }
        }

        return res-1;
    }
};

Runtime: O(n * n). We process an individual cell only once (or twice). Memory: O(n) for the queue.