Max Area of Island

🎯

Max Area of Island

mediumGRAPHAmazonFacebookGoogle

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.

💡 This problem is a classic example of exploring connected components in a grid using graph traversal techniques like DFS or BFS. Beginners often struggle because grids are not explicit graphs, and they must translate grid neighbors into graph edges and manage visited states carefully.

📋

Problem Statement

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

💡

Example

Input"[[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]]"

Output6

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

• Grid with all zeros → output 0
• Grid with all ones → output equals total cells
• Grid with one cell only → output 1 if land, else 0
• Grid with multiple small islands → output is max size among them

⚠️

Common Mistakes

Not marking visited cells leading to infinite recursion or double counting

Stack overflow or incorrect area counts

✅ Always mark cells as visited before recursive calls or after popping from stack/queue

Checking diagonal neighbors when problem states only horizontal/vertical connections

Incorrectly larger island areas counted

✅ Restrict neighbor exploration to up, down, left, right only

Not handling grid boundaries properly causing index out of range errors

Runtime exceptions or crashes

✅ Add boundary checks before accessing grid cells

Using recursion without considering maximum recursion depth

Stack overflow on large grids

✅ Use iterative DFS or BFS to avoid recursion limits

Recomputing area for the same island multiple times

Incorrect max area or inefficient code

✅ Use visited set/array to ensure each island is counted once

🧠

Brute Force (DFS with visited set)

💡 Starting with brute force DFS helps understand how to explore each cell and its neighbors recursively. It lays the foundation for more efficient or iterative solutions.

Intuition

For each cell that is land and not visited, recursively explore all connected land cells to find the island's area. Track the maximum area found.

Algorithm

1. Initialize max_area to 0 and a visited set.
2. Iterate over each cell in the grid.
3. If the cell is land and not visited, perform DFS to find the area of that island.
4. Update max_area if the current island's area is larger.

💡 The main challenge is managing visited cells to avoid counting the same land multiple times and correctly exploring neighbors.

</>

Code

from typing import List

def maxAreaOfIsland(grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    visited = set()

    def dfs(r, c):
        if (r < 0 or r >= rows or c < 0 or c >= cols or
            grid[r][c] == 0 or (r, c) in visited):
            return 0
        visited.add((r, c))
        area = 1
        area += dfs(r + 1, c)
        area += dfs(r - 1, c)
        area += dfs(r, c + 1)
        area += dfs(r, c - 1)
        return area

    max_area = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and (r, c) not in visited:
                max_area = max(max_area, dfs(r, c))
    return max_area

# Example usage:
if __name__ == '__main__':
    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]]
    print(maxAreaOfIsland(grid))

Line Notes

visited = set()Track visited cells to avoid revisiting and infinite recursion

def dfs(r, c):Define recursive DFS to explore connected land

if (r < 0 or r >= rows or c < 0 or c >= cols orBoundary and base case checks to stop recursion

visited.add((r, c))Mark current cell as visited to prevent re-exploration

area += dfs(r + 1, c)Explore downward neighbor recursively

for r in range(rows):Iterate over all rows to find islands

if grid[r][c] == 1 and (r, c) not in visited:Start DFS only on unvisited land cells

import java.util.*;

public class MaxAreaOfIsland {
    public static int maxAreaOfIsland(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        int maxArea = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1 && !visited[r][c]) {
                    maxArea = Math.max(maxArea, dfs(grid, visited, r, c));
                }
            }
        }
        return maxArea;
    }

    private static int dfs(int[][] grid, boolean[][] visited, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length ||
            grid[r][c] == 0 || visited[r][c]) {
            return 0;
        }
        visited[r][c] = true;
        int area = 1;
        area += dfs(grid, visited, r + 1, c);
        area += dfs(grid, visited, r - 1, c);
        area += dfs(grid, visited, r, c + 1);
        area += dfs(grid, visited, r, c - 1);
        return area;
    }

    public static void main(String[] args) {
        int[][] 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}
        };
        System.out.println(maxAreaOfIsland(grid));
    }
}

Line Notes

boolean[][] visited = new boolean[rows][cols];Track visited cells to avoid revisiting

