Number of islands

You're 30 minutes into a Meta onsite when the interviewer pulls up a grid on the screen. "Imagine you're looking at a satellite image of an ocean. Some cells are land, others are water. How would you count the number of separate land masses?" This is Number of Islands, also known as "Number of Islands" on LeetCode and the Blind 75, and it ranks among the most frequently asked medium-difficulty questions at Amazon, Microsoft, and Meta. It tests whether you can translate a visual grid problem into a graph traversal algorithm, specifically depth-first search.

TL;DR

Scan the grid cell by cell. When you find an unvisited land cell, trigger a DFS that flood-fills the entire connected island by marking all reachable land cells as visited. Increment the island counter each time you start a new DFS. This runs in O(m * n) time and space, where m and n are the grid dimensions. The core insight is that each DFS call discovers exactly one complete island, so the number of DFS calls equals the number of islands.

Why This Problem Matters

Number of Islands is the gateway to an entire family of grid and graph traversal problems. Once you can flood-fill connected components on a 2D grid, you have the tools to tackle problems like max island area, shortest bridge between islands, surrounded regions, and Pacific Atlantic water flow. Companies love this problem because it naturally tests DFS/BFS fluency, boundary checking, and the ability to think about implicit graphs without being given an explicit adjacency list.

Understanding the Problem

Given an m x n grid where each cell is either 1 (land) or 0 (water), return the number of islands. An island is a group of 1s connected horizontally or vertically. The grid is surrounded by water on all sides.

Here is the example grid from the problem:

Looking at this grid, you can visually pick out three separate clusters of land cells. But how do you teach a computer to do the same thing?

The answer lies in treating each land cell as a node in a graph, with edges connecting adjacent land cells. Counting islands becomes counting connected components.

Edge Cases to Consider

1. Single cell grid: [[0]] returns 0, [[1]] returns 1
2. All water: No DFS ever triggers, return 0
3. All land: One massive island, return 1
4. Checkerboard pattern: Every land cell is isolated, maximizing island count

Solution Approach

Think of it like painting. You scan the grid from top-left to bottom-right. Every time you find an unpainted land cell, you grab a new color and paint the entire connected region. When you're done scanning, the number of colors you used equals the number of islands.

In algorithmic terms:

1. Create a seen grid to track visited cells
2. Scan every cell in nested row/column loops
3. When you hit an unvisited land cell, run DFS to mark the entire island as visited
4. Increment the counter each time you start a new DFS

How the DFS Works

The DFS is a recursive flood fill. Starting from a land cell, it:

1. Marks the current cell as visited
2. Checks all 4 neighbors (up, down, left, right)
3. For each neighbor that is in bounds, unvisited, and land, recursively visits it

This spreads across the entire island like water flowing through connected channels. When it returns, every cell in that island is marked as seen.

Walking Through the Example

Let's trace through the simpler grid that contains just one island:

Step 1: Start scanning. The scanner hits cell (0,0), which is land and unvisited. We trigger DFS and the flood fill begins.

Step 2: DFS expands. From (0,0), we visit neighbors (0,1) and (1,0). Each of those visits their own neighbors, spreading the seen markers across the island.

Step 3: DFS complete. The recursion returns after visiting all 7 connected land cells. The counter increments to 1. The scanner continues but finds no more unvisited land.

Result: 1 island, which matches our expected output.

The Three-Island Example

For the more complex grid with 3 islands, the algorithm starts three separate DFS calls. Each discovers a different connected component:

• Green (Island 1): 7 cells forming the large connected mass in the upper-left
• Purple (Island 2): 3 cells in the lower-right quadrant
• Orange (Island 3): 1 isolated cell at (3,0)

The scanner encounters these in order: it finds (0,0), flood-fills island 1, then continues scanning until it reaches (2,3) for island 2, and finally (3,0) for island 3.

Implementation

Prefer a different language? Jump to solutions in other languages.

Here is the solution in Java:

import java.util.List;
import java.util.stream.Stream;

public class Solution {
  public int countIslands(int[][] grid) {
    boolean[][] seen = new boolean[grid.length][grid[0].length];
    int numIslands = 0;

    for (int i = 0; i < grid.length; i++) {
      for (int j = 0; j < grid[0].length; j++) {
        if (grid[i][j] == 1 && !seen[i][j]) {
          search(grid, seen, i, j);
          numIslands++;
        }
      }
    }

    return numIslands;
  }

  private void search(int[][] grid, boolean[][] seen, int r, int c) {
    seen[r][c] = true;
    traversableRowCols(grid, seen, r, c)
      .forEach(rowCol -> search(grid, seen, rowCol.get(0), rowCol.get(1)));
  }

  private Stream<List<Integer>> traversableRowCols(
    int[][] grid, boolean[][] seen, int r, int c
  ) {
    return Stream.of(
      List.of(r - 1, c), List.of(r + 1, c), List.of(r, c - 1), List.of(r, c + 1)
    ).filter(rowCol -> isTraversable(grid, seen, rowCol.get(0), rowCol.get(1)));
  }

  private boolean isTraversable(int[][] grid, boolean[][] seen, int r, int c) {
    return r >= 0 && c >= 0 && r < grid.length &&
             c < grid[0].length && !seen[r][c] && grid[r][c] == 1;
  }
}

The search method is the DFS engine. It marks the current cell and recurses into valid neighbors. The isTraversable check handles boundary validation, the seen guard, and the land check in one clean predicate.

Complexity Analysis

Time Complexity: O(m * n)

Each cell is processed at most twice: once during the outer scan and once when visited by DFS. The seen grid ensures no cell is ever revisited by DFS. Across all DFS calls combined, the total number of recursive invocations is bounded by the number of land cells, which is at most m * n.

Space Complexity: O(m * n)

Two sources of space usage:

• Seen grid: m * n booleans
• Recursion stack: In the worst case (entire grid is land arranged in a snake pattern), the DFS stack reaches m * n frames

For grids with a mix of land and water, the actual stack depth is typically much smaller than m * n, but we report worst-case.

Alternative Approaches

1. BFS with queue: Same complexity, avoids deep recursion. Use when grid dimensions might exceed stack limits.
2. Union-Find (Disjoint Set): Useful when islands are built incrementally (cells added one at a time). O(m * n * alpha(m * n)) time, nearly linear.
3. In-place modification: Skip the seen grid by setting visited cells to 0. Saves O(m * n) space but mutates input.

Common Pitfalls

1. Forgetting diagonal exclusion: The standard problem uses 4-directional adjacency, not 8. Adding diagonals produces incorrect counts.
2. Off-by-one in bounds checking: Always check r >= 0 && c >= 0 before accessing the grid. Negative indices cause exceptions in most languages.
3. Not marking cells before recursing: If you mark the cell as seen after the recursive calls instead of before, you create infinite loops as neighbors revisit the current cell.
4. Stack overflow on large grids: For grids larger than roughly 500x500, consider switching to iterative BFS to avoid stack depth limits.

Edge Cases

The checkerboard pattern is a great stress test. Every land cell is surrounded by water on all sides, producing the maximum possible number of islands:

This 3x3 grid has 5 islands, each a single isolated cell. Your algorithm must handle this correctly because the DFS for each island terminates immediately after marking one cell.

The opposite extreme is a grid where all land cells form one connected component:

Despite the hourglass shape with two water cells, every land cell connects through the center, forming a single island.

Interview Tips

When solving this problem in an interview:

1. Clarify adjacency: "Are islands connected only horizontally and vertically, or diagonally too?"
2. Ask about mutation: "Can I modify the input grid, or should I preserve it?"
3. Draw the grid: Sketch a small 3x3 or 4x4 example and walk through DFS visually
4. Mention BFS alternative: After implementing DFS, say "For very large grids, I'd switch to BFS to avoid stack overflow"
5. Discuss Union-Find: If the interviewer asks about online updates (adding land cells one at a time), pivot to the Union-Find approach

Key Takeaways

• Number of Islands reduces to counting connected components on an implicit graph where land cells are nodes and edges connect 4-directional neighbors.
• The DFS flood fill marks all cells in a connected component as visited in one pass, so the number of DFS initiations equals the island count.
• Time and space are both O(m * n). Space comes from the seen grid and recursion stack. BFS trades stack depth for queue memory but has identical asymptotic complexity.
• Always mark cells as visited before recursing into neighbors to prevent infinite loops. This is the most common bug candidates introduce.
• Test with edge cases: empty grid, single cell, all water, all land, and checkerboard patterns. These catch boundary errors and off-by-one mistakes that slip through with standard examples.

Practice Makes Perfect

