A wrong way to solve

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:

1111000010110000problem matrix

We can create the ‘number matrix’:

1111111122332233number matrix

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

1010(0, 0) to (4, 0) area of ‘problem matrix’

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:

1111111000000111111011000101101010110111011111111problem matrix A

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

222

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

1111110001101011000111111problem matrix B

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

222

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