Leetcode 463 Island Perimeter Solved

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.

The Island Perimeter problem is a classic 2D array problem. This problem is asking you to find the perimeter of the island, which is a region of connected land cells in a rectangular grid. Each cell in the grid can either be land (represented by the value 1) or water (represented by the value 0).

The island doesn’t have any “lakes”, meaning that all of the water cells inside the island are connected to the water cells that surround the island. This means that the island will have a single boundary that is formed by the land cells that are adjacent to water cells.

To solve this problem, you’ll need to iterate over each cell in the grid and check if it’s a land cell. If it is a land cell, you’ll need to check if it has any adjacent water cells (i.e., cells with a value of 0) to determine if it contributes to the perimeter of the island.

For example, consider the following 5×5 grid:

Copy code0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0

The island in this grid is the region of connected land cells in the center of the grid. To compute the perimeter of the island, you would iterate over each land cell and check if it has any adjacent water cells:

• The land cell at (1, 1) has three adjacent water cells, so it contributes 3 to the perimeter.
• The land cell at (1, 2) has two adjacent water cells, so it contributes 2 to the perimeter.
• The land cell at (1, 3) has three adjacent water cells, so it contributes 3 to the perimeter.
• The land cell at (2, 1) has two adjacent water cells, so it contributes 2 to the perimeter.
• The land cell at (2, 3) has two adjacent water cells, so it contributes 2 to the perimeter.
• The land cell at (3, 1) has three adjacent water cells, so it contributes 3 to the perimeter.
• The land cell at (3, 2) does not have any adjacent water cells, so it does not contribute to the perimeter.
• The land cell at (3, 3) has three adjacent water cells, so it contributes 3 to the perimeter.
• The land cell at (4, 1) has two adjacent water cells, so it contributes 2 to the perimeter.
• The land cell at (4, 2) has two adjacent water cells, so it contributes 2 to the perimeter.
• The land cell at (4, 3) has two adjacent water cells, so it contributes 2 to the perimeter.

Adding up all of the contributions from the land cells, we get a total perimeter of 20.

We can solve the problem using multiple approaches, In this article, we will explain three approaches that you can use in your interview.

Approach 1: Counting Boundaries

In this approach, we will count the boundaries around each land cell to compute the total perimeter of the island.

1. Iterate over each cell in the grid.
2. If the current cell is a land cell (i.e., has a value of 1), count the number of adjacent water cells (i.e., cells with a value of 0) that are up, down, left, or right of the current cell.
3. Add the number of adjacent water cells to a running total of the perimeter.
4. Return the total perimeter once all cells have been processed.

Here’s the pseudocode for this approach:

function islandPerimeter(grid):
    perimeter = 0
    for i from 0 to grid.length-1:
        for j from 0 to grid[i].length-1:
            if grid[i][j] == 1:
                # count adjacent water cells
                count = 0
                if i == 0 or grid[i-1][j] == 0:
                    count += 1
                if j == 0 or grid[i][j-1] == 0:
                    count += 1
                if i == grid.length-1 or grid[i+1][j] == 0:
                    count += 1
                if j == grid[i].length-1 or grid[i][j+1] == 0:
                    count += 1
                # add to perimeter
                perimeter += count
    return perimeter

Explanation:

The function islandPerimeter takes a rectangular grid as input and returns the perimeter of the island in the grid. We initialize the variable perimeter to 0, and then iterate over each cell in the grid using two nested for loops.

For each land cell (i.e., a cell with a value of 1), we count the number of adjacent water cells by checking the values of the four neighboring cells (up, down, left, and right). If a neighboring cell has a value of 0, we increment the count.

Once we’ve counted the adjacent water cells, we add the count to the running total of the perimeter. Once all cells have been processed, we return the total perimeter.

Approach 2: Tracing Boundaries

In this approach, we will trace the boundary of the island by following the edges between land and water cells.

1. Iterate over each cell in the grid until a land cell is found.
2. From the starting land cell, follow the edge of the island by moving to adjacent land cells.
3. When an edge cell (i.e., a land cell with at least one adjacent water cell) is reached, add the length of the edge to the perimeter and continue tracing the boundary in the same direction.
4. Stop tracing the boundary when the starting land cell is reached again.
5. Repeat steps 1-4 until all land cells have been processed.
6. Return the total perimeter once all land cells have been processed.

Here’s the pseudocode for this approach:

function islandPerimeter(grid):
    perimeter = 0
    visited = set()
    for i from 0 to grid.length-1:
        for j from 0 to grid[i].length-1:
            if grid[i][j] == 1 and (i, j) not in visited:
                # trace boundary
                stack = [(i, j)]
                length = 0
                while stack:
                    x, y = stack.pop()
                    if (x, y) in visited:
                        continue                visited.add((x, y))
                # check neighbors
                if x == 0 or grid[x-1][y] == 0:
                    length += 1
                elif (x-1, y) not in visited:
                    stack.append((x-1, y))
                if y == 0 or grid[x][y-1] == 0:
                    length += 1
                elif (x, y-1) not in visited:
                    stack.append((x, y-1))
                if x == len(grid)-1 or grid[x+1][y] == 0:
                    length += 1
                elif (x+1, y) not in visited:
                    stack.append((x+1, y))
                if y == len(grid[x])-1 or grid[x][y+1] == 0:
                    length += 1
                elif (x, y+1) not in visited:
                    stack.append((x, y+1))
            # add to perimeter
            perimeter += length
return perimeter

