Amazon's Interview Question: Count Island
Tags: interview, code, graph, recursion
Published: 2018-11-02 16:05:43

---
title: Amazon's Interview Question: Count Island
published: true
description: coding interview question I was asked at an Amazon Interview and solution
tags: interview, code, graph, recursion
cover_image: https://thepracticaldev.s3.amazonaws.com/i/uvki6y9fkypdaa676rw2.jpeg
---

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.

## Problem

Given a 2 dimension array `matrix`  of `0s` and `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.

### Example

```python
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
```



## Approaches

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 `1` or `0`.

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).

**Pseudocode**

```python
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
    
```

## Solution (Python)

```python
def get_number_of_islands(binaryMatrix):
    rows = len(binaryMatrix)
    cols = len(binaryMatrix[0])
    # 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[0])
    return row >= 0 and row < rows and col >= 0 and col < cols
```



## Extra

- What is the time and space complexities?
- Question variation: Find the island with the largest size? In this case above, return `5`
- 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. 


## Notes

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