Once you're comfortable counting islands, these related problems build on the same DFS/BFS grid traversal pattern:

• Find the maximum area island in the grid
• Determine the number of distinct island shapes
• Find the shortest bridge (minimum 0s to flip) between two islands
• Count surrounded regions that cannot reach the grid border

This problem and thousands of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top companies. Whether you're targeting Amazon, Meta, or Microsoft, mastering grid traversal problems like this will build a strong foundation for your interview prep.

Solutions in Other Languages

Python

from typing import List


class Solution:
    def count_islands(self, grid: List[List[int]]) -> int:
        seen = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
        num_islands = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1 and not seen[i][j]:
                    self.search(grid, seen, i, j)
                    num_islands += 1
        return num_islands

    def search(self, grid, seen, r, c):
        seen[r][c] = True
        for row_col in self.traversable_row_cols(grid, seen, r, c):
            self.search(grid, seen, row_col[0], row_col[1])

    def traversable_row_cols(self, grid, seen, r, c):
        return filter(
            lambda row_col: self.is_traversable(grid, seen, row_col[0], row_col[1]),
            [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]]
        )

    def is_traversable(self, grid, seen, r, c):
        return 0 <= r < len(grid) and \
               0 <= c < len(grid[0]) and \
               not seen[r][c] and grid[r][c] == 1

JavaScript

class Solution {
  countIslands(grid) {
    const seen = [...Array(grid.length)].map(_ => Array(grid[0].length));
    let numIslands = 0;
    for (let i = 0; i < grid.length; i++) {
      for (let j = 0; j < grid[0].length; j++) {
        if (grid[i][j] === 1 && !seen[i][j]) {
          this.search(grid, seen, i, j);
          numIslands++;
        }
      }
    }
    return numIslands;
  }

  search(grid, seen, r, c) {
    seen[r][c] = true;
    this.traversableRowCols(grid, seen, r, c)
      .forEach(rowCol => this.search(grid, seen, rowCol[0], rowCol[1]));
  }

  traversableRowCols(grid, seen, r, c) {
    return [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]]
      .filter(rowCol => this.isTraversable(grid, seen, rowCol[0], rowCol[1]));
  }

  isTraversable(grid, seen, r, c) {
    return r >= 0 && c >= 0 && r < grid.length &&
      c < grid[0].length && !seen[r][c] && grid[r][c] === 1;
  }
}

TypeScript

class Solution {
  countIslands(grid: number[][]): number {
    const seen: boolean[][] = Array.from(
      { length: grid.length }, () => Array(grid[0].length).fill(false)
    );
    let numIslands = 0;
    for (let i = 0; i < grid.length; i++) {
      for (let j = 0; j < grid[0].length; j++) {
        if (grid[i][j] === 1 && !seen[i][j]) {
          this.search(grid, seen, i, j);
          numIslands++;
        }
      }
    }
    return numIslands;
  }

  search(grid: number[][], seen: boolean[][], r: number, c: number): void {
    seen[r][c] = true;
    this.traversableRowCols(grid, seen, r, c)
      .forEach(rowCol => this.search(grid, seen, rowCol[0], rowCol[1]));
  }

  traversableRowCols(grid: number[][], seen: boolean[][], r: number, c: number): number[][] {
    return [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]]
      .filter(rowCol => this.isTraversable(grid, seen, rowCol[0], rowCol[1]));
  }

  isTraversable(grid: number[][], seen: boolean[][], r: number, c: number): boolean {
    return r >= 0 && c >= 0 && r < grid.length &&
      c < grid[0].length && !seen[r][c] && grid[r][c] === 1;
  }
}

C++

#include <iostream>
#include <vector>

class Solution {
public:
  int countIslands(std::vector<std::vector<int>> &grid) {
    std::vector<std::vector<bool>> seen(grid.size(), std::vector<bool>(grid[0].size()));
    int numIslands = 0;

    for (int i = 0; i < grid.size(); i++) {
      for (int j = 0; j < grid[0].size(); j++) {
        if (grid[i][j] == 1 && !seen[i][j]) {
          search(grid, seen, i, j);
          numIslands++;
        }
      }
    }

    return numIslands;
  }

private:
  void search(std::vector<std::vector<int>> &grid,
              std::vector<std::vector<bool>> &seen, int r, int c) {
    seen[r][c] = true;
    for (auto &rowCol: traversableRowCols(grid, seen, r, c)) {
      search(grid, seen, rowCol.first, rowCol.second);
    }
  }

