Description

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Solution

Identify islands using nested loops. When an island is found mark it as seen and increment the count.

Setup function

We'll reference the rows and cols length multiple times so we initialize m and n to make it easier to use them later.

We also define a set, seen, to allow us to track which nodes/land we've seen.

Lastly we define a var count set to 0 which we return at the end of the function. This will be what holds the number of islands

1//
2 
3var numIslands = function (grid) {
4  var m = grid.length
5  var n = grid[0].length
6  var seen = new Set()
7 
8  var count = 0
9 
10  return count
11}

1//
2 
3function numIslands(grid: string[][]): number {
4  var m = grid.length
5  var n = grid[0].length
6  var seen = new Set()
7 
8  var count = 0
9 
10  return count
11}

1//
2 
3class Solution {
4  int numIslands(List<List<String>> grid) {
5    var m = grid.length;
6    var n = grid[0].length;
7    var seen = new Set();
8 
9    var count = 0;
10 
11    return count;
12  }
13}

1//
2 
3class Solution {
4  public int numIslands(char[][] grid) {
5    int count = 0;
6    int m = grid.length;
7    int n = grid[0].length;
8    Set<String> seen = new HashSet<String>();
9 
10    return count;
11  }
12}

1#
2 
3class Solution:
4  def numIslands(self, grid: List[List[str]]) -> int:
5    seen = set()
6    m, n = len(grid), len(grid[0])
7 
8    count = 0
9 
10    return count

1#
2 
3def num_islands(grid)
4  m, n = grid.length, grid[0].length
5  seen = Set.new
6  count = 0
7  return count
8end

1//
2 
3func numIslands(grid [][]byte) int {
4  count := 0
5  m := len(grid)
6  n := len(grid[0])
7 
8  seen := make(map[string]bool)
9 
10  return count
11}

Iterate matrix nodes

Loop over the rows and cols of the matrix.

On each node call dfs() and pass in the coordinates of the node.

If dfs() returns true increment count.

1//
2 
3var numIslands = function (grid) {
4  var m = grid.length
5  var n = grid[0].length
6  var seen = new Set()
7 
8  function dfs(r, c) {
9  }
10 
11  var count = 0
12 
13  for (var r = 0; r < m; r++) {
14    for (var c = 0; c < n; c++) {
15      if (dfs(r, c)) {
16        count += 1
17      }
18    }
19  }
20 
21  return count
22}

1//
2 
3function numIslands(grid: string[][]): number {
4  var m = grid.length
5  var n = grid[0].length
6  var seen = new Set()
7 
8  function dfs(r,c) {
9  }
10 
11  var count = 0
12 
13  for (var r = 0; r < m; r++) {
14    for (var c = 0; c < n; c++) {
15      if (dfs(r, c)) {
16        count += 1
17      }
18    }
19  }
20 
21  return count;
22};

1//
2 
3class Solution {
4  int numIslands(List<List<String>> grid) {
5    var m = grid.length;
6    var n = grid[0].length;
7    var seen = new Set();
8 
9    dfs(r,c) {
10    }
11 
12    var count = 0;
13 
14    for (var r = 0; r < m; r++) {
15      for (var c = 0; c < n; c++) {
16        if (dfs(r, c)) {
17          count += 1;
18        }
19      }
20    }
21 
22    return count;
23  }
24}

1//
2 
3class Solution {
4  public int numIslands(char[][] grid) {
5    int count = 0;
6    int m = grid.length;
7    int n = grid[0].length;
8    Set<String> seen = new HashSet<String>();
9 
10    for (int r = 0; r < m; r++) {
11      for (int c = 0; c < n; c++) {
12        if (dfs(r, c, seen, grid)) {
13          count += 1;
14        }
15      }
16    }
17 
18    return count;
19  }
20 
21  public boolean dfs(int r, int c, Set<String> seen, char[][] grid) {
22  }
23}

1#
2 
3class Solution:
4  def numIslands(self, grid: List[List[str]]) -> int:
5    seen = set()
6    m, n = len(grid), len(grid[0])
7 
8    def dfs(r, c):
9      pass
10 
11    count = 0
12    for r in range(m):
13      for c in range(n):
14        if dfs(r, c):
15          res += 1
16 
17    return count

