Number of Islands - Python Solution

1. Introduction

"Number of Islands" is a classic problem in computer science, often used to teach concepts of graph traversal and depth-first search (DFS). The problem involves identifying distinct islands in a grid, where an island is formed by adjacent '1's (land) and surrounded by '0's (water). This problem is essential for understanding how to navigate and process grid-based data structures.

Problem

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), the objective is to return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

2. Solution Steps

1. Initialize a count of islands to 0.

2. Iterate over each cell of the grid.

3. When a cell with '1' (land) is found, increment the island count and initiate a DFS to mark all adjacent lands.

4. In DFS, mark the current land as visited (e.g., set to '0') and recursively call DFS for all adjacent lands (up, down, left, right).

5. Continue the process until all cells in the grid have been checked.

6. Return the total count of islands.

3. Code Program

def numIslands(grid):
    if not grid:
        return 0

    def dfs(i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == '0':
            return
        grid[i][j] = '0'
        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)

    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1

    return count

# Example Usage
print(numIslands([["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]))
print(numIslands([["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]))

Output:

1
3

Explanation:

1. Depth-First Search (DFS): DFS is used to traverse and mark all the lands that are part of the same island.

2. Island Counting: Each time an unvisited land ('1') is found, the island count is incremented and DFS is initiated from that cell.

3. Marking Visited: During DFS, each visited land cell is marked as '0' to avoid revisiting it.

4. Adjacent Land Exploration: DFS explores all adjacent lands (up, down, left, right) that are part of the same island.

5. Comprehensive Exploration: The entire grid is explored, and each group of connected lands is counted as an island.

6. Total Islands: The function returns the total number of islands found in the grid.


Related Python Source Code Examples:

Python string literals Python string length example Python String join() method example Python string split() method example Python String index() method example Python string find() method example Python string startswith() method example Python string endswith() method example Python String lower() method example Python String upper() method example Python string title() method example Python string capitalize() method example Python string islower() method example Python string istitle() method example Python string isupper() method example Python string swapcase() method example Python string strip() method example Python string replace() method example Python string isdigit() method example Python string isdecimal() method example Python string isnumeric() method example Python string isalpha() method example Python string isalnum() method example Write a python program to concatenate strings in different ways Python program to create a new string by appending s2 in the middle of s1 Split a given string on asterisk into several substrings and display each substring in Python Write a Python program to count all lower case, upper case, digits, and special symbols from a given string Write a python program to return a string such that the string is arranged from lowercase letters and then uppercase letters Write a Python Class to Reverse a String Word by Word Write a python class to implement pow(x, n) Write a python class to convert an integer to a Roman numeral Write a python program to find the factorial of a number using recursion Write a Python program to convert temperature in Celsius to Fahrenheit Write a Python program to find the largest number among the three input numbers Write a Python program to print only even numbers using the function Write a python program to filter integer, float, string from a list Write a python program to check whether the given number is greater than 50 and also divisible by 2 using nested if else Write a python program to demonstrate a simple class creation Write a python program to demonstrate the object as an argument Write a python program to demonstrate an object as an argument with default values Write a python program to demonstrate method overriding Write a Python program for Linear Search and Binary Search Python list - insert, remove, append, len, pop and clear example Write a python program to add two numbers Write a python program to get the python version Write a python program to check whether the first and last letters of the given word is vowel or not ? Write a python program to count the number of digits Write a python program to filter integer, float, string from a list Write a python program to find the average of 10 numbers Write a python program to traverse a list and print the values in it Write a python program to print first 20 natural numbers using while loop Write a python program to print the square of all numbers from 1 to 10 Write a python program to get the sum of digits Write a python program to print right angle triangle pattern using * Write a python program to remove vowels in a word Write a python program to find absolute value using function Wrtie a python program to demonstrate the use of variable length arguments Write a python program to demonstrate the use of default arguments Write a python program to demonstrate the use of keyword arguments Write a python program to print a simple list using functions Write a python program to find the max values in a list using function Given a string of odd length greater 7, return a string made of the middle three chars of a given String Arrange string characters such that lowercase letters should come first Write a Python program to Count all lower case, upper case, digits, and special symbols from a given string Write a Python program to Find all occurrences in a given string ignoring the case Given an input string, count occurrences of all characters within a string and return the details as dictionary Write a Python program to Split a given string on asterisk into several substrings and display each substring Write a Python program to Check whether the given string startswith 'h' Write a python program to concatenate strings in different ways Write a python program to return a string such that the string is arranged from lowercase letters and then uppercase letters Write a python program to repeat a givent string multiple times Write a python program to create a simple list and nested list with different datatypes Write a python program to add elements to an existing list from user input Write a python program to reverse a given list Write a python program to convert a list to tuple using tuple function Write a python program to check whether the user given input is equal to the current working directory or not Write a Python program for Linear Search and Binary Search Selection Sort Algorithm in Python Bubble Sort Algorithm in Python Bogo Sort Algorithm in Python Bucket Sort Algorithm in Python Comb Sort Algorithm in Python Counting Sort Algorithm in Python Heap Sort Algorithm in Python Insertion Sort Algorithm in Python Merge Sort Algorithm in Python Quick Sort Algorithm in Python Shell Sort Algorithm in Python Interpolation Search Algorithm in Python Stack Implementation in Python Queue Implementation in Python Deque Implementation in Python Singly Linked List Implementation in Python Doubly Linked List Implementation in Python Circular Linked List Implementation in Python PriorityQueue Implementation in Python Circular Queue Implementation in Python Binary Search Tree Implementation in Python Stack Implementation Using Linked List in Python Stack Implementation Using Doubly Linked List in Python Python - Convert Binary to Decimal Example Python - Convert Binary to Hexadecimal Example Python - Convert Binary to Octal Example Python - Convert Decimal to Binary Example Python - Convert Decimal to Octal Example Python Convert String to Int Python Convert String to DateTime Python Convert String to Date Python Convert String to JSON Python Convert String to Number Python Convert String to List Python Convert String to Float Python Convert String to Bytes Python Convert List to String Python Convert List to Set Python Convert List to Dictionary Python Convert List to Tuple Python Convert List to JSON Python Convert List to Array Python Convert List to String With Commas Python Convert List to Dataframe Python Convert Set to List Python Convert Set to String Python Convert Set to Tuple Python Convert Set to Dictionary Python Convert Set to JSON Python Convert Set to Comma Separated String Python Convert Dictionary to JSON Python Convert Dictionary to Dataframe Python Convert Dictionary to String Python Convert Dictionary to List Python Convert Dictionary Keys to List Python Convert Dictionary Values to List Python Convert Dictionary to Tuple Python Convert Array to String Python Convert Array to String With Commas Python Convert Array to List Python Convert Array to Set Python Convert Array to JSON Python Convert Array to Dictionary Python Convert Array to Tuple Python Convert Int to String Python Convert Int to Binary Python Convert Int to Float Python Convert Date to String Python Convert Date to Epoch Python Convert Date to Unix Timestamp Python Convert Date to DateTime Python Convert Date to DateTime Python Convert Date to Timestamp Python Convert Date String to DateTime Python Convert Date String to Epoch Python Convert Tuple to String Python Convert Tuple to List Python Convert Tuple to Dictionary Python Convert Tuple to Comma Separated String Python Convert Tuple to Array Python Convert Tuple to JSON Python Convert JSON to String Python Convert JSON to Dictionary Python Convert JSON to Array Python Convert JSON to XML Python Convert JSON to List

Comments

Post a Comment