About two weeks ago I met the “number of islands” problem in LeetCode. The first idea that jumped out of my brain is ‘dynamic programming’: I can create a new matrix (let’s name it ‘number matrix’) with the same size as the problem matrix, and set every position a value. The value is the number of islands from (0, 0) to this position.

For example, as the below problem matrix:

1	1	1	1
0	0	0	0
1	0	1	1
0	0	0	0

We can create the ‘number matrix’:

1	1	1	1
1	1	1	1
2	2	3	3
2	2	3	3

Why the (4, 0) position in ‘number matrix’ is 2? Because the (0, 0) to (4, 0) area in ‘problem matrix’ has two islands:

1

0

1

0

Then, every time we want to calculate the value of a position in the ‘number matrix’ we can first calculate the values of its ‘left’, ‘top’ and ‘left-top’ position.

For example, since the (3, 3), (4, 3) and (3, 4) positions in the ‘number matrix’ are all ‘3’, and the (4, 4) position in ‘problem matrix’ is ‘0’, the (4, 4) position of ‘number matrix’ should be ‘3’ also.

But unfortunately, after two weeks of struggling on thinking, I finally found out that the value of a position in the ‘number matrix’ can’t be decided by its nearest three positions: left, top and left-top. The counterexample is below:

1	1	1	1	1	1	1
0	0	0	0	0	0	1
1	1	1	1	1	0	1
1	0	0	0	1	0	1
1	0	1	0	1	0	1
1	0	1	1	1	0	1
1	1	1	1	1	1	1

Let’s just build the number matrix for the (6, 6) to (7, 7) area of problem matrix A:

2	2
2

Don’t rush. Let’s look at another problem matrix:

1	1	1	1	1
1	0	0	0	1
1	0	1	0	1
1	0	0	0	1
1	1	1	1	1

This time, we also build the number matrix for the (4, 4) to (5, 5) area of problem matrix B:

2	2
2

See? They have the same values for left, top and left-top, but different final results (problem matrix A has just 1 island but problem matrix B has 2).

Two weeks of hard thinking just got the wrong idea. But this is the charming of algorithm 🙂