LeetCode - Number of Islands Fastest Solution

Hello Code Recipian! Welcome back to another article on leetcode problem solutions. Today we will be solving leetcode problem no. 200, Number of Islands. This problem also features in GeeksForGeeks, Number of Islands.

Problem Statement: Number of Islands

Given a 2D m x n array (matrix) grid containing only 1s (land) and 0s (water), count the number of islands in it.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically (not diagonally). You may assume all four edges of the grid are all surrounded by water.

Example 1

Input: grid =

Output: 3

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

Example 2

Input: grid =

Output: 1

Explanation: The matrix has only one island. 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

Questions on island pattern are a popular choice in coding interviews. We can solve these problems efficiently using both depth first search (DFS) or breadth first search (BFS) approaches. We have explained the BFS approach in detail in another article. In this article we will be discussing the DFS solution.

The idea behind DFS approach is that, as soon as we find a land cell, we go to the depth, find all the connected land cells (vertically and diagonally) and count the number of islands.

Algorithm

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

1. Initialization:

   Initialize 3 variables: row, col and count.

   1. row represents the no. of rows in the input matrix.

   2. col represents the no. of columns in the input matrix.

   3. count represent our result, count of no. of islands.

2. Find a land cell or 1:

   The first step in this algorithm is to find a land cell. Starting from the (0,0) position, we start iterating through the given 2D array until we find a land cell. Each time we find a land cell, we call the DFS function and perform a recursive DFS from this land cell, to find all the land cells connected to it, vertically and horizontally.

3. Depth first search:

   For each call (in step 2) the DFS function does the following things:

   1. Check if our DFS function is within the bounds of the given 2D array. If it is not in bounds, we simply return from recursion stack.

   2. Check if the current cell is a land. Since we want to count islands we must only process land cells. If we encounter a water cell, we return from recursion stack.

   3. Next, if the current cell is a land, we mark the current cell as processed, by making it 0. This step is important and is needed to prevent recounting already processed islands.

   4. After this we recursively call the DFS function in all 4 directions (right, down, left and up) and repeat steps a-d until there are no more connected land cells left to be processed.

4. Increment island count:

   Once the control returns to the main caller in step 2, we increment the count by one, since we have processed one island (set of connected land cells).

5. Repeat island counting steps:

   Repeat steps 2-4 for all the land cells in the given 2D array.

6. Return final result:

   Finally, return the result count after all land cells in the input array are processed.

Note: The above algorithm modifies the input array to arrive at the result. If the interviewer asks you to do this without modifying the input array, you can easily modify the above algorithm by taking a boolean hashmap to keep track of the processed elements instead of modifying the given input array.

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

Nested Loop:

The nested loop is used for iterating through all elements of the input 2D array exactly once. Hence, the time complexity is O(row x col), where row and col represents number of rows and columns in grid respectively.

DFS Function:

The DFS function also processes each element at most once. Hence, the time complexity of the DFS function is also O(row x col).

Therefore the overall time complexity of the algorithm is O(row x col).

Space Complexity

The worst case space complexity of the algorithm is O(row x col) because of the recursion call stack. The worst case occurs when all the elements of the given input array are 1s.

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.