Islands

The “Islands” coding pattern, often referred to as the “Connected Components” pattern, is a common technique used in graph-related problems to identify and count groups of connected elements in a matrix or graph. It’s particularly useful for solving problems where you need to find clusters, islands, or connected components.

Here’s a brief explanation of the Islands coding pattern:

1. Iterate Through Elements: Traverse through the given matrix or graph, considering each element.
2. Identify Starting Points: When you encounter an element that belongs to a group (e.g., ‘1’ in a matrix representing land), treat it as a starting point for an island or connected component.
3. Explore Neighbors: Use Depth-First Search (DFS) or Breadth-First Search (BFS) to explore all the connected elements from the starting point. Mark the visited elements to avoid revisiting them.
4. Count or Process: Depending on the problem, you might need to count the islands, find the size of each connected component, determine the perimeter, etc.

This pattern is often used to solve problems related to counting islands in a 2D grid, finding the size of connected components in a graph, determining if there’s a path between two elements, and other similar tasks.

The key concept is to traverse through the matrix or graph, identify starting points (elements that belong to a group), and then perform graph traversal to explore all connected elements. The DFS or BFS traversal helps you find the entire connected component associated with each starting point.

In summary, the Islands coding pattern involves identifying groups of connected elements in a matrix or graph using techniques like Depth-First Search or Breadth-First Search. It’s useful for solving problems that require finding clusters, islands, or connected components.

• Flood Fill
  Given an image represented by a 2D matrix of integers, an initial pixel, and a new color, implement the flood fill algorithm to change all connected pixels with the initial color to the new color.
• Number of Islands
  Given a 2D grid of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
• Surrounded Regions
  Given a 2D board containing ‘X’ (representing walls) and ‘O’ (representing open spaces), capture all regions surrounded by ‘X’. A region is considered surrounded if all its adjacent cells (top, bottom, left, and right) are walls or are out of bounds.
• Walls and Gates
  You are given a 2D grid representing a house, with rooms labeled as ‘INF’ for empty rooms, -1 for walls, and 0 for gates. You need to fill each empty room with the distance to the nearest gate. If it is impossible to reach a gate, leave the room labeled as ‘INF’.
• Find All Groups of Farmland
  You are given a 2D grid representing a piece of farmland, where the value 1 represents cultivated land and 0 represents uncultivated land. A group of farmland is a connected region of cultivated land, where a cell is considered connected to its adjacent cells horizontally and vertically. You need to find all groups of farmland and return their coordinates as a list of 4-element arrays.
• Count Sub Islands
  You are given two 2D grids, grid1 and grid2, both representing islands, where grid1 represents the original island and grid2 represents a sub-island formed by cutting out a rectangle from grid1. The values 1 in the grids represent land, and 0 represents water.
• Minesweeper
  You are given a 2D grid representing a Minesweeper game. You need to reveal the cells of the grid according to the following rules: