About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Count Islands Problem

Given a two-dimensional boolean matrix, find the number of islands.

An island is a group of connected 1s or a standalone 1. A cell in the matrix can be connected to up to 8 neighbors: 2 vertical, 2 horizontal and 4 diagonal.

Example

Input:

[

[1, 1, 0, 0, 0],

[0, 1, 0, 0, 1],

[1, 0, 0, 1, 1],

[0, 0, 0, 0, 0],

[1, 0, 1, 0, 1]

]

Output: 5

(0 0), (0 1), (1 1) and (2 0) make an island.

(1 4), (2 4) and (2 3) make an island.

(4 0) makes an island.

(4 2) makes an island.

(4 4) makes an island.

Notes

Input Format: Function has one argument, a two-dimensional integer matrix. All the values in the matrix are either 0 or 1.

Output Format: Return an integer, the number of islands of 1s.

Constraints:

  • 1 <= rows <= 450
  • 1 <= columns <= 450
  • Values in the matrix are either 0 or 1.

 Use as little extra memory as possible

Solve the problem without allocating a “visited” matrix.

Solution

Below are the 2 solutions

1. other_solution.cpp

The problem is easy but there is one very important thing to learn. We recommend reading through the whole editorial even if your solution passed all tests.

Treat the matrix like a graph and do a simple DFS (see other_solution.cpp) or BFS (see optimal_solution.cpp).

We are not allowed to use a “visited” matrix, but we can modify the input matrix itself! When a node is visited, change its value from 1 to 0.

Time Complexity:

Time complexity of BFS or DFS is O(V + E), in our case it will be O(n * m + 8 * n * m) that is O(n * m).

Auxiliary Space Used:

O(n * m) for the DFS solution, other_solution.cpp. The space is used by the call stack because the solution is recursive. If we had used an iterative DFS implementation, we would use a stack and same O(n * m) auxiliary space for that.

Consider the worst case for DFS:

9

10

1 1 1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0 0 1

1 1 1 1 1 1 1 1 0 1

1 0 0 0 0 0 0 1 0 1

1 0 1 1 1 1 0 1 0 1

1 0 1 0 0 0 0 1 0 1

1 0 1 1 1 1 1 1 0 1

1 0 0 0 0 0 0 0 0 1

1 1 1 1 1 1 1 1 1 1


// -------- START --------

// All 8 directions. Consider as pair: {add_r[i], add_r[i]}.
const int add_r[8] = {0, -1, -1, -1, 0, 1, 1, 1};
const int add_c[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

/*
Note that we are passing matrix by reference. Passing by value will not work because we are doing 
modifications in matrix. So either pass by reference or use global variable.  
*/
void dfs(int r, int c, vector> &matrix)	
{
	matrix[r][c] = 0;
	for (int i = 0; i < 8; i++)
	{
		// Try to visit all 8 neighbours. 
		int new_r = r + add_r[i];
		int new_c = c + add_c[i];

		// Out of the matrix. 
		if (new_r < 0 || new_r >= matrix.size() || new_c < 0 || new_c >= matrix[0].size())
		{
			continue;
		}

		if (matrix[new_r][new_c])
		{
			dfs(new_r, new_c, matrix);
		}
	}
}

int count_islands(vector> matrix)
{
	int islands = 0;
	int n = matrix.size();
	int m = matrix[0].size();

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			// When we find unvisited node, visit it and visit all the reachable nodes. 
			if (matrix[i][j])
			{
				islands++;
				dfs(i, j, matrix);
			}
		}
	}
	return islands;
}

// -------- END --------

2. optimal_solution.cpp

DFS would make up to almost (n * m) / 2 nested recursive calls; that takes O(n * m) space.

BFS solution (optimal_solution.cpp), on the other hand, uses just O(max(n, m)) of auxiliary space.

Consider the worst case for BFS:

10

10

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

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

At some point of time all the nodes of the last row and last column will be in the queue. The queue will then take O(n+m) = O(max(n, m)) space.

This difference in used space between the two algorithms can affect performance in some real life cases.

Space Complexity:

O(n * m) due to input size and auxiliary space used.


// -------- START --------

// All 8 directions. Consider as pair: {add_r[i], add_r[i]}.
const int add_r[8] = {0, -1, -1, -1, 0, 1, 1, 1};
const int add_c[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

void bfs(int r, int c, vector> &matrix)
{
	queue> q;
	q.push({r, c});
	matrix[r][c] = 0;
	while (q.empty() == false)
	{
		pair head = q.front();
		q.pop();
		int r = head.first;
		int c = head.second;
	
		for (int i = 0; i < 8; i++)
		{
			// Try to visit all 8 neighbours.
			int new_r = r + add_r[i];
			int new_c = c + add_c[i];

			// Out of the matrix. 
			if (new_r < 0 || new_r >= matrix.size() || new_c < 0 || new_c >= matrix[0].size())
			{
				continue;
			}

			if (matrix[new_r][new_c])
			{
				/*
				We could have marked as 0 when we pop-up the element from the queue and not here. 
				This will also give correct answer, but that is not the correct way! If we do 
				that, same element will be pushed multiple times in the queue (that will increase 
				running time and queue size unnecessarily)! Take some examples and try to figure 
				it out. 
				*/
				matrix[new_r][new_c] = 0;
				q.push({new_r, new_c});
			}
		}
	}
}

int count_islands(vector> matrix)
{
	int islands = 0;
	int n = matrix.size();
	int m = matrix[0].size();

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			// When we find unvisited node, visit it and visit all the reachable nodes. 
			if (matrix[i][j])
			{
				islands++;
				bfs(i, j, matrix);
			}
		}
	}
	return islands;
}

// -------- END --------


Attend our Free Webinar on How to Nail Your Next Technical Interview

Recommended Posts

All Posts