  std::vector<std::pair<int, int>> traversableRowCols(
      std::vector<std::vector<int>> &grid,
      std::vector<std::vector<bool>> &seen, int r, int c) {
    std::vector<std::pair<int, int>> result;
    for (auto &point: {
        std::make_pair(r - 1, c), std::make_pair(r + 1, c),
        std::make_pair(r, c - 1), std::make_pair(r, c + 1)
    }) {
      if (isTraversable(grid, seen, point.first, point.second)) {
        result.push_back(point);
      }
    }
    return result;
  }

  bool isTraversable(std::vector<std::vector<int>> &grid,
      std::vector<std::vector<bool>> &seen, int r, int c) {
    return r >= 0 && c >= 0 && r < grid.size() &&
           c < grid[0].size() && !seen[r][c] && grid[r][c] == 1;
  }
};

Go

package solution

type Solution struct{}

type Point struct {
  row int
  col int
}

func (s *Solution) CountIslands(grid [][]int) int {
  seen := make([][]bool, len(grid))
  for i := range seen {
    seen[i] = make([]bool, len(grid[0]))
  }

  numIslands := 0
  for i := 0; i < len(grid); i++ {
    for j := 0; j < len(grid[0]); j++ {
      if grid[i][j] == 1 && !seen[i][j] {
        search(grid, seen, i, j)
        numIslands++
      }
    }
  }
  return numIslands
}

func search(grid [][]int, seen [][]bool, r, c int) {
  seen[r][c] = true
  for _, rowCol := range traversableRowCols(grid, seen, r, c) {
    search(grid, seen, rowCol.row, rowCol.col)
  }
}

func traversableRowCols(grid [][]int, seen [][]bool, r, c int) []Point {
  result := make([]Point, 0)
  for _, point := range []Point{{r - 1, c}, {r + 1, c}, {r, c - 1}, {r, c + 1}} {
    if isTraversable(grid, seen, point.row, point.col) {
      result = append(result, point)
    }
  }
  return result
}

func isTraversable(grid [][]int, seen [][]bool, r, c int) bool {
  return r >= 0 && c >= 0 &&
    r < len(grid) && c < len(grid[0]) &&
    !seen[r][c] && grid[r][c] == 1
}

Scala

class Solution {
  def countIslands(grid: Array[Array[Int]]): Int = {
    val seen = Array.ofDim[Boolean](grid.length, grid(0).length)
    var numIslands = 0
    for (i <- grid.indices) {
      for (j <- grid(0).indices) {
        if (grid(i)(j) == 1 && !seen(i)(j)) {
          search(grid, seen, i, j)
          numIslands += 1
        }
      }
    }
    numIslands
  }

  private def search(grid: Array[Array[Int]], seen: Array[Array[Boolean]],
                     r: Int, c: Int): Unit = {
    seen(r)(c) = true
    traversableRowCols(grid, seen, r, c)
      .foreach(rowCol => search(grid, seen, rowCol._1, rowCol._2))
  }

  private def traversableRowCols(grid: Array[Array[Int]], seen: Array[Array[Boolean]],
                                  r: Int, c: Int): Seq[(Int, Int)] = {
    Seq((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1))
      .filter(rowCol => isTraversable(grid, seen, rowCol._1, rowCol._2))
  }

  private def isTraversable(grid: Array[Array[Int]], seen: Array[Array[Boolean]],
                             r: Int, c: Int): Boolean = {
    r >= 0 && c >= 0 && r < grid.length &&
      c < grid(0).length && !seen(r)(c) && grid(r)(c) == 1
  }
}

Kotlin

class Solution {
  fun countIslands(grid: Array<IntArray>): Int {
    val seen = Array(grid.size) { BooleanArray(grid[0].size) }
    var numIslands = 0
    for (i in grid.indices) {
      for (j in grid[0].indices) {
        if (grid[i][j] == 1 && !seen[i][j]) {
          search(grid, seen, i, j)
          numIslands++
        }
      }
    }
    return numIslands
  }

  private fun search(grid: Array<IntArray>, seen: Array<BooleanArray>, r: Int, c: Int) {
    seen[r][c] = true
    traversableRowCols(grid, seen, r, c).forEach { search(grid, seen, it[0], it[1]) }
  }

