Backend interview prep

Start Learning

Count Islands in a Matrix

Java coding interview problem for Matrix Problems: Count Islands in a Matrix.

The Count Islands in a Matrix problem is one of the most popular matrix traversal problems in coding interviews.

It is commonly asked because it combines:

  • Matrix traversal
  • Graph algorithms
  • Depth First Search (DFS)
  • Breadth First Search (BFS)
  • Connected components

This problem appears in interviews at:

  • Google
  • Amazon
  • Microsoft
  • Meta
  • Apple

What is Count Islands in a Matrix?

Given a matrix containing:

1

and

0

where:

  • 1 represents land
  • 0 represents water

we need to count the number of separate islands.

An island is formed by connected land cells.

Example

Input:

[
 [1,1,0,0],

 [1,1,0,0],

 [0,0,1,0],

 [0,0,0,1]
]

Visualization:

L L W W

L L W W

W W L W

W W W L

There are:

Island 1:

1 1

1 1

Island 2:

1

Island 3:

1

Output:

3

Understanding Grid Traversal

A matrix can be considered a graph.

Each cell is a:

Node

and neighboring cells are:

Edges

Example:

1 1

1 0

The three land cells are connected.

Island Definition

Two land cells belong to the same island when they are connected.

Most problems consider:

4-direction connectivity

Meaning movement is allowed:

Up

Down

Left

Right

4-Direction Connectivity

Example:

1 1 0

0 1 0

0 0 1

Connections:

(0,0)

|

(0,1)

|

(1,1)

The last:

(2,2)

is separate.

Number of islands:

2

8-Direction Connectivity

Some problems allow diagonal movement.

Directions:

Up

Down

Left

Right

4 Diagonals

Example:

1 0

0 1

Using 4 directions:

2 islands

Using 8 directions:

1 island

Why Is Count Islands Asked in Interviews?

This problem tests:

1. Graph Thinking

Can you convert:

Matrix

↓

Graph

?

2. Traversal Algorithms

Understanding:

  • DFS
  • BFS

is required.

3. Visited Tracking

Can you avoid processing the same cell multiple times?

4. Problem Transformation

Many real problems are variations:

  • Connected regions
  • Image segmentation
  • Maze solving

Real-World Applications

Image Processing

Images can be represented as:

Pixel Matrix

Example:

1 = Object pixel

0 = Background

Counting connected objects becomes:

Count Islands

Geographic Systems

Maps contain:

Land

Water

Finding separate land masses uses island counting.

Computer Vision

Used for:

  • Object detection
  • Region identification
  • Image segmentation

Network Analysis

A grid can represent:

  • Connected systems
  • Communication networks
  • Components

Problem Statement

Given a matrix:

m × n

where:

1 = land

0 = water

return the number of islands.

Two land cells are connected if they share an edge.

Example 1

Input:

[
[1,1,0],

[1,0,0],

[0,0,1]
]

Output:

2

Example 2

Input:

[
[1,0,1],

[0,1,0],

[1,0,1]
]

Using 4-direction:

Output:

5

Constraints

Example:

1 <= rows <= 500

1 <= columns <= 500

Important Observation

Whenever we find:

land = 1

we found a possible new island.

Steps:

  1. Increase island count.
  2. Visit all connected land cells.
  3. Mark them visited.

Flood Fill Pattern

The Count Islands problem follows the same pattern as:

  • Flood Fill
  • Maze traversal
  • Connected components

Example:

Before DFS:

1 1 0

1 0 0

0 0 1

Start DFS:

(0,0)

Visit:

(0,1)

(1,0)

Mark visited.

Remaining:

0 0 0

0 0 0

0 0 1

Direction Arrays Concept

Instead of writing:

up

down

left

right

separately, use arrays.

Directions:

int[] rowDirection =
{
    -1,
     1,
     0,
     0
};


int[] columnDirection =
{
     0,
     0,
    -1,
     1
};

Movement:

(row + rowDirection[i])

(column + columnDirection[i])

Approach 1 — Brute Force Scanning

The first idea:

For every land cell:

1

check surrounding cells.

Problem:

A large connected island may contain hundreds of cells.

Without traversal:

  • Duplicate counting happens.
  • Same island is processed multiple times.

Therefore:

We need:

DFS

or

BFS

Approach 2 — DFS Traversal Approach

Depth First Search explores all connected land cells.

When DFS finishes:

one complete island is processed.

DFS Algorithm

  1. Traverse every matrix cell.
  2. If cell is land:
count++
  1. Start DFS.
  2. Mark connected cells as visited.

DFS Example

Matrix:

1 1 0

1 0 0

0 0 1

Find:

matrix[0][0] = 1

Count:

islands = 1

DFS visits:

(0,0)

(0,1)

(1,0)

Continue scanning.

Find:

(2,2)

Count:

islands = 2

Java Program — DFS Approach

public class CountIslandsDFS {


    private static final int[] ROWS =
            {-1, 1, 0, 0};


    private static final int[] COLS =
            {0, 0, -1, 1};


