Matthew Prinz

Yet another software engineer that enjoys optimizing.

7 minute read

Foreward

I’m going to start making some posts on Leetcode problems I’ve done. I want to explain my thinking process. Most of the time, I find these problems have one key “trick” which I think is important to know and afterwards is very simple.

Leetcode 200: Number of Islands

Let’s start with the problem statement: 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.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.

The Process

The first thing that should jump out to you is that this is a graphing problem. Why? Well, we have an m x m grid and we have to find a pattern within it. How do we find things in general in graphs? We have two searching algorithms: breadth first search (BFS) and depth first search (DFS). Whichever one we choose to use will work. I’m going to start with BFS.

But all we know how to do is find things now - so how do we solve the problem? Here’s where the trick comes in. When we encounter an island, we can mark it by flipping the entire island over, from '1's to '0's. Using either searching algorithm, we can find the entire island.

I’m going to assume that the reader has seen breadth first search before, so I will not explain the pseudocode for it. If you have not, I’d recommend taking a look at page 202, from John Erickson’s Algorithms, located for free here. Here is the pseudocode for BFS as a refresher:

1
2
3
4
5
6
7
8
9
10
11
12
13

function BFS(G, root) is
  let Q be a queue
    label root as explored
    Q.enqueue(root)
    while Q is not empty do
        v := Q.dequeue()
        if v is the goal then
            return v
        for all edges from v to w in G.adjacentEdges(v) do
          if w is not labeled as explored then
              label w as explored
              w.parent := v
              Q.enqueue(w)

Pseudocode from Wikipedia

So, let’s turn our pseudocode into real code. The current coordinate we’re looking at will be marked by the parameters i and j. We’ll be marking nodes by their indices, so the node at grid[0][0] is marked in the queue as the array [0, 0] and explored as the string "0,0". We need the comma so we don’t have a collision between the multiple digit coordinates (for example, the coordinate 11, 2 and the coordinate 1, 12).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

void BFS(char[][] grid, int i, int j) {
    Queue<int[]> queue = new LinkedList<>();
    Set<String> explored = new HashSet<>();
    queue.add(new int[]{i, j});
    explored.add("" + i + ',' + j);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int k = 0; k < size; k++) {
            int[] coords = queue.poll();
            int currI = coords[0];
            int currJ = coords[1];
            if ((currI + 1) < grid.length && grid[currI + 1][currJ] == '1') {
                if (!explored.contains("" + (currI + 1) + ',' + currJ)) {
                    queue.add(new int[]{(currI + 1), currJ});
                    explored.add("" + (currI + 1) + ',' + currJ);
                }
            }
            if ((currI - 1) >= 0 && grid[currI - 1][currJ] == '1') {
                if (!explored.contains("" + (currI - 1) + ',' + currJ)) {
                    queue.add(new int[]{(currI - 1), currJ});
                    explored.add("" + (currI - 1) + ',' + currJ);
                }
            }
            if ((currJ + 1) < grid[0].length && grid[currI][currJ + 1] == '1') {
                if (!explored.contains("" + currI + ',' + (currJ + 1))) {
                    queue.add(new int[]{currI, (currJ + 1)});
                    explored.add("" + currI + ',' + (currJ + 1));
                }
            } 
            if ((currJ - 1) >= 0 && grid[currI][currJ - 1] == '1') {
                if (!explored.contains("" + currI + ',' + (currJ - 1))) {
                    queue.add(new int[]{currI, (currJ - 1)});
                    explored.add("" + currI + ',' + (currJ - 1));
                }
            }
            grid[currI][currJ] = '0';
        }
    }
}

Those if statements check up, down, left and right (exploring the edges in our pseudocode, line 9) and make sure that we’re still on the “island”.

Now, we need a wrapper function around BFS to solve the problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
  public int numIslands(char[][] grid) {
    int result = 0;
    for (int i = 0; i < grid.length; i++) {
      for (int j = 0; j < grid[0].length; j++) {
        if (grid[i][j] == '1') {
          result++;
          bfs(grid, i, j);
        }
      }
    }
    return result;
  }
}

