Solution: Number of Distinct Islands

Let’s solve the Number of Distinct Islands problem using the Hash Maps pattern.

We'll cover the following

Statement

Given an m x n binary matrix where 11 represents land and 00 represents water. An island is a group of connected 1s1s that are adjacent horizontally or vertically. Two islands are considered the same if one matches the other without rotating or flipping. The task is to return the number of distinct islands.

Constraints:

  • m == grid.length

  • n == grid[i].length

  • 1≤1 \leq m, n ≤100\leq100

  • grid[i][j] is either 00 or 11.

Solution

This algorithm is designed to find the number of distinct islands in a grid, where each island is a group of connected 1s1s. The idea is to treat the grid as a map and perform a depth-first search(DFS) to explore every piece of land. During DFS, the shape of the island is stored by the relative positions of land cells to the initial starting point of the island. This means the coordinates are normalized so that two islands can be compared even in different locations on the grid. These shapes are stored in the dictionary as keys, and the count of islands having the same shape is stored as a value. The result is the number of keys in the dictionary, which represents the distinct islands.

Here’s the step-by-step implementation of the solution:

  • Initialize a set to track visited land cells and a dictionary to store the shapes of islands.

  • Loop through every cell in the grid. For each unvisited cell containing 11:

    • Call DFS on the cell.

    • Explore all connected land cells recursively in all four directions (up, down, left, right) until the entire island is mapped.

    • Normalize every land cell included in an island by subtracting the coordinates of that land cell from the coordinates of the first cell in the respective island.

  • Once DFS completes exploring an island, the shape is stored in the dictionary. The key in this dictionary represents the shape, and the value is a count of the islands having the same shape.

  • After processing the entire grid, return the dictionary as the number of distinct island shapes is the number of unique keys in the dictionary.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.