1#
2 
3def num_islands(grid)
4  m, n = grid.length, grid[0].length
5  seen = Set.new
6 
7  dfs = lambda do |r,c|
8  end
9 
10  count = 0
11  m.times do |r|
12    n.times do |c|
13      if dfs.call(r,c)
14        count+=1
15      end
16    end
17  end
18  return count
19end

1//
2 
3func numIslands(grid [][]byte) int {
4  count := 0
5  m := len(grid)
6  n := len(grid[0])
7 
8  seen := make(map[string]bool)
9 
10  for r := 0; r < m; r++ {
11    for c := 0; c < n; c++ {
12      if dfs(r, c, seen, grid) {
13        count += 1
14      }
15    }
16  }
17 
18  return count
19}
20 
21func dfs(r int, c int, seen map[string]bool,  grid [][]byte) bool {
22}

Define dfs

DFS takes in the coordinates and ensures the node is inbounds, hasn't been seen, and is land.

If it isn't, then we exit the function, not incrementing the count.

1//
2 
3var numIslands = function (grid) {
4  var m = grid.length
5  var n = grid[0].length
6  var seen = new Set()
7  function dfs(r, c) {
8    var out = r < 0 || c < 0 || r == m || c == n
9    if (out) return false
10    if (seen.has(`${r},${c}`)) return false
11    if (grid[r][c] == 0) return false
12  }
13 
14  var count = 0
15 
16  for (var r = 0; r < m; r++) {
17    for (var c = 0; c < n; c++) {
18      if (dfs(r, c)) {
19        count += 1
20      }
21    }
22  }
23 
24  return count
25}

1//
2 
3function numIslands(grid: string[][]): number {
4  var m = grid.length
5  var n = grid[0].length
6  var seen = new Set()
7  function dfs(r,c) {
8    var out = r < 0 || c < 0 || r == m || c == n
9    if (out) return false
10    if (seen.has(`${r},${c}`)) return false
11    if (grid[r][c] == '0') return false
12  }
13 
14  var count = 0
15 
16  for (var r = 0; r < m; r++) {
17    for (var c = 0; c < n; c++) {
18      if (dfs(r, c)) {
19        count += 1
20      }
21    }
22  }
23 
24  return count
25}

1//
2 
3class Solution {
4  int numIslands(List<List<String>> grid) {
5    var m = grid.length;
6    var n = grid[0].length;
7    var seen = new Set();
8    dfs(r,c) {
9      if (r < 0 || c < 0 || r == m || c == n) {
10        return false;
11      }
12      if (seen.contains('$r,$c')) {
13        return false;
14      }
15 
16      if (grid[r][c] == '0') {
17        return false;
18      }
19    }
20 
21    var count = 0;
22 
23    for (var r = 0; r < m; r++) {
24      for (var c = 0; c < n; c++) {
25        if (dfs(r, c)) {
26          count += 1;
27        }
28      }
29    }
30 
31    return count;
32  }
33}

1//
2 
3class Solution {
4  public int numIslands(char[][] grid) {
5    int count = 0;
6    int m = grid.length;
7    int n = grid[0].length;
8    Set<String> seen = new HashSet<String>();
9 
10    for (int r = 0; r < m; r++) {
11      for (int c = 0; c < n; c++) {
12        if (dfs(r, c, seen, grid)) {
13          count += 1;
14        }
15      }
16    }
17 
18    return count;
19  }
20 
21  public boolean dfs(int r, int c, Set<String> seen, char[][] grid) {
22    boolean out = r < 0 || c < 0 || r == grid.length || c == grid[0].length;
23    if (out) return false;
24    if (Character.toString(grid[r][c]).equals("0")) return false;
25    String coords = String.format("%s,%s", r, c);
26    if (seen.contains(coords)) return false;
27  }
28}

