Number of Distinct Islands
BFS & DFS Problems DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Number of Islands in a Grid (Connected Components using Graph Traversal), Connected Components, Graph Traversal, Breadth-First Search, Queue, Matrices, Two-dimensional Array Traversal, Time Complexity, Space Complexity, matrix representation, graph components, visited tracking, dfs, graph traversal, queue, bfs.
Given a grid of size NxM (N is the number of rows and M is the number of columns in the grid) consisting of '0's (Water) and '1's(Land). Find the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically or diagonally i.e., in all 8 directions. Input Specification: A grid of characters '0' and '1'. Output Specification: Return an integer representing the number of islands. Sample Test Cases: Example 1: Input: [Not explicitly provided in the source content] Output: 3 Explanation: There are 3 islands as the different components are surrounded by water (i.e. 0), and there is no land connectivity in either of the 8 directions hence separating them into 3 islands. Example 2: Input: [Not explicitly provided in the source content] Output: 1 Explanation: All lands are connected. So, only 1 island is present.