    public static int countIslands(
            int[][] grid) {


        int rows =
                grid.length;


        int cols =
                grid[0].length;


        int count = 0;


        for(int i = 0;
            i < rows;
            i++) {


            for(int j = 0;
                j < cols;
                j++) {


                if(grid[i][j] == 1) {


                    count++;


                    dfs(
                        grid,
                        i,
                        j
                    );

                }

            }

        }


        return count;

    }


    private static void dfs(
            int[][] grid,
            int row,
            int col) {


        if(row < 0 ||
           col < 0 ||
           row >= grid.length ||
           col >= grid[0].length ||
           grid[row][col] == 0) {


            return;

        }


        // Mark visited

        grid[row][col] = 0;


        for(int i = 0;
            i < 4;
            i++) {


            dfs(
                grid,
                row + ROWS[i],
                col + COLS[i]
            );

        }

    }

}

Step-by-Step Code Explanation

Input:

1 1 0

1 0 0

0 0 1

Start:

count = 0

Find:

grid[0][0] = 1

Increase:

count = 1

Start DFS.

DFS visits:

(0,0)

(0,1)

(1,0)

Mark them:

0

Remaining:

0 0 0

0 0 0

0 0 1

Find:

(2,2)

Increase:

count = 2

Final answer:

2

Complexity Analysis

For:

m × n

matrix:

Every cell is visited once.

Time:

O(m × n)

DFS recursion stack:

Worst case:

O(m × n)

Space:

O(m × n)

Advantages

  • Simple.
  • Natural graph solution.
  • Easy to extend.
  • Common interview approach.

Drawbacks

  • Recursive stack overflow for very large grids.
  • Modifies original matrix.

Approach 3 — BFS Queue Approach

Breadth First Search (BFS) is another popular solution for the Count Islands problem.

Instead of recursion:

DFS → Stack

BFS uses:

Queue

to explore connected land cells level by level.

BFS Algorithm

  1. Traverse every cell.
  2. When land is found:
count++
  1. Add cell to queue.
  2. Mark it visited.
  3. Remove cells from queue.
  4. Visit all valid neighbors.

BFS Visualization

Matrix:

1 1 0

1 0 0

0 0 1

Start:

(0,0)

Queue:

[(0,0)]

Process:

Visit neighbors:

(0,1)

(1,0)

Queue:

[(0,1),(1,0)]

All connected cells are processed.

Remaining:

0 0 0

0 0 0

0 0 1

Java Program — BFS Approach

import java.util.LinkedList;
import java.util.Queue;

public class CountIslandsBFS {


    private static final int[] ROWS =
            {-1, 1, 0, 0};


    private static final int[] COLS =
            {0, 0, -1, 1};


    public static int countIslands(
            int[][] grid) {


        int rows =
                grid.length;


        int cols =
                grid[0].length;


        int count = 0;


        for(int i = 0;
            i < rows;
            i++) {


            for(int j = 0;
                j < cols;
                j++) {


                if(grid[i][j] == 1) {


                    count++;


                    bfs(
                        grid,
                        i,
                        j
                    );

                }

            }

        }


        return count;

    }


    private static void bfs(
            int[][] grid,
            int row,
            int col) {


        Queue<int[]> queue =
                new LinkedList<>();


        queue.offer(
                new int[]{row,col});


        grid[row][col] = 0;


        while(!queue.isEmpty()) {


            int[] current =
                    queue.poll();


            int currentRow =
                    current[0];


            int currentCol =
                    current[1];


            for(int i = 0;
                i < 4;
                i++) {


                int newRow =
                    currentRow + ROWS[i];


                int newCol =
                    currentCol + COLS[i];


                if(newRow >= 0 &&
                   newCol >= 0 &&
                   newRow < grid.length &&
                   newCol < grid[0].length &&
                   grid[newRow][newCol] == 1) {


                    queue.offer(
                        new int[]{
                            newRow,
                            newCol
                        });


                    grid[newRow][newCol] = 0;

                }

            }

        }

    }

}

DFS vs BFS Comparison

Feature DFS BFS
Data Structure Stack / Recursion Queue
Traversal Depth first Level first
Memory Recursive stack Queue
Implementation Shorter More explicit
Large grids Possible stack overflow Safer

Approach 4 — In-Place DFS Optimization

The previous DFS solution uses the original matrix as a visited tracker.

Example:

Original:

1 1 0

1 0 0

0 0 1

After visiting:

0 0 0

0 0 0

0 0 1

This avoids creating:

boolean visited[][]

Alternative Using Visited Matrix

Some developers prefer keeping the original grid unchanged.

Create:

boolean[][] visited;

Example:

Grid:

1 1 0

1 0 0

0 0 1

Visited:

false false false

false false false

false false false

When visited:

true

Java Program — DFS With Visited Matrix

public class CountIslandsVisited {


    private static final int[] ROWS =
            {-1,1,0,0};


    private static final int[] COLS =
            {0,0,-1,1};


    public static int count(
            int[][] grid) {


        int rows =
                grid.length;


        int cols =
                grid[0].length;


        boolean[][] visited =
                new boolean[rows][cols];


        int islands = 0;


        for(int i = 0;
            i < rows;
            i++) {


            for(int j = 0;
                j < cols;
                j++) {


                if(grid[i][j] == 1 &&
                   !visited[i][j]) {


                    islands++;


                    dfs(
                        grid,
                        visited,
                        i,
                        j
                    );

                }

            }

        }


        return islands;

    }


