Find perimeter of an Island
Given a binary matrix in which the values 0 and 1 correspond to land and water, respectively, and the connected ones form exactly one island, find the perimeter of an island.
Assume that there are no lakes on the island, and all the ones that exist are connected only vertically or horizontally, not diagonally. Each cell of the matrix is a square with one unit-long side. For instance, take a look at the illustration below:
The above image highlights water in blue and land in gray in a 5 × 4 binary matrix. The island represents the following matrix, and the perimeter of the island is 24, as highlighted above.
[0, 1, 1, 1],
[1, 1, 0, 0],
[1, 1, 1, 0],
[0, 1, 0, 0],
[0, 1, 1, 1]
]
We can find the perimeter of the island simply by counting the number of sides adjacent to the water. The idea is to traverse the matrix and check if the current cell is on land or not. If the current cell is land, increment the perimeter count whenever we encounter a boundary. i.e., its top, bottom, right, or left side is adjacent to the water.
Following is the C++, Java, and Python implementation based on the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <iostream> #include <vector> using namespace std; int findPerimeter(vector<vector<int>> const &island) { // base case if (island.size() == 0) { return 0; } int M = island.size(); int N = island[0].size(); int count = 0; // traverse each cell of the matrix for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { // if the current cell is a land if (island[i][j] == 1) { // check if top edge is adjacent to the water if ((i == 0 || island[i - 1][j] == 0)) { count++; } // check if bottom edge is adjacent to the water if (i == M - 1 || island[i + 1][j] == 0) { count++; } // check if left edge is adjacent to the water if (j == 0 || island[i][j - 1] == 0) { count++; } // check if right edge is adjacent to the water if (j == N - 1 || island[i][j + 1] == 0) { count++; } } } } return count; } int main() { vector<vector<int>> island = { { 0, 1, 1, 1 }, { 1, 1, 0, 0 }, { 1, 1, 1, 0 }, { 0, 1, 0, 0 }, { 0, 1, 1, 1 } }; cout << findPerimeter(island) << endl; return 0; } |
Output:
24
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
class Main { public static int findPerimeter(int[][] island) { // base case if (island.length == 0) { return 0; } int M = island.length; int N = island[0].length; int count = 0; // traverse each cell of the matrix for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { // if the current cell is a land if (island[i][j] == 1) { // check if top edge is adjacent to the water if ((i == 0 || island[i - 1][j] == 0)) { count++; } // check if bottom edge is adjacent to the water if (i == M - 1 || island[i + 1][j] == 0) { count++; } // check if left edge is adjacent to the water if (j == 0 || island[i][j - 1] == 0) { count++; } // check if right edge is adjacent to the water if (j == N - 1 || island[i][j + 1] == 0) { count++; } } } } return count; } public static void main(String[] args) { int[][] island = = { { 0, 1, 1, 1 }, { 1, 1, 0, 0 }, { 1, 1, 1, 0 }, { 0, 1, 0, 0 }, { 0, 1, 1, 1 } }; System.out.println(findPerimeter(island)); } } |
Output:
24
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
def findPerimeter(island): # base case if not island: return 0 M, N = len(island), len(island[0]) count = 0 # traverse each cell of the matrix for i in range(0, M): for j in range(0, N): # if the current cell is a land if island[i][j] == 1: # check if top edge is adjacent to the water if i == 0 or island[i - 1][j] == 0: count = count + 1 # check if bottom edge is adjacent to the water if i == M - 1 or island[i + 1][j] == 0: count = count + 1 # check if left edge is adjacent to the water if j == 0 or island[i][j - 1] == 0: count = count + 1 # check if right edge is adjacent to the water if j == N - 1 or island[i][j + 1] == 0: count = count + 1 return count if __name__ == '__main__': island = [ [0, 1, 1, 1], [1, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0], [0, 1, 1, 1] ] print(findPerimeter(island)) |
Output:
24
The time complexity of the proposed solution is O(M × N), where M and N are dimensions of the matrix, and doesn’t require any extra space.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)