if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length ||Boundary and base case checks for recursion

visited[r][c] = true;Mark current cell visited to prevent cycles

area += dfs(grid, visited, r + 1, c);Recursively explore downward neighbor

for (int r = 0; r < rows; r++) {Iterate over all rows to find islands

if (grid[r][c] == 1 && !visited[r][c]) {Start DFS only on unvisited land cells

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        int maxArea = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1 && !visited[r][c]) {
                    maxArea = max(maxArea, dfs(grid, visited, r, c));
                }
            }
        }
        return maxArea;
    }

private:
    int dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int r, int c) {
        if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() ||
            grid[r][c] == 0 || visited[r][c]) {
            return 0;
        }
        visited[r][c] = true;
        int area = 1;
        area += dfs(grid, visited, r + 1, c);
        area += dfs(grid, visited, r - 1, c);
        area += dfs(grid, visited, r, c + 1);
        area += dfs(grid, visited, r, c - 1);
        return area;
    }
};

int main() {
    vector<vector<int>> 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}
    };
    Solution sol;
    cout << sol.maxAreaOfIsland(grid) << endl;
    return 0;
}

Line Notes

vector<vector<bool>> visited(rows, vector<bool>(cols, false));Track visited cells to avoid revisiting

if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() ||Boundary and base case checks for recursion

visited[r][c] = true;Mark current cell visited to prevent cycles

area += dfs(grid, visited, r + 1, c);Recursively explore downward neighbor

for (int r = 0; r < rows; r++) {Iterate over all rows to find islands

if (grid[r][c] == 1 && !visited[r][c]) {Start DFS only on unvisited land cells

function maxAreaOfIsland(grid) {
    const rows = grid.length, cols = grid[0].length;
    const visited = new Set();

    function dfs(r, c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols ||
            grid[r][c] === 0 || visited.has(r + ',' + c)) {
            return 0;
        }
        visited.add(r + ',' + c);
        let area = 1;
        area += dfs(r + 1, c);
        area += dfs(r - 1, c);
        area += dfs(r, c + 1);
        area += dfs(r, c - 1);
        return area;
    }

    let maxArea = 0;
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 1 && !visited.has(r + ',' + c)) {
                maxArea = Math.max(maxArea, dfs(r, c));
            }
        }
    }
    return maxArea;
}

// Example usage:
const 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]
];
console.log(maxAreaOfIsland(grid));

Line Notes

const visited = new Set();Use a set to track visited cells uniquely

if (r < 0 || r >= rows || c < 0 || c >= cols ||Boundary and base case checks to stop recursion

visited.add(r + ',' + c);Mark current cell visited to avoid revisiting

area += dfs(r + 1, c);Recursively explore downward neighbor

for (let r = 0; r < rows; r++) {Iterate over all rows to find islands

if (grid[r][c] === 1 && !visited.has(r + ',' + c)) {Start DFS only on unvisited land cells

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

Each cell is visited once. DFS explores connected land cells. Visited set prevents revisiting.

💡 For a 50x50 grid, this means at most 2500 cells visited once, which is efficient enough for interviews.

Interview Verdict: Accepted

This brute force DFS is efficient enough for the problem constraints and is a solid baseline solution.

🧠

Iterative DFS using Stack

💡 Using an explicit stack instead of recursion avoids call stack overflow and is often preferred in production code or interviews to demonstrate iterative graph traversal.

Intuition

Replace recursive DFS with a stack to explore connected land cells iteratively, tracking visited cells similarly.

Algorithm

1. Initialize max_area to 0 and a visited set.
2. Iterate over each cell in the grid.
3. If the cell is land and not visited, push it onto a stack.
4. While the stack is not empty, pop a cell, mark visited, and push all unvisited land neighbors.
5. Count the area of the island and update max_area.

💡 The main difference is managing the stack explicitly instead of relying on recursion.

</>

Code

from typing import List

def maxAreaOfIsland(grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    visited = set()
    max_area = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and (r, c) not in visited:
                stack = [(r, c)]
                area = 0
                while stack:
                    row, col = stack.pop()
                    if (row, col) in visited:
                        continue
                    visited.add((row, col))
                    area += 1
                    for nr, nc in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in visited:
                            stack.append((nr, nc))
                max_area = max(max_area, area)
    return max_area

# Example usage:
if __name__ == '__main__':
    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]]
    print(maxAreaOfIsland(grid))

Line Notes

stack = [(r, c)]Initialize stack with starting land cell for iterative DFS

while stack:Loop until all connected land cells are explored

if (row, col) in visited:Skip already visited cells to avoid cycles

for nr, nc in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:Check all four neighbors for exploration

max_area = max(max_area, area)Update maximum island area found so far

import java.util.*;

public class MaxAreaOfIsland {
    public static int maxAreaOfIsland(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        int maxArea = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1 && !visited[r][c]) {
                    Stack<int[]> stack = new Stack<>();
                    stack.push(new int[]{r, c});
                    int area = 0;
                    while (!stack.isEmpty()) {
                        int[] cell = stack.pop();
                        int row = cell[0], col = cell[1];
                        if (visited[row][col]) continue;
                        visited[row][col] = true;
                        area++;
                        int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
                        for (int[] d : directions) {
                            int nr = row + d[0], nc = col + d[1];
                            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 && !visited[nr][nc]) {
                                stack.push(new int[]{nr, nc});
                            }
                        }
                    }
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[][] 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}
        };
        System.out.println(maxAreaOfIsland(grid));
    }
}