All together:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

class Solution {
  public int numIslands(char[][] grid) {
    int result = 0;
    for (int i = 0; i < grid.length; i++) {
      for (int j = 0; j < grid[0].length; j++) {
        if (grid[i][j] == '1') {
          result++;
          bfs(grid, i, j);
        }
      }
    }
    return result;
  }
  void bfs(char[][] grid, int i, int j) {
    Queue<int[]> queue = new LinkedList<>();
    Set<String> explored = new HashSet<>();
    queue.add(new int[]{i, j});
    explored.add("" + i + ',' + j);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int k = 0; k < size; k++) {
            int[] coords = queue.poll();
            int currI = coords[0];
            int currJ = coords[1];
            if ((currI + 1) < grid.length && grid[currI + 1][currJ] == '1') {
                if (!explored.contains("" + (currI + 1) + ',' + currJ)) {
                    queue.add(new int[]{(currI + 1), currJ});
                    explored.add("" + (currI + 1) + ',' + currJ);
                }
            }
            if ((currI - 1) >= 0 && grid[currI - 1][currJ] == '1') {
                if (!explored.contains("" + (currI - 1) + ',' + currJ)) {
                    queue.add(new int[]{(currI - 1), currJ});
                    explored.add("" + (currI - 1) + ',' + currJ);
                }
            }
            if ((currJ + 1) < grid[0].length && grid[currI][currJ + 1] == '1') {
                if (!explored.contains("" + currI + ',' + (currJ + 1))) {
                    queue.add(new int[]{currI, (currJ + 1)});
                    explored.add("" + currI + ',' + (currJ + 1));
                }
            } 
            if ((currJ - 1) >= 0 && grid[currI][currJ - 1] == '1') {
                if (!explored.contains("" + currI + ',' + (currJ - 1))) {
                    queue.add(new int[]{currI, (currJ - 1)});
                    explored.add("" + currI + ',' + (currJ - 1));
                }
            }
            grid[currI][currJ] = '0';
        }
    }
  }
}

The depth first search algorithm is more simple and relies on recursion to traverse the graph. Again, I will include the pseudocode as a refresher. If this is the first time you’re viewing DFS, please feel free to check out page 201 from Algorithms.

1
2
3
4
5

function DFS(G, v) is
    label v as discovered
    for all directed edges from v to w that are in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G, w)

Pseudocode from Wikipedia

So, the solution ends up looking something like this:

1
2
3
4
5
6
7
8
9
10

void dfs(char[][] grid, int i, int j) {
  if (i >= grid.length || i < 0 || j < 0 || j >= grid[i].length || grid[i][j] == '0') {
    return;
  }
  grid[i][j] = '0';
  dfs(grid, i + 1, j);
  dfs(grid, i - 1, j);
  dfs(grid, i, j + 1);
  dfs(grid, i, j - 1);
}

Note that this is slightly different from the pseudocode. Instead of labeling the vertex as discovered, we mark it as '0' to indicate that we don’t need to explore it - it’s not part of our island. The wrapper function is identical to the one with BFS, except instead of calling BFS, we call DFS. The full code ends up looking like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
  public int numIslands(char[][] grid) {
    int result = 0;
    for (int i = 0; i < grid.length; i++) {
      for (int j = 0; j < grid[0].length; j++) {
        if (grid[i][j] == '1') {
          dfs(grid, i, j);
          result++;
        }
      }
    }
  return result;
  }
  
  void dfs(char[][] grid, int i, int j) {
    if (i >= grid.length || i < 0 || j < 0 || j >= grid[i].length || grid[i][j] == '0') {
      return;
    }
    grid[i][j] = '0';
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
  }
}

You May Also Enjoy

Resources

2 minute read

In my first post, I mention Algorithms by Jeff Erickson. This post will reflect some of the books and videos I’ve watched in college and beyond. However, I w...