Go to “Number Of Islands (#200)” on Leetcode ↗

Number of Islands

The basic idea behind this problem is to conduct a depth-first search — loop through the grid, one cell at a time, and when you come across a “land” cell, you check out the cells adjacent to it. For each adjacent cell that is also “land”, you check out its adjacent cells, and so on, until you’ve checked out all the adjacent cells that are land. That forms one island; then you move on and keep doing that until you get to the end of the grid.

def num_islands(grid)
  return 0 if grid.empty?
  number_of_islands = 0
  grid.each_with_index do |row, row_index|
    row.each_with_index do |cell, col_index|
      next unless land?(grid, row_index, col_index)
      # Found land; increment count and explore adjacent cells
      number_of_islands += 1
      indices_to_explore = [[row_index, col_index]]
      while !indices_to_explore.empty? do
        next_location = indices_to_explore.pop
        next unless in_bounds?(grid, *next_location) && land?(grid, *next_location)
        # next_location points to land; now make it into ocean
        # so we don't double-count it
        grid[next_location.first][next_location.last] = '0'
        indices_to_explore.concat(neighboring_indices(grid, *next_location))
      end
    end
  end
  return number_of_islands
end

def land?(grid, row_index, col_index)
  grid[row_index][col_index] == '1'
end

def in_bounds?(grid, row_index, col_index)
  row_index >= 0 && col_index >= 0 && row_index < grid.length && col_index < grid.first.length
end

NEIGHBORS_DELTA = [[-1, 0], [0, -1], [1, 0], [0, 1]]

def neighboring_indices(grid, row_index, col_index)
  NEIGHBORS_DELTA.map do |(delta_row, delta_col)|
    next_row = row_index + delta_row
    next_col = col_index + delta_col
    if in_bounds?(grid, next_row, next_col)
      [next_row, next_col]
    else
      nil
    end
  end.compact
end

One note on syntax — in a method call, prefixing an array argument with * spreads it out across multiple arguments in the called method. So if we have an array next_location = [5, 6] and a method def foo(row, col), calling foo(*next_location) assigns 5 to row and 6 to col — it’s the same as calling foo(next_location[0], next_location[1]) but is a little shorter to read and write.

We start by checking if the grid is empty and returning 0 if it is. By doing so, we ensure that grid contains something, so we’re less likely to crash if we’re trying to determine the number of columns with something like grid[0].length and grid turns out to be an empty array (because in that case grid[0] would be nil.

(Of course, you could be more defensive by checking if grid[0] is nil, or even filtering out all nils in grid with something like grid.reject? { |row| row.nil? }. In this case, it’s safe to assume you’ll get some kind of reasonable input).

Then, we use two nested loops to iterate through each row/column in grid. Since we’re only interested in land, we use next to proceed to the next cell without doing anything else unless the current cell is land.

Once we’ve found land, we increment number_of_islands (because, after all, we’ve found a new island). Then we construct a stack, starting with the current cell, and as long as that stack isn’t empty, we “explore” the next location in the stack. “Exploring” a location means:

  1. Removing it from the stack (so the stack eventually empties out)
  2. Checking that it’s in-bounds, and that it’s land (if a location is out of bounds, or if it’s water, that means we’ve reached an edge of this island).
  3. Turning it into ocean (by setting the location’s value to '0') so we don’t count it again on a later iteration
  4. Add the locations that are adjacent to that location to the stack (for the while loop to pick up and continue with).

In this case, adjacent cells are those that are one cell over to the left, top, right, or bottom. We compute the coordinates for the cell in each of those directions and make sure they’re in-bounds. The compact method in Ruby returns a new array that has nil values stripped out.

What’s the runtime complexity of this solution? As an upper-bound, this problem is basically running a DFS on potentially each element of a grid with n elements. Each element in the grid can be considered a vertex, and each vertex has four edges (to its adjacent cells). The runtime of a DFS is O(V+E), and we need to do that up to n times — this is O(n*(n+4n)), which reduces to O(5n2), or O(n2).

Logically, that implies that in the worst case, we could be performing a DFS over each cell in the grid for each cell in the grid. However, our solution sets “land” cells to “water” after we pass over them once, and skips searching over “water” cells, which means we won’t search over any cell more than once. This allows us to say that, for this solution, we’ll search over each cell at most once for each cell. This can be expressed as O(n+n) or O(n).

For storage space, our DFS is bounded by the size of our grid in one direction — for a grid of MxN cells, the maximum amount of storage space needed is O(max(M, N)).