Distinct Island
Given a boolean 2D matrix. The task is to find the number of distinct islands where a group of connected 1s (horizontally or vertically) forms an island. Two islands are considered to be distinct if and only if one island is identical to another (not rotated or reflected).

Question

Distinct Island

Given a boolean 2D matrix. The task is to find the number of distinct islands where a group of connected 1s (horizontally or vertically) forms an island. Two islands are considered to be distinct if and only if one island is identical to another (not rotated or reflected).

Accepted Answer

Firstly I told the interviewer, the Depth-first search approach. I ran Depth-first search on each element of the matrix which is un-visited while traversing the matrix and for each island, I assigned a particular code for that island and store in the map . Now all the components having same code are not distinct so I removed the duplicates elements from the map and return the size of the map. I wrote a proper commented code after telling him approach. Then the interviewer gave me some test cases on which I dry run the code and explained him well. He was very much satisfied with my approach as that was unique solution and I thought that during the interview itself.

Accepted Answer

Depth First Search

For every 1 in the matrix, do DFS and mark all the 1’s as visited which are connected to this 1 and store the path of the island in a string.

Followings are the abbreviated path :

‘S’ - starting vertex

‘D’ - down

‘U’ - up

‘L’ - left

‘R’ - right

‘B’ - backtrack

Consider the following island:

1 1
1 0

Let us simulate the solution's algorithm on this island to understand its working:

At cell (0,0), path = “S”.

We move right.

At cell (0,1), path = “SR”.

We cannot go further, hence we backtrack.

At cell (0,0), path = “SRB”.

We move down.

At cell (1,0), path = “SRBD”.

We cannot go further, hence we backtrack.

At cell (0,0), path = “SRBDB”.

We cannot go further, hence we terminate.

Final path = “SRBDB”.

For every connected component store the path in the set.

Finally, the size of the set will be the total number of distinct islands.

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where N and M are the rows and columns of the matrix.

Since we are using string to store paths that take O(N * M) space. Hence the overall space complexity is O(N * M).

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), Where N and M are the rows and columns of the matrix.

Since in the worst case we would be traversing through the complete matrix that takes O(N * M) time. Hence the overall time complexity is O(N * M)

Top Barclays Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Barclays Software Developer