  private fun traversableRowCols(
    grid: Array<IntArray>, seen: Array<BooleanArray>, r: Int, c: Int
  ): List<List<Int>> {
    return listOf(listOf(r - 1, c), listOf(r + 1, c), listOf(r, c - 1), listOf(r, c + 1))
      .filter { isTraversable(grid, seen, it[0], it[1]) }
  }

  private fun isTraversable(
    grid: Array<IntArray>, seen: Array<BooleanArray>, r: Int, c: Int
  ): Boolean {
    return r >= 0 && c >= 0 && r < grid.size && c < grid[0].size &&
      !seen[r][c] && grid[r][c] == 1
  }
}

Swift

import Foundation

class Solution {
    func countIslands(_ grid: [[Int]]) -> Int {
        var seen = Array(repeating: Array(repeating: false, count: grid[0].count),
                         count: grid.count)
        var numIslands = 0
        for i in 0..<grid.count {
            for j in 0..<grid[0].count {
                if grid[i][j] == 1 && !seen[i][j] {
                    search(grid, &seen, i, j)
                    numIslands += 1
                }
            }
        }
        return numIslands
    }

    private func search(_ grid: [[Int]], _ seen: inout [[Bool]], _ r: Int, _ c: Int) {
        seen[r][c] = true
        for rowCol in traversableRowCols(grid, seen, r, c) {
            search(grid, &seen, rowCol[0], rowCol[1])
        }
    }

    private func traversableRowCols(_ grid: [[Int]], _ seen: [[Bool]],
                                     _ r: Int, _ c: Int) -> [[Int]] {
        return [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]]
            .filter { isTraversable(grid, seen, $0[0], $0[1]) }
    }

    private func isTraversable(_ grid: [[Int]], _ seen: [[Bool]],
                                _ r: Int, _ c: Int) -> Bool {
        return r >= 0 && c >= 0 && r < grid.count && c < grid[0].count &&
               !seen[r][c] && grid[r][c] == 1
    }
}

Rust

pub struct Solution;

impl Solution {
    pub fn count_islands(&self, mut grid: Vec<Vec<i32>>) -> i32 {
        let mut seen = vec![vec![false; grid[0].len()]; grid.len()];
        let mut num_islands = 0;
        for i in 0..grid.len() {
            for j in 0..grid[0].len() {
                if grid[i][j] == 1 && !seen[i][j] {
                    Self::search(&grid, &mut seen, i, j);
                    num_islands += 1;
                }
            }
        }
        num_islands
    }

    fn search(grid: &[Vec<i32>], seen: &mut Vec<Vec<bool>>, r: usize, c: usize) {
        seen[r][c] = true;
        for (nr, nc) in Self::traversable_row_cols(grid, seen, r, c) {
            Self::search(grid, seen, nr, nc);
        }
    }

    fn traversable_row_cols(
        grid: &[Vec<i32>], seen: &[Vec<bool>], r: usize, c: usize,
    ) -> Vec<(usize, usize)> {
        let directions: [(i32, i32); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];
        directions
            .iter()
            .map(|&(dr, dc)| (r as i32 + dr, c as i32 + dc))
            .filter(|&(nr, nc)| Self::is_traversable(grid, seen, nr, nc))
            .map(|(nr, nc)| (nr as usize, nc as usize))
            .collect()
    }

    fn is_traversable(grid: &[Vec<i32>], seen: &[Vec<bool>], r: i32, c: i32) -> bool {
        r >= 0 && c >= 0
            && (r as usize) < grid.len()
            && (c as usize) < grid[0].len()
            && !seen[r as usize][c as usize]
            && grid[r as usize][c as usize] == 1
    }
}

C#

using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int CountIslands(int[][] grid) {
        var seen = new bool[grid.Length, grid[0].Length];
        int numIslands = 0;
        for (int i = 0; i < grid.Length; i++) {
            for (int j = 0; j < grid[0].Length; j++) {
                if (grid[i][j] == 1 && !seen[i, j]) {
                    Search(grid, seen, i, j);
                    numIslands++;
                }
            }
        }
        return numIslands;
    }

    private void Search(int[][] grid, bool[,] seen, int r, int c) {
        seen[r, c] = true;
        foreach (var rowCol in TraversableRowCols(grid, seen, r, c)) {
            Search(grid, seen, rowCol[0], rowCol[1]);
        }
    }

    private List<int[]> TraversableRowCols(int[][] grid, bool[,] seen, int r, int c) {
        return new List<int[]> {
            new[] {r - 1, c}, new[] {r + 1, c}, new[] {r, c - 1}, new[] {r, c + 1}
        }.Where(rowCol => IsTraversable(grid, seen, rowCol[0], rowCol[1])).ToList();
    }

    private bool IsTraversable(int[][] grid, bool[,] seen, int r, int c) {
        return r >= 0 && c >= 0 && r < grid.Length &&
                 c < grid[0].Length && !seen[r, c] && grid[r][c] == 1;
    }
}

