As Far from Land as Possible

BFS

Problem

Given an n x n grid containing only values 0 and 1, where 0represents 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|.

Thought Process

• Question is similar to Rotting Oranges with keeping track of what level we're on

• The farthest 0 (water) is just the deepest level count

Solution

from collections import deque

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        
        hasWater, hasLand = False, False
        q = deque()
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    hasLand = True
                    q.append([i,j])
                elif grid[i][j] == 0:
                    hasWater = True        
                    
        if not hasWater or not hasLand:
            return -1
        
        directions = [[-1,0], [1,0], [0,-1], [0,1]]
        level = 0
        while q:
            levelSize = len(q)
            level+=1
            for _ in range(levelSize):
                coor = q.popleft()
                x, y = coor[0], coor[1]
                for d in directions:
                    newX = x+d[0]
                    newY = y+d[1]
                    
                    if newX < 0 or newX >= len(grid) or newY < 0 or newY >= len(grid[0]):
                        continue
                        
                    if grid[newX][newY] == 0:
                        grid[newX][newY] = 1
                        q.append([newX, newY])
            
                        
        return level-1
    

Time Complexity

• Time: O(n*n) since we're going through the matrix

• Space: O(n*n) because our queue will hold every cell