In this approach, we start by finding a land cell in the grid that hasn’t been visited yet. We then trace the boundary of the island by following the edges between land and water cells.

We start at the current land cell and use a stack to keep track of the cells that we need to visit next. We initialize a variable called length to 0, which will keep track of the length of the boundary that we’ve traced so far.

We enter a while loop that runs as long as the stack is not empty. In each iteration of the loop, we pop the top cell from the stack and check if it has already been visited. If it has been visited, we skip it and move on to the next cell in the stack.

If the current cell hasn’t been visited yet, we mark it as visited and check its four neighboring cells. If a neighboring cell is a water cell, we increment the length of the boundary by 1. If a neighboring cell is a land cell and hasn’t been visited yet, we add it to the stack so that we can visit it later.

Once we’ve finished tracing the boundary of the island starting from the current land cell, we add the length of the boundary to the running total of the perimeter.

We then repeat the same process for each unvisited land cell in the grid. Once we’ve processed all land cells in the grid, we return the total perimeter of the island, which is the sum of the lengths of all the edges that we traced.

This approach is based on the idea that the perimeter of the island is the sum of the lengths of all the edges between land and water cells. By tracing these edges starting from each unvisited land cell, we can compute the total perimeter of the island.

Approach 3: Flood Fill Algorithm

In this approach, we use a variation of the flood fill algorithm to determine the perimeter of the island. The flood fill algorithm is a technique used to explore connected regions of a grid.

1. Iterate over each cell in the grid until a land cell is found.
2. Call the flood fill function on the starting land cell.
3. In the flood fill function, mark the current cell as visited and increment the perimeter by 4 (since each land cell has a perimeter of 4).
4. Recursively call the flood fill function on each neighboring land cell that hasn’t been visited yet.
5. If a neighboring cell has already been visited, decrement the perimeter by 2 (since the shared edge between two adjacent land cells only counts once).
6. Repeat steps 2-5 until all land cells have been processed.
7. Return the total perimeter once all land cells have been processed.

Here’s the pseudocode for this approach:

function islandPerimeter(grid):
    perimeter = 0
    visited = set()
    for i from 0 to grid.length-1:
        for j from 0 to grid[i].length-1:
            if grid[i][j] == 1 and (i, j) not in visited:
                # call flood fill function
                perimeter += floodFill(grid, visited, i, j)
    return perimeter

function floodFill(grid, visited, i, j):
    if (i, j) in visited or grid[i][j] == 0:
        return 0
    visited.add((i, j))
    perimeter = 4
    if i > 0:
        perimeter -= floodFill(grid, visited, i-1, j)
    if j > 0:
        perimeter -= floodFill(grid, visited, i, j-1)
    if i < len(grid)-1:
        perimeter -= floodFill(grid, visited, i+1, j)
    if j < len(grid[i])-1:
        perimeter -= floodFill(grid, visited, i, j+1)
    return perimeter

Explanation:

The function islandPerimeter takes a rectangular grid as input and returns the perimeter of the island in the grid. We initialize the variable perimeter to 0 and create a set called visited to keep track of the cells that have already been processed.

We then iterate over each cell in the grid using two nested for loops. For each land cell that hasn’t been visited yet, we call the floodFill function to explore the connected region of land cells.

In the floodFill function, we first check if the current cell has already been visited or if it’s a water cell. If either of these conditions is true, we return 0 (since the current cell doesn’t contribute to the perimeter).

If the current cell is a land cell that hasn’t been visited yet, we mark it as visited and add 4 to the perimeter (since each land cell has a perimeter of 4).

We then recursively call the floodFill function on each neighboring land cell that hasn’t been visited yet. If a neighboring cell has already been visited, we decrement the perimeter by 2 (since the shared edge between two adjacent land cells only counts once).

Once all neighboring cells have been processed, we return the total perimeter of the connected region of land cells. This value is added to the perimeter of the island in the islandPerimeter function.

Once all land cells have been processed, we return the total perimeter of the island.

Python Solution for Island Perimeter:

def islandPerimeter(grid):
    perimeter = 0
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if grid[i][j] == 1:
                perimeter += 4
                if i > 0 and grid[i-1][j] == 1:
                    perimeter -= 2
                if j > 0 and grid[i][j-1] == 1:
                    perimeter -= 2
    return perimeter

Ruby Solution for Island Perimeter:

def island_perimeter(grid)
    perimeter = 0
    grid.each_with_index do |row, i|
        row.each_with_index do |cell, j|
            if cell == 1
                perimeter += 4
                if i > 0 && grid[i-1][j] == 1
                    perimeter -= 2
                end
                if j > 0 && grid[i][j-1] == 1
                    perimeter -= 2
                end
            end
        end
    end
    return perimeter
end

Java Solution for Island Perimeter:

public int islandPerimeter(int[][] grid) {
    int perimeter = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[i].length; j++) {
            if (grid[i][j] == 1) {
                perimeter += 4;
                if (i > 0 && grid[i-1][j] == 1) {
                    perimeter -= 2;
                }
                if (j > 0 && grid[i][j-1] == 1) {
                    perimeter -= 2;
                }
            }
        }
    }
    return perimeter;
}

JavaScript Solution for Island Perimeter:

function islandPerimeter(grid) {
    let perimeter = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j] === 1) {
                perimeter += 4;
                if (i > 0 && grid[i-1][j] === 1) {
                    perimeter -= 2;
                }
                if (j > 0 && grid[i][j-1] === 1) {
                    perimeter -= 2;
                }
            }
        }
    }
    return perimeter;
}