    private static void dfs(
            int[][] grid,
            boolean[][] visited,
            int row,
            int col) {


        if(row < 0 ||
           col < 0 ||
           row >= grid.length ||
           col >= grid[0].length ||
           grid[row][col] == 0 ||
           visited[row][col]) {


            return;

        }


        visited[row][col] = true;


        for(int i = 0;
            i < 4;
            i++) {


            dfs(
                grid,
                visited,
                row + ROWS[i],
                col + COLS[i]
            );

        }

    }

}

Complexity Analysis

For:

m × n

matrix:

Time:

O(m × n)

Space:

Visited matrix:

O(m × n)

DFS stack:

O(m × n)

Approach 5 — Union Find (Disjoint Set Union)

Another graph-based solution is:

Union Find

Concept

Each land cell is treated as a node.

Initially:

Every land cell = separate island

When two land cells are connected:

Union them

Example:

1 1 0

1 0 0

0 0 1

Initially:

3 land groups

After union:

2 islands

Union Find Operations

Find

Determine parent group:

find(x)

Union

Merge two groups:

union(a,b)

Union Find Benefits

Useful when:

  • Dynamic connections change.
  • Many connectivity queries exist.

Union Find Drawbacks

For a single island count:

DFS/BFS is simpler.

Recursive DFS vs Iterative DFS

Recursive DFS

Advantages:

  • Clean code.
  • Easy to understand.

Disadvantage:

  • Stack overflow risk.

Iterative DFS

Uses:

Stack<int[]>

Advantages:

  • No recursion limit.
  • Better for huge grids.

Java Streams Approach

Streams are not recommended for Count Islands.

Reason:

The algorithm requires:

  • State tracking.
  • Visited management.
  • Graph traversal.

Example:

Arrays.stream(grid)

only processes rows.

It cannot naturally represent:

DFS/BFS traversal

Comparison of All Approaches

Approach Time Space Recommendation
DFS Modify Grid O(m×n) O(m×n) recursion Most common
BFS Queue O(m×n) O(m×n) Safe for large grids
DFS + Visited O(m×n) O(m×n) Preserves input
Union Find O(m×n) O(m×n) Dynamic connectivity

Direction Arrays Concept

Instead of writing:

row - 1

row + 1

col - 1

col + 1

use:

int[] dr =
{-1,1,0,0};


int[] dc =
{0,0,-1,1};

Movement:

newRow = row + dr[i]

newColumn = column + dc[i]

Primitive vs Object Arrays

Primitive Grid

int[][]

Advantages:

  • Faster.
  • Less memory.
  • Better cache usage.

Object Grid

Integer[][]

Advantages:

  • Supports null values.

Disadvantages:

  • More memory.
  • Boxing overhead.

Common Interview Mistakes

Mistake 1

Counting every land cell.

Wrong:

Number of 1s

Correct:

Number of connected groups

Mistake 2

Not marking visited.

Problem:

Infinite traversal.

Mistake 3

Ignoring diagonal rules.

Always confirm:

4-direction

or

8-direction

Mistake 4

Changing grid without permission.

Some problems require original matrix preservation.

Edge Cases

Input Output
Empty matrix 0
All water 0
All land 1
Single cell land 1
Single cell water 0
Diagonal cells only Depends on connectivity

Interview Follow-up Questions

Q1. Count islands using DFS.

Q2. Count islands using BFS.

Q3. Find largest island size.

Q4. Find island perimeter.

Q5. Number of closed islands.

Q6. Number of distinct islands.

Q7. Convert all connected land to water.

Q8. Use Union Find for connectivity.

Related Problems

  • Flood Fill
  • Number of Provinces
  • Surrounded Regions
  • Rotting Oranges
  • Island Perimeter
  • Max Area of Island
  • Shortest Path in Grid

Key Takeaways

Count Islands is a classic:

Matrix → Graph

conversion problem.

The main pattern:

Find unvisited land

↓

Increase count

↓

Traverse connected cells

↓

Mark visited

Best interview approaches:

DFS

or

BFS

Complexity:

Time: O(m × n)

Space: O(m × n)

Frequently Asked Interview Questions

Q1. Why count increases only when land is found?

Because every DFS/BFS marks the complete island.

Q2. Why mark visited?

To avoid counting the same island again.

Q3. DFS or BFS which is better?

Both have the same complexity.

Choice depends on:

  • Stack limits.
  • Implementation preference.

Q4. Can diagonal cells be connected?

Only if the problem specifies 8-direction movement.

Interview Tip

When asked:

"Count islands in a matrix."

Explain:

  1. Treat matrix as a graph.
  2. Find unvisited land.
  3. Start DFS/BFS.
  4. Mark connected cells.
  5. Increment island count.

For senior interviews, discuss:

  • Flood fill pattern.
  • Direction arrays.
  • Union Find.
  • Large grid optimization.

This demonstrates strong understanding of graph traversal and matrix algorithms.