As Far from Land as Possible

📋

As Far from Land as Possible

Edge cases:

</>

IDE

def maxDistance(grid: List[List[int]]) -> int:public int maxDistance(int[][] grid)int maxDistance(vector<vector<int>>& grid)function maxDistance(grid)

def maxDistance(grid: List[List[int]]) -> int:
    # Write your solution here
    pass

class Solution {
    public int maxDistance(int[][] grid) {
        // Write your solution here
        return -1;
    }
}

#include <vector>
using namespace std;

int maxDistance(vector<vector<int>>& grid) {
    // Write your solution here
    return -1;
}

function maxDistance(grid) {
    // Write your solution here
    return -1;
}

Common Bugs to Avoid

Wrong: -1 when water cells existReturning -1 prematurely without checking for water cells or land cells properly.✅ Add explicit checks: if no land or no water cells, return -1; else proceed with BFS.

Wrong: 0 or 1 for max distance when it should be largerUsing single-source BFS or greedy approach starting from one land cell only.✅ Initialize BFS queue with all land cells to perform multi-source BFS.

Wrong: Too small max distance due to BFS stopping earlyNot expanding BFS fully or incorrect distance updates for water cells.✅ Continue BFS until all reachable water cells are processed and distances updated.

Wrong: TLE on large inputsUsing brute force approach with O(n^4) complexity.✅ Implement multi-source BFS with O(n^2) complexity.

✓

Test Cases

Make sure your solution handles grids with no water or no land cells correctly.

Test your BFS approach on tricky grids with multiple land cells and verify distances.

Optimize your solution to run efficiently on large 100x100 grids using multi-source BFS.

t1_01basic

Input{"grid":[[1,0,1],[0,0,0],[1,0,1]]}

Expected2

⏱ Performance - must finish in 2000ms

The water cell at the center (1,1) is 2 steps away from the nearest land cell.

💡 Consider BFS starting from all land cells simultaneously.

💡 Use a multi-source BFS to find the shortest distance to land for each water cell.

💡 The maximum distance found among all water cells is the answer.

Why it failed: Incorrect output likely due to not performing multi-source BFS or incorrect distance calculation. Fix by initializing BFS queue with all land cells and updating distances for water cells.

✓ Correctly computed maximum distance using multi-source BFS.

t1_02basic

Input{"grid":[[1,0,0],[0,0,0],[0,0,0]]}

Expected4

⏱ Performance - must finish in 2000ms

The water cell at (2,2) is 4 steps away from the only land cell at (0,0).

💡 Check distances from the single land cell to all water cells.

💡 Use Manhattan distance or BFS to find shortest paths.

💡 The farthest water cell from land is at bottom-right corner with distance 4.

Why it failed: Output incorrect due to not considering all water cells or wrong distance metric. Fix by using BFS or Manhattan distance correctly for all water cells.

✓ Correctly identified the farthest water cell distance.

t2_01edge

Input{"grid":[[1]]}

Expected-1

⏱ Performance - must finish in 2000ms

Grid with only one cell which is land; no water cell exists, so return -1.

💡 Check if there are any water cells in the grid.

💡 If no water cells exist, the answer must be -1.

💡 Return -1 immediately when grid is all land.

Why it failed: Returned a non -1 value despite no water cells. Fix by adding a check for presence of water cells before BFS.

✓ Correctly returned -1 for grid with no water cells.

t2_02edge

Input{"grid":[[0]]}

Expected-1

⏱ Performance - must finish in 2000ms

Grid with only one cell which is water; no land cell exists, so return -1.

💡 Check if there are any land cells in the grid.

💡 If no land cells exist, the answer must be -1.

💡 Return -1 immediately when grid is all water.

Why it failed: Returned a non -1 value despite no land cells. Fix by adding a check for presence of land cells before BFS.

✓ Correctly returned -1 for grid with no land cells.

t2_03edge

Input{"grid":[[1,1,1],[1,1,1],[1,1,1]]}

Expected-1

⏱ Performance - must finish in 2000ms

Grid with all land cells; no water cell exists, so return -1.

💡 Verify if the grid contains any water cells.

💡 If none, return -1 immediately.

💡 Avoid running BFS when no water cells are present.

Why it failed: Incorrectly computed distance when grid is all land. Fix by checking for water cells before BFS.

✓ Correctly returned -1 for all land grid.

t2_04edge

Input{"grid":[[1,0,1,0],[0,0,0,0],[1,0,1,0],[0,0,0,0]]}

Expected2

⏱ Performance - must finish in 2000ms

Grid with land cells only on edges; max distance inside grid is 2.

💡 Check distances from edge land cells to inner water cells.

💡 Use multi-source BFS starting from all land cells on edges.

💡 The farthest water cells are 2 steps away from nearest land.

Why it failed: Incorrect max distance due to ignoring multiple land sources or incorrect BFS initialization. Fix by including all land cells as BFS sources.

✓ Correctly computed max distance with land on edges.

t3_01corner

Input{"grid":[[0,0,0],[0,1,0],[0,0,0]]}

Expected2

⏱ Performance - must finish in 2000ms

The farthest water cells are corners at distance 2 from the single land cell at center.

💡 Check if BFS correctly expands from all land cells.

💡 Ensure distances are updated for all reachable water cells.

💡 Verify BFS does not stop prematurely and covers entire grid.

Why it failed: Output too small due to BFS stopping early or not updating all distances. Fix by continuing BFS until all water cells are processed.

✓ Correctly computed max distance by full BFS expansion.

t3_02corner

Input{"grid":[[1,0,0,0],[0,0,0,0],[0,0,0,1],[0,0,0,0]]}

Expected3

⏱ Performance - must finish in 2000ms

The farthest water cell is at (3,0) with distance 3 from nearest land at (0,0) or (2,3).

💡 Beware of greedy approaches that pick only one land cell as source.

💡 Use multi-source BFS starting from all land cells simultaneously.

💡 This ensures shortest distance to nearest land is found for each water cell.

Why it failed: Incorrect output due to using single-source BFS or greedy approach. Fix by initializing BFS queue with all land cells.

✓ Correctly used multi-source BFS to find max distance.

t3_03corner

Input{"grid":[[1,0,1,0],[0,0,0,0],[1,0,1,0],[0,0,0,0]]}

Expected2

⏱ Performance - must finish in 2000ms

Multiple land cells; max distance water cells are 2 steps away from nearest land.

💡 Check that BFS does not confuse 0/1 constraints or treat water as land.

💡 Ensure BFS only expands from land cells and updates water distances.

💡 Verify no off-by-one errors in distance calculation.

Why it failed: Wrong output due to treating water cells as land or off-by-one distance errors. Fix by correctly initializing BFS and updating distances only for water cells.

✓ Correctly handled multiple land cells and distances.

t4_01performance

Input{"grid":[[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]}

Expectednull

⏱ Performance - must finish in 2000ms

Large 100x100 grid with scattered land cells; solution must run in O(n^2) time within 2 seconds.

💡 Brute force O(n^4) approach will time out on this input.

💡 Use multi-source BFS to achieve O(n^2) time complexity.

💡 Initialize BFS queue with all land cells and expand simultaneously.

Why it failed: TLE due to brute force or inefficient approach. Fix by implementing multi-source BFS with O(n^2) complexity.

✓ Efficient O(n^2) BFS solution confirmed by passing performance test.

Practice

1. You are given an undirected graph with n nodes and a list of edges. The task is to find how many groups of nodes exist such that each group is fully connected internally and disconnected from other groups. Which algorithmic approach guarantees an optimal solution to this problem?

easy

A. Graph traversal using BFS or DFS to explore connected components

B. Dynamic Programming with memoization to count connected subgraphs

C. Greedy algorithm selecting edges to maximize connectivity

D. Topological sorting to order nodes and count components

Solution

1. Step 1: Understand the problem as counting connected components in an undirected graph

   Counting connected components requires visiting all nodes reachable from a starting node before moving to the next unvisited node.

2. Step 2: Identify BFS or DFS as the standard approach to explore all nodes in a component efficiently

   BFS or DFS traverses all nodes in a component in O(n + e) time, ensuring all connected nodes are counted once.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS/DFS is the classic method for connected components [OK]

Hint: Connected components require graph traversal [OK]

Common Mistakes:

• Confusing with DP or greedy approaches that don't guarantee full exploration

2. Consider the following Python code implementing bidirectional BFS to find the shortest path in a binary matrix. Given the input grid below, what is the returned shortest path length?

grid = [
  [0, 1, 0],
  [1, 0, 0],
  [1, 1, 0]
]

# Code snippet uses the bidirectional BFS approach as described.

What is the output of shortestPathBinaryMatrix(grid)?

easy

A. 3

B. 5

C. -1

D. 4

Solution

1. Step 1: Trace BFS from start (0,0)

   Start at (0,0) with distance 1. Neighbors reachable: (1,1) at distance 2.

2. Step 2: Trace BFS from end (2,2)

   Start at (2,2) with distance 1. Neighbors reachable: (1,2) at distance 2, (1,1) at distance 2.

3. Step 3: Meeting point

   Both searches meet at (1,1). Sum distances: 2 (start side) + 2 (end side) = 4, but since both include the meeting cell, shortest path length is 3.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Shortest path length is 3 steps [OK]

Hint: Bidirectional BFS meets in middle, sum distances minus 1 [OK]

Common Mistakes:

• Off-by-one in path length
• Ignoring meeting cell counted twice

3. You are given a 2D grid containing 'X' and 'O'. The goal is to flip all 'O's that are completely surrounded by 'X's into 'X's themselves, but keep 'O's connected to the boundary unchanged. Which algorithmic approach best guarantees an optimal solution for this problem?

easy

A. Use a brute force approach checking each 'O' region independently with DFS to see if it touches the boundary.

B. Mark all 'O's connected to the boundary first using BFS or DFS, then flip the rest of the 'O's to 'X'.

C. Apply dynamic programming to store subproblems of surrounded regions and combine results.

D. Use a greedy approach to flip 'O's as soon as they are found surrounded by 'X's.

Solution

1. Step 1: Understand the problem constraints

   The problem requires flipping only those 'O's that are fully surrounded by 'X's, meaning 'O's connected to the boundary must remain unchanged.

2. Step 2: Identify the correct approach

   Marking all 'O's connected to the boundary first ensures these safe regions are preserved. Then flipping the rest is straightforward. This approach is efficient and guarantees correctness.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Boundary-connected marking prevents flipping safe 'O's [OK]

Hint: Mark boundary-connected 'O's first to preserve them [OK]

Common Mistakes:

• Trying to check each 'O' region independently leads to high complexity.
• Using greedy flips misses connected 'O's that should be preserved.
• Dynamic programming is not suitable for connectivity problems on grids.

4. What is the time complexity of the optimal Dijkstra-based algorithm for finding the cheapest flight within K stops, given n cities and E flights? Assume the graph is represented as adjacency lists and a min-heap is used. A) O(n^2) because we may visit all nodes multiple times. B) O(E log E) because each edge can be pushed into the heap once. C) O(n log n) because Dijkstra runs in that time on sparse graphs. D) O(K * E) because we relax edges up to K times.

medium

A. O(n^2) because we may visit all nodes multiple times.

B. O(K * E) because we relax edges up to K times.

C. O(E log E) because each edge can be pushed into the heap once.

D. O(n log n) because Dijkstra runs in that time on sparse graphs.

Solution

1. Step 1: Identify heap operations

   Each edge can be pushed into the heap at most once per stops count, but stops ≤ K limits pushes. The heap size is bounded by O(E).

2. Step 2: Analyze complexity

   Each push/pop operation costs O(log E), so total time is O(E log E). The stops constraint prevents exponential blowup.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Heap operations dominate; stops limit expansions [OK]

Hint: Heap operations on edges dominate complexity [OK]

Common Mistakes:

• Assuming O(n^2) from classic Dijkstra on adjacency matrix
• Ignoring that stops limit expansions
• Confusing Bellman-Ford complexity with this approach

5. What is the worst-case space complexity of the in-place DFS solution for the Number of Islands problem on an m x n grid, considering the recursion stack usage?

medium

A. O(1) -- since the grid is modified in-place, no extra space is needed.

B. O(min(m, n)) -- recursion depth limited by smaller grid dimension.

C. O(m*n) -- recursion stack can grow up to the size of the entire grid in worst case.

D. O(m + n) -- recursion stack limited by sum of rows and columns.

Solution

1. Step 1: Identify auxiliary space usage

   The grid is modified in-place, so no extra data structures are used except recursion stack.

2. Step 2: Analyze recursion stack depth

   In worst case (e.g., one large island), DFS can recurse over all cells, leading to recursion stack depth O(m*n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Recursion stack can be as large as all grid cells in worst case [OK]

Hint: Recursion stack can be as large as island size [OK]

Common Mistakes:

• Assuming constant space due to in-place modification
• Confusing recursion depth with grid dimensions