Graphs Islands (Matrix Traversal) problems involve processing a 2D grid (matrix) to identify and often count or analyze connected components, typically referred to as “islands” (land) surrounded by “water.” These problems are a common application of graph traversal algorithms like Breadth-First Search (BFS) or Depth-First Search (DFS) in a grid context.

Core Idea:

  1. Grid Representation: The input is usually a 2D matrix where cells have specific values (e.g., ‘1’ for land, ‘0’ for water, or other characters/numbers representing different states).
  2. Connectivity: “Islands” are formed by connecting adjacent “land” cells, typically horizontally and/or vertically. Diagonal connections might be allowed depending on the problem statement.
  3. Traversal: The primary goal is to traverse the grid, identify distinct islands, and perform some operation on them (e.g., count them, find the largest, calculate perimeter).

Common Scenarios & How it Works:

  1. Iterate and Explore:
    • The most common approach involves iterating through each cell of the matrix.
    • If a “land” cell is encountered that hasn’t been visited yet (or isn’t part of an already processed island):
      • It marks the beginning of a new island.
      • A traversal algorithm (DFS or BFS) is initiated from this cell to find all connected land cells belonging to this island.
      • Visited cells are marked (e.g., changing their value, using an auxiliary visited matrix) to avoid reprocessing and double-counting.
  2. Depth-First Search (DFS):
    • Recursively explores an island. From a land cell, it visits its unvisited land neighbors (up, down, left, right).
    • The recursion continues until all cells in the current island are visited.
    • A separate visited set/matrix or modifying the input grid in-place (e.g., changing ‘1’ to ‘0’ or to a new marker) is crucial.
  3. Breadth-First Search (BFS):
    • Uses a queue to explore an island level by level.
    • Starting from a land cell, its unvisited land neighbors are added to the queue.
    • Cells are processed from the queue, and their neighbors are added, until all cells in the island are visited.
    • Similarly, requires a mechanism to track visited cells.

Key Techniques & Variations:

  1. Counting Islands (e.g., LeetCode #200): The most basic version. Increment a counter each time a new, unvisited land cell is found and its entire island is explored.
  2. Max Area of Island (e.g., LeetCode #695): During the traversal (DFS/BFS) of each island, count the number of cells (area). Keep track of the maximum area found.
  3. Number of Distinct Islands (e.g., LeetCode #694 - Premium): Requires serializing the shape of each island (e.g., by storing relative coordinates of its cells from a starting point) and using a set to count unique shapes.
  4. Island Perimeter (e.g., LeetCode #463): For each land cell, count how many of its four sides are adjacent to water or the grid boundary.
  5. Surrounded Regions / Enclaves (e.g., LeetCode #130, #1020): Identify regions of ‘O’s (or land) that are completely surrounded by ‘X’s (or water) and cannot reach the boundary of the grid. Often involves starting traversals from boundary land cells and marking reachable land; any remaining land cells are surrounded.
  6. Flood Fill (e.g., LeetCode #733): Starting from a given cell, change its color and the color of all connected cells of the same original color to a new color. This is a direct application of DFS/BFS.
  7. Rotting Oranges (e.g., LeetCode #994): A multi-source BFS problem where fresh oranges rot over time if adjacent to a rotten orange. The goal is to find the minimum time for all fresh oranges to rot.

Advantages of Standard Traversal Approaches (DFS/BFS):

  • Systematic Exploration: Both DFS and BFS ensure that all parts of an island are visited systematically.
  • Completeness: Guaranteed to find all cells belonging to an island once a part of it is discovered.
  • Avoiding Double Counting: By marking cells as visited (either by modifying the grid or using an auxiliary data structure), each land cell is processed as part of only one island.
  • Adaptability: Easily adaptable to variations like finding area, perimeter, or specific properties of islands.

When to Use Matrix Traversal for “Island” Problems:

  • When the input is a 2D grid representing some form of segments or regions.
  • When you need to find connected components based on adjacency (horizontal/vertical, sometimes diagonal).
  • Problems involving counting, measuring (area, perimeter), or transforming these connected components.
  • When the state of a cell can change based on its neighbors (e.g., flood fill, rotting oranges).

Example LeetCode Problems:

  1. (#200) Number of Islands
  2. (#695) Max Area of Island
  3. (#463) Island Perimeter
  4. (#130) Surrounded Regions
  5. (#733) Flood Fill
  6. (#1020) Number of Enclaves
  7. (#994) Rotting Oranges (Often categorized as graph BFS, but on a grid)
  8. (#694) Number of Distinct Islands (Premium)
  9. (#827) Making A Large Island (More complex variation)