463. Island Perimeter

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.

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:

1. Initialize a perimeter count to 0.
2. Iterate through each cell in the grid.
3. If a cell is land (1), increment the perimeter count by 4 (all possible sides of a single cell).
4. 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.
5. Continue this process for all land cells in the grid.
6. 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:

1. Initiate a Counter for Perimeter: Start with a variable ans, initialized to 0, which will keep track of the island's perimeter.

2. 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:

   1for i in range(m):
   2    for j in range(n):

3. Check for Land Cells: If the current cell grid[i][j] is a land cell (1), increment the perimeter counter by 4:

   1if grid[i][j] == 1:
   2    ans += 4

   This is because a land cell has 4 potential edges contributing to the perimeter.

4. 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:

     1if i < m - 1 and grid[i + 1][j] == 1:
     2    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:

     1if j < n - 1 and grid[i][j + 1] == 1:
     2    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.

5. 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.

6. 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.

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:

1Grid:
21 0 1
31 1 0
40 1 0

Following the steps outlined in the algorithm:

1. Initiate a Counter for Perimeter: Start with ans = 0.

2. 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.

3. Check for Land Cells: We have done this part during our iteration and added 4 to ans for each land cell.

4. 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.

5. Subtract Shared Edges: Subtractions are accounted for when checking for adjacent land.

6. 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

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.