# Island Perimeter
**Difficulty:** EASY
[External](https://leetcode.com/problems/island-perimeter)
Canonical: https://scaleengineer.com/dsa/problems/island-perimeter
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
**Companies:** [Cadence](https://scaleengineer.com/companies/cadence)
---
## Problem
You are given `row x col` `grid` representing a map where `grid[i][j] = 1` represents land and `grid[i][j] = 0` represents water.

Grid cells are connected **horizontally/vertically** (not diagonally). The `grid` is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1\. The grid is rectangular, width and height don't exceed 100\. Determine the perimeter of the island.

**Example 1:**

![](https://assets.glich.co/dsa/island-perimeter/image0.png) 

**Input:** grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
**Output:** 16
**Explanation:** The perimeter is the 16 yellow stripes in the image above.

**Example 2:**

**Input:** grid = [[1]]
**Output:** 4

**Example 3:**

**Input:** grid = [[1,0]]
**Output:** 4

**Constraints:**

* `row == grid.length`
* `col == grid[i].length`
* `1 <= row, col <= 100`
* `grid[i][j]` is `0` or `1`.
* There is exactly one island in `grid`.

# Approaches
## Brute-Force Iteration
This straightforward approach iterates through every cell of the grid. For each land cell, it checks its four neighbors (up, down, left, right). If a neighbor is a water cell or is outside the grid boundary, it contributes one unit to the total perimeter.
**Time:** O(R * C), where R is the number of rows and C is the number of columns. We must visit every cell in the grid. · **Space:** O(1), as no extra space proportional to the input size is used.
**Pros:** Very intuitive and easy to understand.; Directly models the definition of a perimeter in this context.
**Cons:** Performs more checks than necessary. For each land cell, it looks at all four neighbors, leading to redundant considerations of shared borders.
### Explanation
The algorithm initializes a perimeter count to zero. It then scans the entire grid cell by cell. When it finds a land cell (value `1`), it directly counts the exposed sides. For a land cell at `(r, c)`, we check its top, bottom, left, and right sides. A side is exposed and contributes to the perimeter if the adjacent cell in that direction is either water (`0`) or off the grid. We sum these contributions for all land cells to get the final perimeter.

```java
class Solution {
    public int islandPerimeter(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int perimeter = 0;
        int rows = grid.length;
        int cols = grid[0].length;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    // Check top
                    if (r == 0 || grid[r - 1][c] == 0) {
                        perimeter++;
                    }
                    // Check bottom
                    if (r == rows - 1 || grid[r + 1][c] == 0) {
                        perimeter++;
                    }
                    // Check left
                    if (c == 0 || grid[r][c - 1] == 0) {
                        perimeter++;
                    }
                    // Check right
                    if (c == cols - 1 || grid[r][c + 1] == 0) {
                        perimeter++;
                    }
                }
            }
        }
        return perimeter;
    }
}
```
### Algorithm
- Initialize a variable `perimeter` to 0.
- Get the dimensions of the grid, `rows` and `cols`.
- Iterate through each cell of the grid using nested loops, with `r` from `0` to `rows-1` and `c` from `0` to `cols-1`.
- If the current cell `grid[r][c]` is a land cell (value `1`):
  - Check the cell above: If `r` is `0` (top boundary) or `grid[r-1][c]` is `0` (water), increment `perimeter`.
  - Check the cell below: If `r` is `rows-1` (bottom boundary) or `grid[r+1][c]` is `0`, increment `perimeter`.
  - Check the cell to the left: If `c` is `0` (left boundary) or `grid[r][c-1]` is `0`, increment `perimeter`.
  - Check the cell to the right: If `c` is `cols-1` (right boundary) or `grid[r][c+1]` is `0`, increment `perimeter`.
- After iterating through all cells, return the final `perimeter` value.

## Optimized Iteration by Counting Neighbors
This is a more efficient approach that avoids redundant checks. The core idea is that each land cell contributes 4 to the perimeter, and each shared border between two adjacent land cells subtracts 2 from the total. By iterating through the grid and only counting neighbors in two directions (e.g., right and down), we can calculate the total perimeter efficiently.
**Time:** O(R * C), where R is the number of rows and C is the number of columns. The grid is traversed once. · **Space:** O(1), as only a few variables are used for counting.
**Pros:** More efficient in practice due to fewer checks per cell (at most 2 neighbor checks instead of 4).; Avoids redundant computations by counting each shared border only once.; Elegant mathematical formulation.
**Cons:** The logic might be slightly less direct to grasp initially compared to the brute-force method.
### Explanation
The logic behind this approach is that each land cell initially contributes 4 sides to the perimeter. However, whenever two land cells are adjacent, they share a border. This shared border is internal to the island and should not be part of the perimeter. Since each shared border involves two cells, it removes two sides from the total potential perimeter (one from each cell). To implement this, we iterate through the grid once. We count the total number of land cells. To avoid double-counting shared borders, we only check for adjacent land cells in two directions from each cell: to the right and down. After iterating through the grid, we apply the formula `(total land cells * 4) - (total shared borders * 2)` to get the final result.

```java
class Solution {
    public int islandPerimeter(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int landCells = 0;
        int sharedBorders = 0;
        int rows = grid.length;
        int cols = grid[0].length;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    landCells++;
                    // Count shared border with the right neighbor
                    if (c < cols - 1 && grid[r][c + 1] == 1) {
                        sharedBorders++;
                    }
                    // Count shared border with the bottom neighbor
                    if (r < rows - 1 && grid[r + 1][c] == 1) {
                        sharedBorders++;
                    }
                }
            }
        }
        return landCells * 4 - sharedBorders * 2;
    }
}
```
### Algorithm
- Initialize `landCells = 0` and `sharedBorders = 0`.
- Get the grid dimensions `rows` and `cols`.
- Loop through each row `r` from `0` to `rows - 1`.
- Loop through each column `c` from `0` to `cols - 1`.
- If `grid[r][c]` is `1` (land):
  - Increment `landCells`.
  - Check Right: If `c + 1 < cols` and `grid[r][c+1]` is `1`, increment `sharedBorders`.
  - Check Down: If `r + 1 < rows` and `grid[r+1][c]` is `1`, increment `sharedBorders`.
- Return the result of the formula `landCells * 4 - sharedBorders * 2`.

# Solutions
### Java

```java
class Solution {
public
  int islandPerimeter(int[][] grid) {
    int ans = 0;
    int m = grid.length;
    int n = grid[0].length;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (grid[i][j] == 1) {
          ans += 4;
          if (i < m - 1 && grid[i + 1][j] == 1) {
            ans -= 2;
          }
          if (j < n - 1 && grid[i][j + 1] == 1) {
            ans -= 2;
          }
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int islandPerimeter(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1) {
          ans += 4;
          if (i < m - 1 && grid[i + 1][j] == 1)
            ans -= 2;
          if (j < n - 1 && grid[i][j + 1] == 1)
            ans -= 2;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) ans = 0 for i in range(m): for j in range(n): if grid[i][j] == 1: ans += 4 if i < m - 1 and grid[i + 1][j] == 1: ans -= 2 if j < n - 1 and grid[i][j + 1] == 1: ans -= 2 return ans

```