Reference: LeetCode
Difficulty: Medium

## Problem

Given a non-empty 2D array grid of 0‘s and 1‘s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Count the number of distinct islands. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.

Example:

## Analysis

### DFS (Shape)

The idea is to convert each island’s lands to a form that is comparable. See the example below.

We also notice that a hash set list [(0, 0), (1, 0), (1, 1)] has the same hash code with a set list [(1, 0), (1, 1), (0, 0)]. The order does not count here.

One more thing! We also need to convert a coordinate (x, y) to a unique integer number, say shapeId. An obvious way to do that is by this conversion: x * n + y. Does this guarantee unique integer numbers?

No. Consider the case below:

Unfortunately, two shapes are hashed to the hash code. It occurs because negative results exist. Since we take (0, 2) as the first coordinate, (1, 0), (1, 1) in the second row would be transformed to negative coordinates, which are then hashed to shapeIds that collide with the 1 in the previous row. To solve this problem, we use this conversion: x * n * 2 + y.

Time: $O(MN)$
Space: $O(MN)$

### DFS (Path Signature)

Use a similar idea but it is based on path signature. Let’s define something like directional id as follows:

See the example below to know what it means:

Again, the above strategy has an underlying issue. Consider the following example:

This happens because of the order that we visit each node. It is not easy to understand why. The solution is to add path.add(0) to distinguish each call stack.

Last but not least, the path ID should be contained in an array or array list since the ordering matters.

Time: $O(MN)$
Space: $O(MN)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.
Info
Article :
50
Total Count :
82.3k
UV :
PV :
Last Push :