Dart

class Solution {
  int countIslands(List<List<int>> grid) {
    List<List<bool>> seen = List.generate(
      grid.length, (_) => List.filled(grid[0].length, false));
    int numIslands = 0;
    for (int i = 0; i < grid.length; i++) {
      for (int j = 0; j < grid[0].length; j++) {
        if (grid[i][j] == 1 && !seen[i][j]) {
          _search(grid, seen, i, j);
          numIslands++;
        }
      }
    }
    return numIslands;
  }

  void _search(List<List<int>> grid, List<List<bool>> seen, int r, int c) {
    seen[r][c] = true;
    for (List<int> rowCol in _traversableRowCols(grid, seen, r, c)) {
      _search(grid, seen, rowCol[0], rowCol[1]);
    }
  }

  List<List<int>> _traversableRowCols(
      List<List<int>> grid, List<List<bool>> seen, int r, int c) {
    return [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]]
      .where((rowCol) => _isTraversable(grid, seen, rowCol[0], rowCol[1]))
      .toList();
  }

  bool _isTraversable(
      List<List<int>> grid, List<List<bool>> seen, int r, int c) {
    return r >= 0 && c >= 0 && r < grid.length &&
           c < grid[0].length && !seen[r][c] && grid[r][c] == 1;
  }
}

PHP

<?php

class Solution {
    public function countIslands(array $grid): int {
        $seen = array_fill(0, count($grid),
                           array_fill(0, count($grid[0]), false));
        $numIslands = 0;
        for ($i = 0; $i < count($grid); $i++) {
            for ($j = 0; $j < count($grid[0]); $j++) {
                if ($grid[$i][$j] === 1 && !$seen[$i][$j]) {
                    $this->search($grid, $seen, $i, $j);
                    $numIslands++;
                }
            }
        }
        return $numIslands;
    }

    private function search(array $grid, array &$seen, int $r, int $c): void {
        $seen[$r][$c] = true;
        foreach ($this->traversableRowCols($grid, $seen, $r, $c) as $rowCol) {
            $this->search($grid, $seen, $rowCol[0], $rowCol[1]);
        }
    }

    private function traversableRowCols(
        array $grid, array $seen, int $r, int $c): array {
        return array_filter(
            [[$r - 1, $c], [$r + 1, $c], [$r, $c - 1], [$r, $c + 1]],
            fn($rowCol) => $this->isTraversable($grid, $seen, $rowCol[0], $rowCol[1])
        );
    }

    private function isTraversable(
        array $grid, array $seen, int $r, int $c): bool {
        return $r >= 0 && $c >= 0 && $r < count($grid) &&
               $c < count($grid[0]) && !$seen[$r][$c] && $grid[$r][$c] === 1;
    }
}

Ruby

class Solution
  def count_islands(grid)
    seen = Array.new(grid.length) { Array.new(grid[0].length, false) }
    num_islands = 0
    grid.each_with_index do |row, i|
      row.each_with_index do |cell, j|
        if cell == 1 && !seen[i][j]
          search(grid, seen, i, j)
          num_islands += 1
        end
      end
    end
    num_islands
  end

  private

  def search(grid, seen, row, col)
    seen[row][col] = true
    traversable_coords(grid, seen, row, col).each { |r, c| search(grid, seen, r, c) }
  end

  def traversable_coords(grid, seen, row, col)
    [[row - 1, col], [row + 1, col], [row, col - 1], [row, col + 1]]
      .select { |r, c| traversable?(grid, seen, r, c) }
  end

  def traversable?(grid, seen, row, col)
    row >= 0 && col >= 0 && row < grid.length && col < grid[0].length &&
      !seen[row][col] && grid[row][col] == 1
  end
end