463. Island Perimeter

EasyDepth-First SearchBreadth-First SearchArrayMatrix

Problem Description

In this problem, you are presented with a 2D grid that represents a map, where the value 1 indicates land and the value 0 represents water. The key points about the map are:

There's exactly one island, and it is made up of land cells (1's) that are connected horizontally or vertically.
The surrounding cells outside the grid are water (0's).
There are no "lakes," meaning there are no enclosed areas of water within the island.
Each cell of the grid is a square with a side length of 1.
The dimensions of the grid will not be larger than 100x100.

Your task is to determine and return the perimeter of the island in this grid. Remember that the perimeter counts the boundary that separates land cells from water cells.

Flowchart Walkthrough

Let's utilize the provided algorithm flowchart to determine the appropriate algorithm for solving Leetcode problem 463, Island Perimeter. Follow this step-by-step analysis:

View the Flowchart

Is it a graph?
- Yes: The grid in the problem can be envisaged as a graph, where each cell represents a node. Nodes (cells with value 1) are connected if they are adjacent horizontally or vertically.
Is it a tree?
- No: A tree would not correctly represent the model since multiple separated land blocks (nodes with value 1 that are not connected) can exist, which contradicts the single-connected-component nature of trees.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The relationship between nodes does not involve any direction nor is acyclic in nature; the problem concerns calculating the perimeter of islands on a grid.
Is the problem related to shortest paths?
- No: This problem isn't about finding distances like shortest paths, but rather about calculating the perimeter defined by edges in a graph.
Does the problem involve connectivity?
- Yes: The problem involves determining the boundaries of connected regions (islands of 1s), indicating connectivity concerns.
Is the graph weighted?
- No: There are no weights assigned to edges; the grid is unweighted, as adjacency merely indicates the presence of an island.
Does the problem have small constraints?
- Yes: Generally, problems involving direct grid manipulation, like counting cells or perimeters, are applicable under reasonably small constraints where each cell needs checking.
DFS or backtracking?
- DFS/backtracking: Utilizing Depth First Search (DFS) or backtracking is ideal due to its efficacy in exploring all nodes (cells) connected to a start node within an island, thoroughly useful for edge counting which is necessary for the perimeter calculation.

Hence, following through the flowchart, we ascertain the depth-first search pattern is suitable for efficiently determining the perimeter of each island in the grid.

Intuition

To solve this problem, we need to calculate the total perimeter contributed by each land cell in the grid. Since we're working with a grid that has connected cells horizontally and vertically, each land cell that does not touch another land cell contributes 4 units to the perimeter (as it has four sides).

Here's the intuitive step-by-step approach:

Initialize a perimeter count to 0.
Iterate through each cell in the grid.
If a cell is land (1), increment the perimeter count by 4 (all possible sides of a single cell).
Then, check the adjacent cells:
- If there is a land cell to the right (horizontally adjacent), the shared edge does not contribute to the perimeter, so we subtract 2 from the perimeter count (as it removes one edge from each of the two adjacent land cells).
- Similarly, if there is a land cell below (vertically adjacent), subtract 2 for the shared edge.
Continue this process for all land cells in the grid.
Return the total perimeter count.

This approach works because it dynamically adjusts the perimeter count based on the land cell's adjacency with other land cells, ensuring that shared edges are only counted once.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The solution approach for determining the perimeter of the island adheres to the following algorithmic steps, aligning with the explained intuition:

Initiate a Counter for Perimeter: Start with a variable ans, initialized to 0, which will keep track of the island's perimeter.
Iterate over Grid Cells: Use a nested loop to go through every cell in the grid. Let m be the number of rows and n be the number of columns of the grid:
```
for i in range(m):
    for j in range(n):
```
Check for Land Cells: If the current cell grid[i][j] is a land cell (1), increment the perimeter counter by 4:
```
if grid[i][j] == 1:
    ans += 4
```
This is because a land cell has 4 potential edges contributing to the perimeter.
Check for Adjacent Land: Determine if the land cell has adjacent land cells that would reduce the perimeter:
- To check the cell below the current cell (if it exists and is a land cell), we perform:
```
if i < m - 1 and grid[i + 1][j] == 1:
    ans -= 2
```
  We use the condition i < m - 1 to ensure we're not on the bottom most row before checking the cell below.
- To check the cell to the right of the current cell (if it exists and is a land cell), we perform:
```
if j < n - 1 and grid[i][j + 1] == 1:
    ans -= 2
```
  We use the condition j < n - 1 to ensure we're not on the right most column before checking the cell to the right.
Subtract Shared Edges: The subtraction of 2 from the perimeter ans in the case of adjacent land cells accounts for the fact that each shared edge is part of the perimeter of two adjacent cells. Since this edge cannot be counted twice, we subtract 2 from our total perimeter count — 1 for each of the two cells sharing the edge.
Return Perimeter Count: After the entire grid has been processed, return the calculated perimeter ans.

The algorithm makes use of nested loops to process a 2D matrix, while the main data structure utilized is the 2D list given as input. This approach is straightforward with a linear runtime that corresponds to the size of the grid (O(m*n)), as each cell is visited exactly once.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a simple example to illustrate the solution approach. Consider a 3x3 grid, where 1 represents land and 0 represents water:

Grid:
1 0 1
1 1 0
0 1 0

Following the steps outlined in the algorithm:

Initiate a Counter for Perimeter: Start with ans = 0.
Iterate over Grid Cells: We will examine each cell to determine if it contributes to the perimeter.

First row:

The first cell (0,0) is a 1 (land), so ans += 4 => ans = 4.
The second cell (0,1) is a 0 (water), so no change to ans.
The third cell (0,2) is a 1 (land), so ans += 4 => ans = 8.

Second row:

The first cell (1,0) is a 1 (land). We check the cell above (0,0) which is also a 1. This means we have adjacent land cells, so ans += 4 and ans -= 2 for the shared edge => ans = 10.
The second cell (1,1) is a 1 (land). It's surrounded by land on two sides (above and to the left), so ans += 4 and ans -= 4 (2 for each shared edge) => ans = 10.
The third cell (1,2) is a 0 (water), so no change to ans.

Third row:

The first cell (2,0) is a 0 (water), so no change to ans.
The second cell (2,1) is a 1 (land). It's surrounded by land above only, so ans += 4 and ans -= 2 for the shared edge => ans = 12.
The third cell (2,2) is a 0 (water), so no change to ans.

Check for Land Cells: We have done this part during our iteration and added 4 to ans for each land cell.
Check for Adjacent Land: We have also done this part during our iteration and subtracted 2 from ans for every shared edge with adjacent land.
Subtract Shared Edges: Subtractions are accounted for when checking for adjacent land.
Return Perimeter Count: After processing the entire grid, the total perimeter ans is 12.

Thus, the perimeter of the island in the given grid is 12.

Solution Implementation

1class Solution:
2    def islandPerimeter(self, grid: List[List[int]]) -> int:
3        # Get the number of rows and columns of the grid
4        rows, cols = len(grid), len(grid[0])
5
6        # Initialize perimeter count
7        perimeter = 0
8
9        # Go through each cell in the grid
10        for row in range(rows):
11            for col in range(cols):
12              
13                # If we encounter a land cell
14                if grid[row][col] == 1:
15                    # Add 4 sides to the perimeter
16                    perimeter += 4
17                  
18                    # If there is a land cell below the current one,
19                    # subtract 2 from the perimeter (common side with the bottom cell)
20                    if row < rows - 1 and grid[row + 1][col] == 1:
21                        perimeter -= 2
22                  
23                    # If there is a land cell to the right of the current one,
24                    # subtract 2 from the perimeter (common side with the right cell)
25                    if col < cols - 1 and grid[row][col + 1] == 1:
26                        perimeter -= 2
27      
28        # Return the total perimeter of the island
29        return perimeter
30

1class Solution {
2  
3    // Function to calculate the perimeter of the island.
4    public int islandPerimeter(int[][] grid) {
5        // Initialize perimeter sum to 0.
6        int perimeter = 0;
7        // Get the number of rows in the grid.
8        int rows = grid.length;
9        // Get the number of columns in the grid.
10        int cols = grid[0].length;
11      
12        // Iterate through the grid using nested loops.
13        for (int i = 0; i < rows; i++) {
14            for (int j = 0; j < cols; j++) {
15              
16                // Check if the current cell is land (1 indicates land).
17                if (grid[i][j] == 1) {
18                    // Add 4 for each land cell as it could potentially contribute 4 sides to the perimeter.
19                    perimeter += 4;
20                  
21                    // If there is land directly below the current land, subtract 2 from perimeter count
22                    // (one for the current cell's bottom side and one for the bottom cell's top side).
23                    if (i < rows - 1 && grid[i + 1][j] == 1) {
24                        perimeter -= 2;
25                    }
26                  
27                    // If there is land directly to the right of the current land, subtract 2 from perimeter count
28                    // (one for the current cell's right side and one for the right cell's left side).
29                    if (j < cols - 1 && grid[i][j + 1] == 1) {
30                        perimeter -= 2;
31                    }
32                }
33            }
34        }
35      
36        // Return the total perimeter of the island.
37        return perimeter;
38    }
39}
40

1class Solution {
2public:
3    // Function to calculate the perimeter of islands in a grid.
4    int islandPerimeter(vector<vector<int>>& grid) {
5        // m is the number of rows in the grid.
6        int rowCount = grid.size();
7        // n is the number of columns in the grid.
8        int columnCount = grid[0].size();
9      
10        // Initialize the perimeter result to 0.
11        int perimeter = 0;
12      
13        // Iterate over each cell in the grid.
14        for (int row = 0; row < rowCount; ++row) {
15            for (int column = 0; column < columnCount; ++column) {
16                // Check if the current cell is part of an island.
17                if (grid[row][column] == 1) {
18                    // Each island cell contributes 4 to the perimeter.
19                    perimeter += 4;
20                  
21                    // If the cell below the current one is also part of the island,
22                    // reduce the perimeter by 2 (since two sides are internal and do not contribute to the perimeter).
23                    if (row < rowCount - 1 && grid[row + 1][column] == 1) perimeter -= 2;
24                  
25                    // If the cell to the right of the current one is also part of the island,
26                    // reduce the perimeter by 2 for the same reason.
27                    if (column < columnCount - 1 && grid[row][column + 1] == 1) perimeter -= 2;
28                }
29            }
30        }
31      
32        // Return the total perimeter calculated.
33        return perimeter;
34    }
35};
36

1// Function to calculate the perimeter of islands.
2// The grid is represented by a 2D array where 1 indicates land and 0 indicates water.
3function islandPerimeter(grid: number[][]): number {
4    let height = grid.length,  // The height of the grid
5        width = grid[0].length; // The width of the grid
6
7    let perimeter = 0; // Initialize perimeter counter
8
9    // Iterate over each cell in the grid
10    for (let row = 0; row < height; ++row) {
11        for (let col = 0; col < width; ++col) {
12            let topNeighbor = 0, // Variable to track the top neighbor's value
13                leftNeighbor = 0; // Variable to track the left neighbor's value
14
15            // Check if the top neighbor exists, and if so, get its value
16            if (row > 0) {
17                topNeighbor = grid[row - 1][col];
18            }
19
20            // Check if the left neighbor exists, and if so, get its value
21            if (col > 0) {
22                leftNeighbor = grid[row][col - 1];
23            }
24
25            let currentCell = grid[row][col]; // Current cell value
26
27            // Compare current cell with the top and left cells; increment perimeter accordingly
28            if (currentCell !== topNeighbor) ++perimeter;
29            if (currentCell !== leftNeighbor) ++perimeter;
30        }
31    }
32
33    // Account for the last row and last column edges
34    for (let i = 0; i < height; ++i) {
35        if (grid[i][width - 1] === 1) ++perimeter; // Increment if last column cell is land
36    }
37    for (let j = 0; j < width; ++j) {
38        if (grid[height - 1][j] === 1) ++perimeter; // Increment if last row cell is land
39    }
40
41    return perimeter; // Return the total perimeter of the islands
42}
43

Time and Space Complexity

The time complexity of the given code is O(m * n) where m is the number of rows and n is the number of columns in the grid. This is because there is a nested loop which iterates over each cell in the grid exactly once.

The space complexity of the code is O(1) since it only uses a constant amount of additional space. The variable ans is updated in place and no additional space that scales with the size of the input is allocated.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know