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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

As Far from Land as Possible

Number: 1117

Difficulty: Medium

Paid? No

Companies: Amazon, UiPath

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 Manhattan distance to the nearest land cell is maximized. Return the maximum distance. If the grid contains only water or only land, return -1.

Key Insights

  • Use a multi-source Breadth-First Search (BFS) starting from all the land cells simultaneously.
  • BFS expansion naturally calculates the minimum Manhattan distance from each water cell to the nearest land.
  • Processing cells level-by-level ensures that each water cell is labeled with its shortest distance from any land cell.
  • If either no land or no water exists, return -1 immediately.

Space and Time Complexity

Time Complexity: O(n^2) – Every cell in the grid is visited at most once. Space Complexity: O(n^2) – In the worst-case, the BFS queue may contain a large fraction of the cells.

Solution

To solve the problem, we perform a multi-source BFS starting from every land cell. We initially enqueue all land cell coordinates. Then, using BFS, we expand outwards to visit neighboring water cells. For each water cell encountered, mark the cell with the distance (incremented from the nearest land cell) and add it to the queue. The final maximum distance is determined by the last level of water cell that gets processed. This converts the grid into a distance map, where the value in a water cell minus one gives the Manhattan distance from the nearest land cell.

Code Solutions

from collections import deque

def maxDistance(grid):
    n = len(grid)
    queue = deque()
    
    # Enqueue all land cells.
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                queue.append((i, j))
                
    # Return -1 if grid is all water or all land.
    if not queue or len(queue) == n * n:
        return -1
    
    max_distance = -1
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    # Multi-source BFS.
    while queue:
        i, j = queue.popleft()
        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == 0:
                # Mark the water cell with distance from land.
                grid[ni][nj] = grid[i][j] + 1
                max_distance = max(max_distance, grid[ni][nj] - 1)
                queue.append((ni, nj))
    return max_distance

# Example usage:
print(maxDistance([[1,0,1],[0,0,0],[1,0,1]]))  # Expected output: 2
print(maxDistance([[1,0,0],[0,0,0],[0,0,0]]))  # Expected output: 4
← Back to All Questions