Leetcode 463. Island Perimeter
Problem Explanation
The task is to determine the perimeter of an island that's represented by 1s inside a two-dimensional grid. Constants 0 and 1 represent water and land (island), respectively. Grid cells are connected horizontally and vertically but not diagonally. The grid is surrounded by water. There is no water within the island. The aim is to calculate the perimeter of the island.
Let's walk through the example:
Grid:
1[[0,1,0,0], 2 [1,1,1,0], 3 [0,1,0,0], 4 [1,1,0,0]]
Here, the island is represented by 1's. For each grid cell with a 1, if we were to draw a square around it, it would contribute 4 units to the perimeter. The reduction in perimeter occurs when islands (1's) have neighbors. The perimeter reduces on account of shared edges.
Approach
Iterate through each cell in the grid. When encountering a 1 (land cell), add 4 to the perimeter. Then, check if this cell has a neighbor above or to the left of it. If Yes, these are shared edges and for each shared edge, the perimeter reduces by 2 (both for this cell and neighbour cell). So, for each neighbor, subtract 2 from the perimeter.
This simple algorithm will give us a correct calculation of the island's perimeter.
Python Solution
1 2python 3class Solution: 4 def islandPerimeter(self, grid): 5 islands = 0 6 neighbors = 0 7 8 for i in range(len(grid)): 9 for j in range(len(grid[i])): 10 if grid[i][j] == 1: 11 islands += 1 12 if i > 0 and grid[i - 1][j] == 1: 13 neighbors += 1 14 if j > 0 and grid[i][j - 1] == 1: 15 neighbors += 1 16 return islands * 4 - neighbors * 2
Java Solution
1 2java 3class Solution { 4 public int islandPerimeter(int[][] grid) { 5 int islands = 0, neighbors = 0; 6 for (int i = 0; i < grid.length; i++) { 7 for(int j=0; j<grid[i].length;j++) 8 if(grid[i][j] == 1) 9 { 10 islands++; 11 if(i>0 && grid[i-1][j] == 1) neighbors++; 12 if(j>0 && grid[i][j-1]==1) neighbors++; 13 } 14 return islands*4 - neighbors*2; 15 } 16}
JavaScript Solution
1 2javascript 3var islandPerimeter = function(grid) { 4 var islands = 0; 5 var neighbors = 0; 6 7 for(var i=0; i<grid.length; i++) 8 for(var j=0; j<grid[i].length; j++) 9 if(grid[i][j]===1) 10 { 11 islands++; 12 if(i>0 && grid[i-1][j]===1) neighbors++; 13 if(j>0 && grid[i][j-1]===1) neighbors++; 14 } 15 return islands*4 - neighbors*2; 16};
C++ Solution
1 2cpp 3class Solution { 4public: 5 int islandPerimeter(vector<vector<int>>& grid) { 6 int islands = 0, neighbors = 0; 7 8 for (int i = 0; i < grid.size(); i++) 9 for(int j=0; j<grid[i].size();j++) 10 if(grid[i][j] == 1) 11 { 12 islands++; 13 if(i>0 && grid[i-1][j] == 1) neighbors++; 14 if(j>0 && grid[i][j-1]==1) neighbors++; 15 } 16 return islands*4 - neighbors*2; 17 } 18};
C# Solution
1
2csharp
3public class Solution {
4 public int IslandPerimeter(int[][] grid) {
5 int islands = 0, neighbors = 0;
6
7 for(int i=0; i<grid.Length; i++)
8 for(int j=0; j<grid[i].Length; j++)
9 if(grid[i][j] == 1)
10 {
11 islands++;
12 if(i>0 && grid[i-1][j] == 1) neighbors++;
13 if(j>0 && grid[i][j-1] == 1) neighbors++;
14 }
15 return islands * 4 - neighbors * 2;
16 }
17}
In all language solutions, The loops iterate over every cell of the grid and check whether it is an Island or not. If yes, the island count is incremented and if there are neighbours (only up and left to eliminate duplicate edge counting) the neighbour count is incremented. At the end, return the total perimeter which is calculated as per the approach.## JavaScript Solution Explanation
The JavaScript solution uses a definition statement to create a function named islandPerimeter
that takes a grid as an input argument. This grid is made up of an array of arrays where each subarray represents a row from the grid. The function contains two variable declarations, islands
and neighbors
, initialized to 0.
Two nested for-loops are used to iterate through each cell in the grid. When it encounters a 1 (island), it increments the islands
counter by 1.
After this, two conditional statements check if the current cell has a neighbor above or to the left. This is determined by checking if the cells at indices [i-1
][j] (cell above the current cell) and [i][j-1
] (cell to the left of the current cell) are islands (1s). If a neighbor is found, the neighbors
counter is incremented by 1.
Finally, it returns the result of the expression islands * 4 - neighbors * 2
, which calculates the island's perimeter.
Java Solution Explanation
The Java solution is very similar to the JavaScript solution. It defines a method named islandPerimeter
that takes a 2D array grid
as a parameter. This method uses two integer variables islands
and neighbors
, both set to 0.
Two nested for-loops iterate over each cell in the given grid and increase the islands
counter by one if an island (1) is detected.
Two conditional statements then check if the current cell has a neighbor above or to the left and increments the neighbors
counter by one if true.
Finally, the perimeter of the island is computed using the formula islands * 4 - neighbors * 2
and returned by the method.
Python Solution Explanation
The Python solution defines a class Solution
that includes a method islandPerimeter
. This method takes a list of lists grid
as a parameter. It uses two variables islands
and neighbors
which are both initialized to 0.
It uses nested for-loops to iterate over each cell in the grid. If the cell is an island (the value of the cell is 1), the islands
counter is increased by one.
Then, the script checks whether the current cell has a neighbor above (grid[i - 1][j] == 1
) or to the left (grid[i][j - 1] == 1
). If these conditions are fulfilled, the neighbors
counter is increased by one.
Finally, the method returns the perimeter of the island calculated by the formula islands * 4 - neighbors * 2
.
All solutions operate on the same underlying logic and perform similar operations tailored to their individual language's syntax and conventions.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.