Max Area of Island

📋

Problem

Imagine you are analyzing satellite images of an archipelago to find the largest island by area. Each pixel is either land or water, and you want to find the biggest connected landmass.

Given a 2D grid of 0s and 1s, where 1 represents land and 0 represents water, find the size (number of cells) of the largest connected island. An island is a group of 1s connected horizontally or vertically. Return 0 if no island exists.

m == grid.lengthn == grid[i].length1 ≤ m, n ≤ 50grid[i][j] is either 0 or 1

Edge cases: Grid with all zeros → output 0Grid with all ones → output equals total cellsGrid with one cell only → output 1 if land, else 0

</>

IDE

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

def maxAreaOfIsland(grid):
    # Write your solution here
    pass

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maxAreaOfIsland(vector<vector<int>>& grid) {
    // Write your solution here
    return 0;
}

function maxAreaOfIsland(grid) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Counting diagonal neighbors as connectedIncorrect neighbor checks include diagonals instead of only up/down/left/right.✅ Change neighbor exploration to only four directions: (r+1,c), (r-1,c), (r,c+1), (r,c-1).

Wrong: Returning 0 for single land cell gridNot handling single cell grids or missing base case.✅ Add base case to return 1 if grid has one cell with value 1.

Wrong: Underestimating max area by stopping earlyGreedy approach that returns first island size found instead of max.✅ Explore all islands and track maximum area found.

Wrong: Returning non-zero for all water gridNot checking for land presence or incorrect initialization.✅ Return 0 if no land cells found after full traversal.

Wrong: TLE on large gridsUsing exponential or repeated DFS without visited set.✅ Use visited set and O(m*n) DFS/BFS to avoid repeated work.

✓

Test Cases

Try testing your solution on grids with no land or only one cell to catch base case bugs.

Consider tricky island shapes and ensure your traversal only connects orthogonally.

Focus on algorithmic efficiency and avoid repeated work to pass large input tests.

t1_01basic

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

Expected6

⏱ Performance - must finish in 2000ms

The largest island has 6 connected land cells. DFS or BFS can find and count connected components to determine this.

💡 Think about traversing the grid to find connected components of 1s.

💡 Use DFS or BFS to explore all connected land cells and count their area.

💡 Keep track of visited cells to avoid counting the same land multiple times.

Why it failed: Returned incorrect max area; likely missed marking visited cells or incorrect DFS/BFS traversal. Fix by ensuring visited set and exploring all four directions properly.

✓ Correctly identifies the largest connected island area.

t1_02basic

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

Expected4

⏱ Performance - must finish in 2000ms

There are two islands: one of size 4 (top-left) and one of size 4 (top-right). The max area is 4.

💡 Identify all islands and compare their sizes.

💡 Remember to reset visited for each new island search.

💡 Return the maximum area found after checking all cells.

Why it failed: Incorrect max area; possibly not resetting visited or not exploring all connected cells. Fix by proper DFS/BFS and visited tracking.

✓ Correctly computes max island area among multiple islands.

t2_01edge

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

Expected0

⏱ Performance - must finish in 2000ms

Grid with all water cells; no islands exist, so max area is 0.

💡 Check if the grid contains any land cells at all.

💡 If no land found, return 0 immediately.

💡 Ensure your code handles grids with no islands gracefully.

Why it failed: Returned non-zero area for all water grid; fix by checking for land presence before DFS/BFS.

✓ Correctly returns 0 when no islands exist.

t2_02edge

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

Expected1

⏱ Performance - must finish in 2000ms

Single cell grid with land; max area is 1.

💡 Handle smallest grid sizes correctly.

💡 Check single cell neighbors carefully (none in this case).

💡 Return 1 if the single cell is land.

Why it failed: Returned 0 for single land cell; fix by handling single cell grids and counting land correctly.

✓ Correctly returns 1 for single land cell grid.

t2_03edge

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

Expected25

⏱ Performance - must finish in 2000ms

Grid with all land cells; max area equals total cells (5x5=25).

💡 Check if your code can handle large connected components.

💡 Ensure no cells are missed or double counted.

💡 Return total number of cells if all are land.

Why it failed: Returned less than total cells for all land grid; fix by ensuring full traversal and no early stopping.

✓ Correctly returns total cells count for all land grid.

t3_01corner

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

Expected1

⏱ Performance - must finish in 2000ms

Multiple islands of size 1 separated diagonally; max area is 1.

💡 Remember islands connect only horizontally or vertically, not diagonally.

💡 Check neighbors carefully to avoid diagonal connections.

💡 Count each isolated land cell as separate island of size 1.

Why it failed: Incorrectly counted diagonal neighbors as connected; fix by checking only up/down/left/right neighbors.

✓ Correctly counts islands connected only orthogonally.

t3_02corner

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

Expected7

⏱ Performance - must finish in 2000ms

Two islands: one large of size 7 and one smaller of size 4; max area is 7.

💡 Ensure you do not merge separate islands incorrectly.

💡 Track visited cells to avoid double counting.

💡 Return the largest connected component size.

Why it failed: Merged separate islands or missed some cells; fix by proper visited tracking and separate DFS/BFS calls.

✓ Correctly identifies largest island among multiple.

t3_03corner

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

Expected5

⏱ Performance - must finish in 2000ms

Largest island has 5 connected cells; tests correct DFS/BFS traversal and no greedy mistakes.

💡 Avoid greedy approaches that pick first found island only.

💡 Explore all islands to find the maximum area.

💡 Use complete DFS/BFS to count connected cells accurately.

Why it failed: Returned smaller area due to greedy stopping early; fix by exploring all islands fully.

✓ Correctly finds max island area by exploring all.

t4_01performance

Input{"_description":"n=50x50 grid at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Grid size 50x50 (max constraints). Algorithm must run in O(m*n) time within 2 seconds.

💡 Use O(m*n) DFS or BFS to avoid timeouts.

💡 Avoid repeated work by marking visited cells.

💡 Iterate over all cells once and explore islands efficiently.

Why it failed: TLE due to exponential or repeated work; fix by using visited set and O(m*n) DFS/BFS.

✓ Algorithm runs within time limits using efficient graph traversal.

Practice

1. You are given a connected undirected graph where each node contains a value and a list of its neighbors. The task is to create a deep copy of this graph such that the cloned graph has the same structure but no shared nodes with the original. Which algorithmic approach guarantees an optimal solution that handles cycles and multiple components correctly?

easy

A. Use a brute force DFS that recursively clones neighbors without tracking visited nodes.

B. Use BFS or DFS with a hash map to track visited nodes and clone each node exactly once.

C. Use a greedy approach that clones nodes only when their values are unique.

D. Use dynamic programming to store intermediate clone results indexed by node values.

Solution

1. Step 1: Understand the problem constraints

   The graph may contain cycles and multiple components, so naive recursion can cause infinite loops or duplicate clones.

2. Step 2: Identify the correct approach

   Using BFS or DFS with a hash map to track visited nodes ensures each node is cloned once, preventing infinite recursion and preserving graph structure.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Tracking visited nodes avoids infinite loops and duplicates [OK]

Hint: Track visited nodes to avoid infinite recursion [OK]

Common Mistakes:

• Not tracking visited nodes causes infinite recursion
• Using node values as keys fails with duplicate values

2. Consider the following Python code for checking if a graph is a valid tree. What is the return value when calling valid_tree(4, [[0,1],[1,2],[2,3]])?

easy

A. true

B. false

C. Raises an exception

D. Returns null

Solution

1. Step 1: Check edge count

   Edges count is 3, nodes count is 4, so edges == n-1 condition passes.

2. Step 2: BFS traversal and cycle detection

   Starting from node 0, BFS visits nodes 0,1,2,3 without revisiting any node or detecting cycles. All nodes are visited.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Graph is connected and acyclic, so valid tree [OK]

Hint: Edges must be n-1 and BFS visits all nodes [OK]

Common Mistakes:

• Confusing cycle detection with revisiting parent
• Forgetting to check all nodes visited

3. You are given a set of rooms, each containing keys to other rooms. Starting from room 0, you want to determine if you can visit every room by collecting keys along the way. Which algorithmic approach guarantees an optimal solution to this problem?

easy

A. Graph traversal using DFS or BFS with a visited set to avoid revisiting rooms

B. Sorting rooms by number of keys and visiting in descending order

C. Dynamic programming to store reachable rooms and combine results

D. Greedy algorithm that picks the room with the most keys first

Solution

1. Step 1: Understand the problem as graph traversal

   The rooms and keys form a directed graph where edges represent keys leading to other rooms.

2. Step 2: Identify the correct algorithmic pattern

   DFS or BFS with a visited set ensures all reachable nodes (rooms) are visited without repetition, guaranteeing correctness and optimality.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Graph traversal with visited set is standard for reachability [OK]

Hint: Keys and Rooms is a graph reachability problem [OK]

Common Mistakes:

• Thinking greedy approach works because more keys means more rooms
• Trying DP which is unnecessary and overcomplicates
• Sorting rooms doesn't guarantee connectivity

4. You are given a 2D grid map of '1's (land) and '0's (water). You need to count the number of distinct islands, where an island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Which algorithmic approach guarantees an optimal solution to this problem?

easy

A. Use Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse connected components in the grid.

B. Use a sorting-based approach to group land cells and count islands.

C. Use Dynamic Programming to store intermediate island counts for subgrids.

D. Use a greedy approach to count islands by scanning rows and columns independently.

Solution

1. Step 1: Understand the problem as finding connected components in a grid

   The problem requires identifying groups of adjacent '1's connected horizontally or vertically, which is a classic graph traversal problem.

2. Step 2: Recognize that DFS or BFS traversals efficiently explore connected components

   DFS or BFS starting from each unvisited land cell will mark all connected land cells as visited, ensuring each island is counted exactly once.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DFS/BFS is the standard approach for connected components in grids [OK]

Hint: Islands = connected components -> use DFS/BFS [OK]

Common Mistakes:

• Thinking greedy or sorting can identify islands correctly.

5. What is the time complexity of the bidirectional BFS algorithm for finding the shortest path in an n x n binary matrix, assuming all cells are walkable (0)?

medium

A. O(n^4) because each BFS can explore all cells and edges

B. O(8^(n^2)) due to 8 possible moves from each cell

C. O(n^2) because BFS explores each cell at most once from both ends

D. O(n^3) because of nested loops over rows, columns, and directions

Solution

1. Step 1: Identify number of vertices and edges

   Grid has n^2 vertices; each vertex has up to 8 edges.

2. Step 2: Analyze BFS complexity

   BFS visits each vertex once; total edges processed is O(8*n^2) = O(n^2).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bidirectional BFS halves search space but still O(n^2) [OK]

Hint: BFS in grid -> O(n²) due to vertices and edges [OK]

Common Mistakes:

• Confusing exponential moves with complexity
• Assuming nested loops multiply to n^3 or n^4