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.