A popular problem associated with Leetcode’s online judge. Determine the count of islands in a grid of locations that are either land or water.

Problem

Consider the following grid of locations.

11110
11010
11000
00000

Each location is either land (1) or water (0).

Your task is to count the number of islands. An island is surrounded by water and consists of several pieces of land reachable from each other by moving horizontally or vertically. Whatever is outside the four edges of the grid is water.

Input. The input consists of the number of rows of the grid in one line followed by the rows of the grid. For example

4
11000
11000
00100
00011

Output.

The output consists of a single number, the count of islands in the grid. For example, the number of islands in the sample input is 3.

Solution

Here is a Ruby implementation.

def explore_island m, v, i, j
  w = [[i, j]]
  v[i][j] = true
  while not w.empty?
    i, j = w.pop
    if j > 0 and m[i][j-1] == 1 and !v[i][j-1]
      w << [i, j-1]
      v[i][j-1] = true
    end
    if j + 1 < m[i].length and m[i][j+1] == 1 and !v[i][j+1]
      w << [i, j+1]
      v[i][j+1] = true
    end
    if i > 0 and m[i-1][j] == 1 and !v[i-1][j]
      w << [i-1, j]
      v[i-1][j] = true
    end
    if i + 1 < m.length and m[i+1][j] == 1 and !v[i+1][j]
      w << [i+1, j]
      v[i+1][j] = true
    end
  end
end

def count_islands m
  v = m.map { |r| r.map { |_| false }}
  c = 0
  m.each_with_index do |r, i|
    r.each_with_index do |l, j|
      if l == 1 and !v[i][j]
        explore_island m, v, i, j
        c += 1
      end
    end
  end
  return c
end

def main
  n = readline.strip.to_i
  m = []
  while n > 0
    m << readline.strip.chars.map { |e| e.to_i }
    n -= 1
  end
  m.each { |r| puts "#{r}" }
  puts count_islands m
end

main

Want to read more?

I regularly write solutions to programming problems that you may or may not find in technical job interviews. I also love to explain those solutions and answer questions. If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.

Comments