Skip to main content

< Back to Data Structures and Algorithms

Graph Algorithms · Grids

Minimum Island

The size of a grid's smallest island, measuring each as it's explored and keeping the least.

Step through it

Examples
Edge cases
grid
WLWWWWLWWWWWWLWWWLLWLWWLLLLWWW

Step 0 of 61

Output

Running… play or step to the end.

The code

/* Finds the number of islands that exist within a grid.
 * @param {array[][]} grid // a 2d array of land/water tiles.
 * @returns {int} // The minimum size island within the grid.
 */
const minimumIsland = grid => {
  // Keeps track of every visited tile within the grid.
  const visited = new Set()
  /* Keeps track of the size of the smallest island found.
     Initialise to Infinity to ensure all found islands are smaller */
  let minSize = Infinity

  // O(n) loop over every row within the grid.
  for (let row=0; row < grid.length; row++) {
      // O(n) loop over every column within the grid
    for (let col=0; col < grid[row].length; col++) {
      // Find the size of the island present at the given tile.
      const size = exploreSize(grid, row, col, visited)

      // Size greater than 0 if a new island is found and traversed.
      // Size less than minSize means we found a new smaller island.
      if (size > 0 && size < minSize) {
        // Set the new smallest size.
        minSize = size
      }
    }
  }

  // Traversed the entire grid. Return the size of the smallest island.
  return minSize
}

/* Explores a tile within the 2d grid.
 * If the tile is part of a new island, explore the island and return its size.
 * @param {array[][]} grid // a 2d array of land/water tiles.
 * @param {int} row // The current row we're looking at.
 * @param {int} col // The current column we're looking at.
 * @param {Set} visited // Keeps track of previously visited tiles.
 * @returns {int} // The size of the island
 */
const exploreSize = (grid, row, col, visited) => {
  // Row or column is out of bounds, no new land found.
  const rowInBounds = 0 <= row && row < grid.length
  const colInBounds = 0 <= col && col < grid[0].length
  if (!rowInBounds || !colInBounds) return 0

  // Tile is water, no new land found.
  if (grid[row][col] === 'W') return 0

  // Tile has already been explored, no new land found.
  const pos = `${row},${col}`
  if (visited.has(pos)) return 0

  /* New land found! */

  // Mark the tile as visited.
  visited.add(pos)

  // Initialise the size of the island to 1.
  let size = 1

  // Explore the adjacent tiles of the island and increment the island size
  size += exploreSize(grid, row-1, col, visited) // Look up
  size += exploreSize(grid, row+1, col, visited) // Look down
  size += exploreSize(grid, row, col-1, visited) // Look left
  size += exploreSize(grid, row, col+1, visited) // Look right

  // Island explored. Return its size.
  return size
}

// A 2d array representing a grid of land (L) and water (W) tiles.
const grid = [
  ['W', 'L', 'W', 'W', 'W'],
  ['W', 'L', 'W', 'W', 'W'],
  ['W', 'W', 'W', 'L', 'W'],
  ['W', 'W', 'L', 'L', 'W'],
  ['L', 'W', 'W', 'L', 'L'],
  ['L', 'L', 'W', 'W', 'W'],
]

minimumIsland(grid)

The original on GitHub (opens in a new tab)