1#
2 
3class Solution:
4  def numIslands(self, grid: List[List[str]]) -> int:
5    seen = set()
6    m, n = len(grid), len(grid[0])
7 
8    def dfs(r, c):
9      out = r<0 or c<0 or r==m or c==n
10      if out or (r, c) in seen or grid[r][c] == '0':
11        return False
12 
13    count = 0
14    for r in range(m):
15      for c in range(n):
16        if dfs(r, c):
17          res += 1
18 
19    return count

1#
2 
3def num_islands(grid)
4  m, n = grid.length, grid[0].length
5  seen = Set.new
6 
7  dfs = lambda do |r,c|
8    out = r < 0 || c < 0 || r == m || c == n
9    return false if out
10    return false if grid[r][c] == '0'
11    return false if seen.include?("#{r},#{c}")
12  end
13 
14  count = 0
15  m.times do |r|
16    n.times do |c|
17      if dfs.call(r,c)
18        count+=1
19      end
20    end
21  end
22 
23  return count
24end

1//
2 
3func numIslands(grid [][]byte) int {
4  count := 0
5  m := len(grid)
6  n := len(grid[0])
7 
8  seen := make(map[string]bool)
9 
10  for r := 0; r < m; r++ {
11    for c := 0; c < n; c++ {
12      if dfs(r, c, seen, grid) {
13        count += 1
14      }
15    }
16  }
17 
18  return count
19}
20 
21func dfs(r int, c int, seen map[string]bool,  grid [][]byte) bool {
22  m := len(grid)
23  n := len(grid[0])
24  out := r < 0 || c < 0 || r == m || c == n
25  if out || grid[r][c] == '0' {
26    return false
27  }
28 
29  coords := fmt.Sprintf("%d,%d", r, c)
30 
31  if _, ok := seen[coords]; ok {
32    return false
33  }
34}

Recursively call DFS()

Within dfs we now recursively call dfs updating r & c.

We increment and decrement both values to check left, top, right, and below the current node.

Return true at the end of the function so that the outer nested loop knows to increment the count.

1//
2 
3var numIslands = function (grid) {
4  var m = grid.length
5  var n = grid[0].length
6  var seen = new Set()
7  function dfs(r, c) {
8    var out = r < 0 || c < 0 || r == m || c == n
9    if (out) return false
10    if (seen.has(`${r},${c}`)) return false
11    if (grid[r][c] == 0) return false
12 
13    seen.add(`${r},${c}`)
14 
15    dfs(r + 1, c)
16    dfs(r - 1, c)
17    dfs(r, c + 1)
18    dfs(r, c - 1)
19 
20    return true
21  }
22 
23  var count = 0
24 
25  for (var r = 0; r < m; r++) {
26    for (var c = 0; c < n; c++) {
27      if (dfs(r, c)) {
28        count += 1
29      }
30    }
31  }
32 
33  return count
34}

1//
2function numIslands(grid: string[][]): number {
3  var m = grid.length
4  var n = grid[0].length
5  var seen = new Set()
6  function dfs(r,c) {
7    var out = r < 0 || c < 0 || r == m || c == n
8    if (out) return false
9    if (seen.has(`${r},${c}`)) return false
10    if (grid[r][c] == '0') return false
11    seen.add(`${r},${c}`)
12    dfs(r + 1, c)
13    dfs(r - 1, c)
14    dfs(r, c + 1)
15    dfs(r, c - 1)
16    return true
17  }
18 
19  var count = 0
20 
21  for (var r = 0; r < m; r++) {
22    for (var c = 0; c < n; c++) {
23      if (dfs(r, c)) {
24        count += 1
25      }
26    }
27  }
28 
29  return count
30}

1//
2 
3class Solution {
4  int numIslands(List<List<String>> grid) {
5    var m = grid.length;
6    var n = grid[0].length;
7    var seen = new Set();
8    dfs(r,c) {
9      if (r < 0 || c < 0 || r == m || c == n) {
10        return false;
11      }
12      if (seen.contains('$r,$c')) {
13        return false;
14      }
15 
16      if (grid[r][c] == '0') {
17        return false;
18      }
19 
20      seen.add('$r,$c');
21 
22      dfs(r + 1, c);
23      dfs(r - 1, c);
24      dfs(r, c + 1);
25      dfs(r, c - 1);
26 
27      return true;
28    }
29 
30    var count = 0;
31 
32    for (var r = 0; r < m; r++) {
33      for (var c = 0; c < n; c++) {
34        if (dfs(r, c)) {
35          count += 1;
36        }
37      }
38    }
39 
40    return count;
41  }
42}

