We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

As Far from Land as Possible

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires maximizing the distance from water cells to the nearest land cells.
  • Manhattan distance is used to measure the distance between two cells.
  • A breadth-first search (BFS) approach is suitable for this problem as it can explore all possible cells uniformly.
  • The solution leverages multiple starting points (land cells) to explore distances to water cells.

Space and Time Complexity

Time Complexity: O(n^2) - We traverse each cell in the grid. Space Complexity: O(n^2) - In the worst case, we might need to store all the water cells in the queue.

Solution

To solve this problem, we can use a breadth-first search (BFS) approach. We start by identifying all the land cells (1s) and enqueue them as our initial points. Then, we perform BFS from these land cells to explore the distances to the water cells (0s). Each time we reach a water cell, we calculate the distance from the nearest land cell and keep track of the maximum distance found. The BFS ensures that we explore the closest cells first, allowing us to maximize the distance to water cells efficiently.

Code Solutions

from collections import deque

def maxDistance(grid):
    n = len(grid)
    queue = deque()
    
    # Add all land cells to the queue
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                queue.append((i, j))
    
    # If there are no land or no water cells
    if len(queue) == 0 or len(queue) == n * n:
        return -1
    
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    max_distance = -1
    
    # BFS to find the maximum distance to land
    while queue:
        for _ in range(len(queue)):
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0:
                    grid[nx][ny] = grid[x][y] + 1  # Mark the distance
                    max_distance = max(max_distance, grid[nx][ny] - 1)
                    queue.append((nx, ny))
    
    return max_distance
← Back to All Questions