LeetCode - Number of Islands BFS Solution

Hello Code Recipian! Welcome back to another leetcode problem solutions article. In our previous article we discussed the depth first search solution for leetcode problem no.200, Number of Islands. Today let's see how we can solve the same problem using the bread first search (BFS) technique.

Problem Statement: Number of Islands

Given a m x n 2D binary array grid which represents of map of '1's (land) and '0's (water), return the number of islands in this grid.

An island is formed by connecting adjacent lands vertically or horizontally and it should be surrounded by water. You may assume all four edges of the grid are all surrounded by water.

Example 1

Input: grid =

Output: 1

Explanation: The matrix has only one island. See the highlighted cells below.

Example 2

Input: grid =

Output: 3

Explanation: The matrix has three islands. See the highlighted cells below.

Constraints:

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 300

• grid[i][j] is '0' or '1'.

Solution

If you have not yet gone through our previous article on DFS solution, we highly recommend to you to check that out first because, it will provide you with key insights which will help you understand this problem better.

Tip: DFS solutions are typically implemented using stack data structure or recursion. BFS solutions mostly involve the use of queue data structure.

Algorithm

Below is a step-by-step explanation for the working of the algorithm:

1. Initialization:

   To begin with, we initialize 3 variables: rows, cols and islandCount.

   1. rows represents the total number of rows in grid matrix.

   2. cols represents the total number of columns in grid matrix.

   3. islandCount is used to store the result, total number of islands in grid matrix.

2. Iterate through the matrix elements to find land cells:

   Traverse through each element in the input grid matrix. In each iteration perform the following steps:

   1. If the current cell is a water cell, ignore. Continue iteration.

   2. If the current cell is a land cell:

      1. Increment islandCount since we have found a island.

      2. Call the BFS function (defined in step 3).

3. BFS function:

   The BFS function will be called from step 2 with the coordinates (row,col) of the land cell. For each call, the BFS function does the following things, as long as the current cell is in bounds and is a land cell:

   1. Initially add coordinates (row,col) to queue.

   2. Next, de-queue the front element from queue.

   3. Mark the current cell as processed by making it 0.

   4. Add all current cell neighbours (vertically and horizontally) to the queue.

   5. Repeat steps b, c & d until the queue becomes empty.

4. Repeat island counting steps:

   Repeat steps 2-3 for all land cells in the given input grid.

5. Return final result:

   Finally, return the result islandCount, after all the cells in the input matrix are processed.

Simulation

Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses:

1. Udemy Video Tutorials - Available at 95% off

2. System Design Interview Complete Guide

3. Cracking The Coding Interview - Most Preferred Book For Coding Interviews

4. Data Structures And Algorithms - A Complete Guide 

5. Learn In-Demand Tech Skills And Stay Ahead Of Others

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

C Solution

Rust Solution

Complexity Analysis

Time Complexity

Grid Traversal:

The nested loop iterates over all elements of the input 2D array once, this results in a time complexity of O(rows x cols).

BFS Function:

The BFS function also process each element in the input array at most once, so time complexity is O(rows x cols).

Therefore the overall time complexity of this algorithm is O(rows x cols).

Space Complexity

The space complexity is dependent on the queue used. In the worst case when all cells in grid are land cells, the queue can grow upto min(rows, cols). Thus the space complexity of this solution is O(min(rows, cols)).

That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries.

If you enjoyed this article, please subscribe to our website and Youtube channel. Your support inspires us to create more such articles in the future.

Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there!

Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.

Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.