Line Notes

Stack<int[]> stack = new Stack<>();Use stack to manage cells for iterative DFS

while (!stack.isEmpty()) {Process all connected cells until stack empties

if (visited[row][col]) continue;Skip cells already visited to avoid infinite loops

int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};Define neighbor directions for exploration

maxArea = Math.max(maxArea, area);Update max area after exploring one island

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        int maxArea = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1 && !visited[r][c]) {
                    stack<pair<int,int>> stk;
                    stk.push({r, c});
                    int area = 0;
                    while (!stk.empty()) {
                        auto [row, col] = stk.top();
                        stk.pop();
                        if (visited[row][col]) continue;
                        visited[row][col] = true;
                        area++;
                        vector<pair<int,int>> directions = {{1,0},{-1,0},{0,1},{0,-1}};
                        for (auto& d : directions) {
                            int nr = row + d.first, nc = col + d.second;
                            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 && !visited[nr][nc]) {
                                stk.push({nr, nc});
                            }
                        }
                    }
                    maxArea = max(maxArea, area);
                }
            }
        }
        return maxArea;
    }
};

int main() {
    vector<vector<int>> 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}
    };
    Solution sol;
    cout << sol.maxAreaOfIsland(grid) << endl;
    return 0;
}

Line Notes

stack<pair<int,int>> stk;Use stack to hold cells for iterative DFS

while (!stk.empty()) {Process all connected land cells iteratively

if (visited[row][col]) continue;Skip already visited cells to avoid loops

vector<pair<int,int>> directions = {{1,0},{-1,0},{0,1},{0,-1}};Define neighbor directions for exploration

maxArea = max(maxArea, area);Update max island area after exploration

function maxAreaOfIsland(grid) {
    const rows = grid.length, cols = grid[0].length;
    const visited = new Set();
    let maxArea = 0;

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 1 && !visited.has(r + ',' + c)) {
                const stack = [[r, c]];
                let area = 0;
                while (stack.length > 0) {
                    const [row, col] = stack.pop();
                    if (visited.has(row + ',' + col)) continue;
                    visited.add(row + ',' + col);
                    area++;
                    const directions = [[1,0],[-1,0],[0,1],[0,-1]];
                    for (const [dr, dc] of directions) {
                        const nr = row + dr, nc = col + dc;
                        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1 && !visited.has(nr + ',' + nc)) {
                            stack.push([nr, nc]);
                        }
                    }
                }
                maxArea = Math.max(maxArea, area);
            }
        }
    }
    return maxArea;
}

// Example usage:
const 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]
];
console.log(maxAreaOfIsland(grid));

Line Notes

const stack = [[r, c]];Initialize stack with starting land cell for iterative DFS

while (stack.length > 0) {Process all connected land cells until stack empties

if (visited.has(row + ',' + col)) continue;Skip already visited cells to avoid infinite loops

const directions = [[1,0],[-1,0],[0,1],[0,-1]];Define neighbor directions for exploration

maxArea = Math.max(maxArea, area);Update maximum island area found so far

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

Each cell is visited once. Stack replaces recursion but complexity remains the same.

💡 For a 50x50 grid, this iterative approach is just as efficient but safer for deep recursion cases.

Interview Verdict: Accepted

Iterative DFS is a robust alternative to recursion, often preferred in interviews to show mastery of graph traversal.

🧠

Breadth-First Search (BFS)

💡 BFS explores neighbors level-by-level using a queue. It is an alternative to DFS and can be easier to understand for some. It also avoids recursion.

Intuition

For each unvisited land cell, use a queue to explore all connected land cells breadth-wise, counting the island area.

Algorithm

1. Initialize max_area to 0 and a visited set.
2. Iterate over each cell in the grid.
3. If the cell is land and not visited, enqueue it.
4. While the queue is not empty, dequeue a cell, mark visited, and enqueue all unvisited land neighbors.
5. Count the area of the island and update max_area.

💡 BFS uses a queue instead of a stack or recursion, but the logic of exploring neighbors is similar.

</>

Code

from typing import List
from collections import deque

def maxAreaOfIsland(grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    visited = set()
    max_area = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and (r, c) not in visited:
                queue = deque([(r, c)])
                area = 0
                while queue:
                    row, col = queue.popleft()
                    if (row, col) in visited:
                        continue
                    visited.add((row, col))
                    area += 1
                    for nr, nc in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in visited:
                            queue.append((nr, nc))
                max_area = max(max_area, area)
    return max_area

# Example usage:
if __name__ == '__main__':
    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]]
    print(maxAreaOfIsland(grid))

Line Notes

from collections import dequeImport deque for efficient queue operations

queue = deque([(r, c)])Initialize queue with starting land cell for BFS

while queue:Process cells level-by-level until queue empties

if (row, col) in visited:Skip already visited cells to avoid cycles

queue.append((nr, nc))Enqueue unvisited land neighbors for exploration

import java.util.*;

public class MaxAreaOfIsland {
    public static int maxAreaOfIsland(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        int maxArea = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1 && !visited[r][c]) {
                    Queue<int[]> queue = new LinkedList<>();
                    queue.offer(new int[]{r, c});
                    int area = 0;
                    while (!queue.isEmpty()) {
                        int[] cell = queue.poll();
                        int row = cell[0], col = cell[1];
                        if (visited[row][col]) continue;
                        visited[row][col] = true;
                        area++;
                        int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
                        for (int[] d : directions) {
                            int nr = row + d[0], nc = col + d[1];
                            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 && !visited[nr][nc]) {
                                queue.offer(new int[]{nr, nc});
                            }
                        }
                    }
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[][] 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}
        };
        System.out.println(maxAreaOfIsland(grid));
    }
}

Line Notes

Queue<int[]> queue = new LinkedList<>();Use queue to manage BFS exploration

while (!queue.isEmpty()) {Process cells in FIFO order for BFS

if (visited[row][col]) continue;Skip already visited cells to avoid infinite loops

int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};Define neighbor directions for exploration

maxArea = Math.max(maxArea, area);Update max island area after BFS completes

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        int maxArea = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1 && !visited[r][c]) {
                    queue<pair<int,int>> q;
                    q.push({r, c});
                    int area = 0;
                    while (!q.empty()) {
                        auto [row, col] = q.front();
                        q.pop();
                        if (visited[row][col]) continue;
                        visited[row][col] = true;
                        area++;
                        vector<pair<int,int>> directions = {{1,0},{-1,0},{0,1},{0,-1}};
                        for (auto& d : directions) {
                            int nr = row + d.first, nc = col + d.second;
                            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 && !visited[nr][nc]) {
                                q.push({nr, nc});
                            }
                        }
                    }
                    maxArea = max(maxArea, area);
                }
            }
        }
        return maxArea;
    }
};

int main() {
    vector<vector<int>> 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}
    };
    Solution sol;
    cout << sol.maxAreaOfIsland(grid) << endl;
    return 0;
}

Line Notes

queue<pair<int,int>> q;Use queue to hold cells for BFS exploration

while (!q.empty()) {Process cells in FIFO order to explore neighbors level-wise

if (visited[row][col]) continue;Skip already visited cells to avoid cycles

vector<pair<int,int>> directions = {{1,0},{-1,0},{0,1},{0,-1}};Define neighbor directions for BFS

maxArea = max(maxArea, area);Update max island area after BFS completes

function maxAreaOfIsland(grid) {
    const rows = grid.length, cols = grid[0].length;
    const visited = new Set();
    let maxArea = 0;

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 1 && !visited.has(r + ',' + c)) {
                const queue = [[r, c]];
                let area = 0;
                while (queue.length > 0) {
                    const [row, col] = queue.shift();
                    if (visited.has(row + ',' + col)) continue;
                    visited.add(row + ',' + col);
                    area++;
                    const directions = [[1,0],[-1,0],[0,1],[0,-1]];
                    for (const [dr, dc] of directions) {
                        const nr = row + dr, nc = col + dc;
                        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1 && !visited.has(nr + ',' + nc)) {
                            queue.push([nr, nc]);
                        }
                    }
                }
                maxArea = Math.max(maxArea, area);
            }
        }
    }
    return maxArea;
}

// Example usage:
const 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]
];
console.log(maxAreaOfIsland(grid));

Line Notes

const queue = [[r, c]];Initialize queue with starting land cell for BFS

while (queue.length > 0) {Process cells in FIFO order until queue empties

if (visited.has(row + ',' + col)) continue;Skip already visited cells to avoid infinite loops

const directions = [[1,0],[-1,0],[0,1],[0,-1]];Define neighbor directions for BFS

maxArea = Math.max(maxArea, area);Update maximum island area after BFS completes

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

Each cell is visited once. BFS explores neighbors level-wise using a queue.

💡 For a 50x50 grid, BFS is efficient and avoids recursion, making it a safe choice.

Interview Verdict: Accepted

BFS is a clean alternative to DFS and is accepted for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the recursive DFS or iterative DFS is sufficient. BFS is a good alternative if you prefer queue-based traversal or want to avoid recursion.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force DFS (Recursive)	O(m*n)	O(m*n) due to recursion stack and visited set	Yes (deep recursion)	N/A	Good to explain and code if recursion depth is manageable
2. Iterative DFS (Stack)	O(m*n)	O(m*n) for stack and visited set	No	N/A	Preferred for large inputs or to avoid recursion
3. BFS (Queue)	O(m*n)	O(m*n) for queue and visited set	No	N/A	Good alternative to DFS, especially if BFS is more familiar

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach, and progressively discuss iterative and BFS solutions. Practice coding and testing edge cases.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force DFS approach and its intuition.Step 3: Discuss iterative DFS to avoid recursion depth issues.Step 4: Present BFS as an alternative traversal method.Step 5: Code your chosen approach carefully and test with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 7min. Total ~25min

What the Interviewer Tests

The interviewer tests your understanding of graph traversal on grids, handling of visited states, boundary conditions, and ability to optimize recursion with iteration or BFS.

Common Follow-ups

• What if diagonal connections count as connected? → Modify neighbor checks to include diagonals.
• How to handle very large grids? → Use iterative methods and possibly union-find for offline queries.

💡 These follow-ups test your adaptability and understanding of graph connectivity variations and scalability.

🔍

Pattern Recognition

When to Use

1) Problem involves a grid or matrix, 2) Need to find connected components, 3) Connectivity is horizontal/vertical neighbors, 4) Need to compute max/min/total size of connected regions

Signature Phrases

largest connected islandconnected horizontally or verticallygrid of 0s and 1sfind max area of island

NOT This Pattern When

Problems involving shortest path or weighted graphs are different patterns, e.g., Dijkstra or A*.

Similar Problems

Number of Islands - count how many connected islands existFlood Fill - change color of connected regionSurrounded Regions - capture surrounded areas in grid

Practice

1. Consider the following Python code that counts connected components using BFS. What is the value of count returned by countComponents(4, [[0,1],[2,3]])?

easy

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Trace BFS starting from node 0

   Nodes 0 and 1 are connected, so BFS visits both, marking them visited. This forms one component.

2. Step 2: Trace BFS starting from node 2

   Nodes 2 and 3 are connected, BFS visits both, marking them visited. This forms the second component.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two disconnected pairs -> 2 components [OK]

Hint: Count increments once per unvisited node BFS start [OK]

Common Mistakes:

• Counting edges instead of components
• Off-by-one in count increment

2. Identify the bug in the following code snippet intended to find the center of a star graph:

medium

A. Line 4: Incorrect initialization of frequency dictionary

B. Line 9: Incorrect condition to check center node frequency

C. Line 11: Returning node inside loop instead of after loop

D. Line 7: Missing frequency update for node v in each edge

Solution

1. Step 1: Inspect frequency updates

   The code updates frequency for u but misses updating for v, so counts are incomplete.

2. Step 2: Consequence of missing update

   Without counting both nodes per edge, the center node frequency will be underestimated, causing incorrect results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Both nodes in each edge must be counted for correct frequency [OK]

Hint: Both nodes in each edge must be counted [OK]

Common Mistakes:

• Counting only one node per edge
• Incorrect frequency condition
• Returning too early in loop

3. Examine the following modified Union-Find based bipartite check code. Which line contains a subtle bug that can cause incorrect results on disconnected graphs?

medium

A. Line: for node in range(n):

B. Line: for i in range(1, len(graph[node])):

C. Line: if not uf.union(graph[node][0], graph[node][i]):

D. Line: return True

Solution

1. Step 1: Identify missing iteration over disconnected components

   The loop iterates over all nodes, but the union-find approach requires checking all connected components separately to detect conflicts.

2. Step 2: Recognize that skipping isolated components causes missed conflicts

   If the graph has disconnected parts, conflicts in unvisited components won't be detected, causing false positives.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Iterating over all nodes is necessary but must include component checks [OK]

Hint: Missing component checks cause false bipartite positives [OK]

Common Mistakes:

• Assuming single pass covers all components
• Ignoring isolated nodes

4. What is the time complexity of the optimal algorithm that finds the minimum number of vertices to reach all nodes in a directed acyclic graph with n nodes and e edges?

medium

A. O(n * e) because each node is processed for all edges

B. O(n + e) because each node and edge is processed once

C. O(n^2) because of nested loops over nodes

D. O(e log n) due to priority queue operations in topological sort

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm iterates over all edges once to build the graph and in-degree array, then processes each node and its edges once during the queue processing.

2. Step 2: Combine complexities

   Building graph: O(e), processing nodes and edges in BFS: O(n + e). No nested loops over all nodes and edges.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time in nodes and edges for DAG traversal [OK]

Hint: Topological sort runs in O(n + e) time [OK]

Common Mistakes:

• Assuming nested loops cause O(n*e)
• Confusing with dense graph complexities
• Thinking priority queues are used

5. Suppose the graph edges can have negative weights but no negative cycles. Which algorithm modification or choice correctly computes the shortest network delay times from a start node?

hard

A. Use DFS with path relaxation and memoization to handle negative weights efficiently.

B. Use Dijkstra's algorithm with a priority queue as usual; it handles negative weights correctly.

C. Use BFS since negative weights can be ignored for shortest paths.

D. Use Bellman-Ford algorithm to relax edges repeatedly, detecting negative cycles if any.

Solution

1. Step 1: Recognize that Dijkstra's algorithm fails with negative weights because it assumes non-negative edge costs

   BFS cannot handle weighted edges properly, and DFS with memoization is inefficient and may not terminate correctly.

2. Step 2: Bellman-Ford algorithm is designed to handle negative weights and detect negative cycles by repeated edge relaxation

   It guarantees correct shortest paths if no negative cycles exist.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bellman-Ford handles negative weights safely [OK]

Hint: Bellman-Ford handles negative weights; Dijkstra does not [OK]

Common Mistakes:

• Using Dijkstra with negative weights incorrectly
• Assuming BFS works for weighted graphs
• Believing DFS with memoization is efficient here