Last year when I was interviewing with Amazon, the first question that I was asked is to write a function
get_number_of_islands(matrix) . This was the first time I had seen this problem. It was hard for me. In retrospect, I want to share what I had learned and approaches to solving this problem.
Given a 2 dimension array
1s, count the number of islands of
1s. An island is surrounded by a group of adjacent cells that are all
1s. A cell can only be adjacent to each other horizontally and vertically.
input: binaryMatrix = [ [0, 1, 0, 1, 0], [0, 0, 1, 1, 1], [1, 0, 0, 1, 0], [0, 1, 1, 0, 0], [1, 0, 1, 0, 1] ] output: 6 # there are six islands
First, you should ask the interviewer questions for clarification, paraphrase the problem to make sure you understand it correctly, and/or state any assumptions.
- Does the matrix have the same number of columns or rows? (Interviewer: it should not matter)
- We assume that the cell can be adjacent only horizontally and vertically, not diagonally? (Correct)
- The function should handle the empty matrix and out of bound data access correctly.
Second, now you can talk about the processes to solve this problem out loud.
Okay, so we want to iterate over each cell in the matrix. Then we can check if the cell is
It is a
0, it is not an island and we can continue. If it is a
1, it is guaranteed that we found 1 island. (sound like a base case? ) At this point, we need a mechanism to make this cell as visited, so next time around we can skip it to avoid repeated counting. After that, we want to look at all the adjacent cells to repeat the process (recursion).
def main(): visited  # array to keep track of visited cell num_islands = 0 # start with zero for each row, col in matrix num_island += get_number_of_islands(matrix, row, col) #return 1 if it is an island return num_island def get_number_of_islands(matrix, row, col, visited): check if row and col is out of bound of the matrix check if we already visited the cell with row, col check if the cell is 0 => return 0 mark the cell as visited in the visited array recursive call get_number_of_islands() on each adjacent cell return 1
def get_number_of_islands(binaryMatrix): rows = len(binaryMatrix) cols = len(binaryMatrix) # you can use Set if you like # or change the content of binaryMatrix as it is visited visited = [[0 for col in range(cols)] for r in range(rows)] number_of_island = 0 for row in range(rows): for col in range(cols): number_of_island += get_island(binaryMatrix, row, col, visited) return number_of_island # get a continuous island def get_island(binaryMatrix, row, col, visited): if not is_valid(binaryMatrix, row, col) or visited[row][col] == 1 or binaryMatrix[row][col] == 0: return 0 # mark as visited visited[row][col] = 1 get_island(binaryMatrix, row, col + 1, visited) get_island(binaryMatrix, row, col - 1, visited) get_island(binaryMatrix, row + 1, col, visited) get_island(binaryMatrix, row - 1, col, visited) return 1 def is_valid(binaryMatrix, row, col): rows = len(binaryMatrix) cols = len(binaryMatrix) return row >= 0 and row < rows and col >= 0 and col < cols
- What is the time and space complexities?
- Question variation: Find the island with the largest size? In this case above, return
- This problem can also be solved without using recursion as well. But it is required a Queue or Stack to keep track of adjacent cells to visit.
This question can be hard and make an interviewee being stuck (including myself) due to a number of reasons.
- unfamiliarity with basic Graph data structure and the concepts of DFS or BFS traversal. This is considered a graph with the adjacency matrix.
- being stuck in handling the base case and recursive case.
- interview time constraint
*Cover image is obtained from unsplash.com