1//
2 
3class Solution {
4  public int numIslands(char[][] grid) {
5    int count = 0;
6    int m = grid.length;
7    int n = grid[0].length;
8    Set<String> seen = new HashSet<String>();
9 
10    for (int r = 0; r < m; r++) {
11      for (int c = 0; c < n; c++) {
12        if (dfs(r, c, seen, grid)) {
13          count += 1;
14        }
15      }
16    }
17 
18    return count;
19  }
20 
21  public boolean dfs(int r, int c, Set<String> seen, char[][] grid) {
22    boolean out = r < 0 || c < 0 || r == grid.length || c == grid[0].length;
23    if (out) return false;
24    if (Character.toString(grid[r][c]).equals("0")) return false;
25    String coords = String.format("%s,%s", r, c);
26    if (seen.contains(coords)) return false;
27    seen.add(coords);
28 
29    dfs(r + 1, c, seen, grid);
30    dfs(r - 1, c, seen, grid);
31    dfs(r, c + 1, seen, grid);
32    dfs(r, c - 1, seen, grid);
33 
34    return true;
35  }
36}

1#
2 
3class Solution:
4  def numIslands(self, grid: List[List[str]]) -> int:
5    seen = set()
6    m, n = len(grid), len(grid[0])
7 
8    def dfs(r, c):
9      out = r<0 or c<0 or r==m or c==n
10      if out or (r, c) in seen or grid[r][c] == '0':
11        return False
12      seen.add((r, c))
13      dfs(r + 1, c)
14      dfs(r - 1, c)
15      dfs(r, c + 1)
16      dfs(r, c - 1)
17      return True
18 
19    count = 0
20    for r in range(m):
21      for c in range(n):
22        if dfs(r, c):
23          res += 1
24 
25    return count

1#
2 
3def num_islands(grid)
4  m, n = grid.length, grid[0].length
5  seen = Set.new
6 
7  dfs = lambda do |r,c|
8    out = r < 0 || c < 0 || r == m || c == n
9    return false if out
10    return false if grid[r][c] == '0'
11    return false if seen.include?("#{r},#{c}")
12 
13    seen.add("#{r},#{c}")
14 
15    dfs.call(r+1,c)
16    dfs.call(r-1,c)
17    dfs.call(r,c+1)
18    dfs.call(r,c-1)
19    return true
20  end
21 
22  count = 0
23  m.times do |r|
24    n.times do |c|
25      if dfs.call(r,c)
26        count+=1
27      end
28    end
29  end
30  return count
31end

1//
2import "fmt"
3 
4func numIslands(grid [][]byte) int {
5  count := 0
6  m := len(grid)
7  n := len(grid[0])
8 
9  seen := make(map[string]bool)
10 
11  for r := 0; r < m; r++ {
12    for c := 0; c < n; c++ {
13      if dfs(r, c, seen, grid) {
14        count += 1
15      }
16    }
17  }
18 
19  return count
20}
21 
22func dfs(r int, c int, seen map[string]bool,  grid [][]byte) bool {
23  m := len(grid)
24  n := len(grid[0])
25  out := r < 0 || c < 0 || r == m || c == n
26  if out || grid[r][c] == '0' {
27    return false
28  }
29 
30  coords := fmt.Sprintf("%d,%d", r, c)
31 
32  if _, ok := seen[coords]; ok {
33    return false
34  }
35 
36  seen[coords] = true
37 
38  dfs(r + 1, c, seen, grid)
39  dfs(r - 1, c, seen, grid)
40  dfs(r, c + 1, seen, grid)
41  dfs(r, c - 1, seen, grid)
42 
43  return true
44}

Questions? Concerns?

Please comment a better solution if you have one.