Solution: Problem Challenge 1

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Problem Challenge 1

Table of Contents

Contents are not accessible

Problem Statement

You are given a 2D matrix containing only 1s (land) and 0s (water).

An island is a connected set of 1s (land) and is surrounded by either an edge or 0s (water). Each cell is considered connected to other cells horizontally or vertically (not diagonally).

There are no lakes on the island, so the water inside the island is not connected to the water around it. A cell is a square with a side length of 1.

The given matrix has only one island, write a function to find the perimeter of that island.

Example 1

Input: matrix =

Output: 14

Explanation: The boundary of the island constitutes 14 sides.

Example 2

Input: matrix =

Output: 12

Explanation: The boundary of the island constitute 12 sides.

Solution

The question follows the Island pattern and is quite similar to Number of Islands problem.

We will traverse the matrix linearly to find the island. We can use the Depth First Search (DFS) or Breadth First Search (BFS) to traverse the island i.e., to find all of its connected land cells.

How do we calculate the boundary if the island?

Each cell has four sides. Each side of an island cell can be shared with another cell; we can include the side in the island perimeter only if the other cell is a water.

If a cell side is on boundary, we should include that side in the perimeter.

Following piece of code will cover these two conditions:

if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length)
   return 1; // returning 1, since this a boundary cell initiated this DFS call
 if (matrix[x][y] == 0)
   return 1; // returning 1, because of the shared side b/w a water and a land cell

Code (DFS)

Here is what our DFS algorithm will look like. We will use a separate matrix to mark nodes visited.

Python3

. . . .

Time Complexity

Time complexity of the above algorithm will be $O(M*N)$ , where ‘M’ is the number of rows and 'N' is the number of columns of the input matrix. This is due to the fact that we have to traverse the whole matrix to find the island.

Space Complexity

DFS recursion stack can go $M*N$ deep when the whole matrix is filled with '1's. Hence, the space complexity will be $O(M*N)$ , where ‘M’ is the number of rows and 'N' is the number of columns of the input matrix.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible