As Far from Land as Possible - Practice Coding Problems

As Far from Land as Possible - Problem

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

Input & Output

Example 1 — Basic Grid

$ Input: grid = [[1,0,1],[0,0,0],[1,0,1]]

› Output: 2

💡 Note: The center cell (1,1) is farthest from land. Distance to nearest land at (0,1) is |1-0|+|1-1| = 1+0 = 1, to (1,0) is |1-1|+|1-0| = 0+1 = 1, so minimum is 1. But cell (1,1) has distance 2 to corners, making it the farthest point.

Example 2 — No Water

$ Input: grid = [[1,0,0],[0,1,0],[0,0,1]]

› Output: 2

💡 Note: Water cells like (0,1) and (0,2) are distance 1 from land, but (0,2) is distance 2 from nearest land at (1,1): |0-1|+|2-1| = 1+1 = 2.

Example 3 — All Land

$ Input: grid = [[1,1],[1,1]]

› Output: -1

💡 Note: No water cells exist, so return -1 as specified in the problem.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Grid

3×3 grid with land (1) and water (0) cells

Calculate Distances

Find distance from each water cell to nearest land

Maximum Distance

Return the largest distance found

Key Takeaway

🎯 Key Insight: Use multi-source BFS starting from all land cells to efficiently find maximum distance to water

Asked in

G Google 15 A Amazon 12 M Microsoft 8 F Facebook 6

The key insight is to use multi-source BFS starting from all land cells simultaneously. This naturally finds the shortest distance from each water cell to the nearest land. Best approach is Multi-Source BFS with Time: O(n²), Space: O(n²).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Water Cell	O(n⁴)	O(1)	For each water cell, calculate distance to all land cells and find minimum
Multi-Source BFS	O(n²)	O(n²)	Start BFS from all land cells simultaneously and expand outward

Brute Force - Check Every Water Cell — Algorithm Steps

Find all water cells and all land cells
For each water cell, calculate distance to every land cell
Keep track of minimum distance for each water cell
Return the maximum of all minimum distances

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Cells

Identify all water (0) and land (1) cells

Check Distances

For each water cell, calculate distance to every land cell

Find Maximum

Track the water cell with maximum distance to nearest land

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int** grid, int n) {
    int waterCells[n*n][2], landCells[n*n][2];
    int waterCount = 0, landCount = 0;
    
    // Find all water and land cells
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0) {
                waterCells[waterCount][0] = i;
                waterCells[waterCount][1] = j;
                waterCount++;
            } else {
                landCells[landCount][0] = i;
                landCells[landCount][1] = j;
                landCount++;
            }
        }
    }
    
    // If no water or no land, return -1
    if (waterCount == 0 || landCount == 0) {
        return -1;
    }
    
    int maxDistance = 0;
    
    // For each water cell, find distance to nearest land
    for (int w = 0; w < waterCount; w++) {
        int minDist = INT_MAX;
        for (int l = 0; l < landCount; l++) {
            int dist = abs(waterCells[w][0] - landCells[l][0]) + 
                      abs(waterCells[w][1] - landCells[l][1]);
            if (dist < minDist) {
                minDist = dist;
            }
        }
        if (minDist > maxDistance) {
            maxDistance = minDist;
        }
    }
    
    return maxDistance;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for small grids
    int n = 0;
    // Count rows by counting ']' - 1
    for (int i = 0; line[i]; i++) {
        if (line[i] == ']') n++;
    }
    n--; // Subtract 1 for outer bracket
    
    int** grid = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
    }
    
    // Parse grid values
    int row = 0, col = 0;
    for (int i = 0; line[i] && row < n; i++) {
        if (line[i] >= '0' && line[i] <= '9') {
            grid[row][col] = line[i] - '0';
            col++;
            if (col == n) {
                col = 0;
                row++;
            }
        }
    }
    
    printf("%d\n", solution(grid, n));
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n⁴)

For each of n² water cells, we check all n² land cells

✓ Linear Growth

Space Complexity

O(1)

Only using variables, no extra data structures

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Every Water Cell — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler