Quick Overview

This question evaluates a candidate's understanding of grid-based graph traversal and connected-component detection, along with the ability to recognize and canonicalize distinct island shapes.

Count islands and distinct shapes

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

##### Question LeetCode 200. Number of Islands LeetCode 694. Number of Distinct Islands https://leetcode.com/problems/number-of-islands/description/ https://leetcode.com/problems/number-of-distinct-islands/description/

Overview: This question evaluates a candidate's understanding of grid-based graph traversal and connected-component detection, along with the ability to recognize and canonicalize distinct island shapes.

Given a binary grid of 0s and 1s, count the total number of islands and the number of distinct island shapes. An island is a maximal group of 1s connected 4-directionally (up, down, left, right). Two islands are the same shape if one can be translated (shifted) to match the other; rotations and reflections do not count. Return [number_of_islands, number_of_distinct_shapes].

Constraints

  • 1 <= rows, cols <= 200
  • grid[i][j] is 0 or 1
  • Connectivity is 4-directional (up, down, left, right)
  • Two islands are the same shape only under translation; rotations/reflections are different
  • Return format: [number_of_islands, number_of_distinct_shapes]

Hints

  1. Traverse each unvisited land cell with DFS or BFS to mark its island.
  2. Record each island's cells relative to the starting cell to normalize by translation.
  3. Sort the relative coordinates to get a canonical shape representation and store it in a set.
  4. Use only 4-directional neighbors; diagonals do not connect islands.

Loading coding console...

Show the approach

Approach

Iterate over the grid. When a land cell is found that has not been visited, start a DFS to explore its entire island, marking cells visited. To capture the island's shape independent of its position, for each cell in the island record the coordinate relative to the first cell of that island. Sort these relative coordinates to form a canonical representation and insert it into a set. The number of DFS starts is the number of islands; the size of the set is the number of distinct shapes.

Time complexity:
O(rows * cols)
Space complexity:
O(rows * cols)