Practice/Oracle/Leetcode 694. Number of Distinct Islands

Leetcode 694. Number of Distinct Islands

CodingMust

Problem

You are given a 2D binary grid where each cell contains either 0 (water) or 1 (land). An island is defined as a group of adjacent land cells connected horizontally or vertically (4-directional connectivity).

Your task is to count how many distinct island shapes exist in the grid. Two islands are considered to have the same shape if one can be translated (shifted) to match the other exactly. Rotation and reflection do not count as the same shape.

For example, these two islands have the same shape because the second is just a translation of the first:

Island 1: Island 2: 1 1 1 1 1 1

But these two islands have different shapes:

Island 1: Island 2: 1 1 1 1 1 1

Requirements

1. Count each unique island shape only once, regardless of how many times it appears in the grid
2. Two islands are identical only if they match after translation (shifting position)
3. Islands that are rotations or reflections of each other count as different shapes
4. Use 4-directional connectivity (up, down, left, right) to determine island boundaries

Constraints

• 1 <= grid.length, grid[0].length <= 50
• grid[i][j] is either 0 or 1
• Time complexity should be O(m × n) where m and n are grid dimensions
• Space complexity should be O(m × n) in the worst case

Examples

Example 1:

Input: grid = [ [1,1,0,0,0], [1,1,0,0,0], [0,0,0,1,1], [0,0,0,1,1] ] Output: 1 Explanation: There are two islands, but they both form a 2×2 square shape. When normalized to start from the same origin point, they are identical.

Example 2:

Input: grid = [ [1,1,0,1,1], [1,0,0,0,0], [0,0,0,0,1], [1,1,0,1,1] ] Output: 3 Explanation: There are four islands with three distinct shapes that cannot be translated to match each other.

Example 3:

Input: grid = [ [1,0,1], [0,0,0], [1,0,1] ] Output: 1 Explanation: All four islands are single cells, representing the same shape.