Coding

Number of distinct islands

Asked at

Kotak

Oracle

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You are given a 2D matrix grid of size N × M, where each cell contains either 0 or 1. Find the number of distinct islands where a group of connected 1s (horizontally or vertically) forms an island. Two islands are considered to be same if and only if one island is equal to another (not rotated or reflected).

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:

Same colored islands are equal. We have 2 equal islands, so we have only 1 distinct island.

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:

Same colored islands are equal. We have 4 islands, but 2 of them are equal, So we have 3 distinct islands..

Input: grid = [[1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0],[0, 0, 0, 1, 1]]

1 <= N, M <= 500
grid[i][j] == 0 or 1

cpp

class Solution
{
public:
    int countDistinctIslands(vector<vector<int>> &grid){
        
    }
};

java

class Solution {
    public int countDistinctIslands(int[][] grid) {
      
    }
}

python

class Solution:
    def countDistinctIslands(self, grid):

javascript

class Solution {
    countDistinctIslands(grid) {
       
    }
}

csharp

public class Solution
{
    public int CountDistinctIslands(List<List<int>> grid)
    {
      
    }
}

func countDistinctIslands(grid [][]int) int {

}

Stuck? Show a way to structure it+

01Scan the grid for unvisited land
02DFS each island while collecting relative coordinates
03Serialize the ordered relative shape consistently
04Insert the signature into a set

Reference answer

Start by restating the input contract for Number of distinct islands and testing the smallest boundary case before choosing the algorithm. Traverse each island and record its cells relative to that island's starting cell, for example (row-startRow, col-startCol). The normalized shape is translation-invariant, so serialize it into a set. The set size is the number of distinct shapes. Explain the invariant while coding, then show how each update preserves it. On an R by C grid, traversal and shape serialization are O(R * C) time and O(R * C) space in the worst case. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

How do you treat rotations as identical?
Tests: follow-up reasoning
Can BFS be used instead of DFS?
Tests: follow-up reasoning

Hiring now

Get the Kotak interview, not just the prep

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Or practice this question first

Next question