Island Perimeter Leetcode Problem 463 [Python Solution]
Island Perimeter is an interesting problem that falls under the category of graph-related challenges on LeetCode.
It's considered an easy problem, but it offers a great opportunity to delve into the depths of graph algorithms.
In this blog post, we'll explore the problem, discuss various approaches to solve it, provide Python code solutions, analyze time and space complexities, and share the reasoning behind our chosen approach.
Let's get started!
Problem Overview
Question:
You are given an 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 and vertically (not diagonally).
The grid is completely surrounded by water, and there is exactly one island, which consists of 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 a side length of 1. The grid is rectangular, with width and height not exceeding 100. Determine the perimeter of the island.
Example 1:
Input: grid = [[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]
Output: 16
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 the grid.
Now that we understand the problem statement, let's dive into solving it.
Understanding Island Perimeter Constraints
Before we jump into solving the problem, it's crucial to understand the constraints.
These constraints provide insights into how we can approach the problem:
- The grid represents land (
1) and water (0). - The grid is surrounded by water, and there is exactly one island, which is a group of connected land cells.
- We need to calculate the perimeter of this island.
- The island is connected horizontally and vertically.
- The grid is rectangular and has dimensions not exceeding 100×100. With these constraints in mind, we can proceed to explore potential solutions to the problem.
Island Perimeter LeetCode Problem Solution
To calculate the perimeter of the island, we can employ a depth-first search (DFS) approach.
We'll start from a land cell, and at each step, we'll explore adjacent land cells while marking them as visited to avoid revisiting.
When we encounter the boundary of the grid or a water cell, we'll add 1 to the perimeter.
The final sum of increments will represent the island's perimeter.
1. Bruteforce Approach
We can begin with a brute-force approach that explores every cell in the grid, checking its surroundings.
This approach involves the following steps:
def islandPerimeter(self, grid):
def dfs(i, j):
if i >= len(grid) or j >= len(grid[0]) or i < 0 or j < 0 or grid[i][j] == 0:
return 1
if (i, j) in visit:
return 0
visit.add((i, j))
perim = dfs(i, j + 1)
perim += dfs(i + 1, j)
perim += dfs(i, j - 1)
perim += dfs(i - 1, j)
return perim
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]:
return dfs(i, j)
In this code, we define a dfs function, which performs the depth-first search.
It checks for boundary conditions and marks visited cells.
For each land cell encountered, it explores adjacent cells in four directions (right, down, left, and up).
It returns 1 for perimeter contribution and 0 for previously visited cells.
The main function iterates through the entire grid, identifying land cells (where grid[i][j] == 1) and initiating the DFS process.
Finally, the total perimeter is returned.
Efficient Approach with DFS
While the brute-force approach works, it can be optimized.
The efficient approach involves utilizing DFS but without the need to explicitly return 0 for visited cells.
Here's a more streamlined Python solution:
def islandPerimeter(self, grid):
def dfs(i, j):
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:
return 1
if grid[i][j] == -1:
return 0
grid[i][j] = -1
perim = 0
perim += dfs(i + 1, j)
perim += dfs(i - 1, j)
perim += dfs(i, j + 1)
perim += dfs(i, j - 1)
return perim
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
return dfs(i, j)
In this optimized solution, we maintain the DFS structure, but instead of using a visit set to track visited cells, we modify the original grid.
We set visited cells to -1 to prevent revisiting.
The function dfs now returns 1 for perimeter contribution and 0 for cells marked as -1. The main function iterates through the grid, initiates DFS from land cells, and modifies the grid accordingly.
Time and Space Complexity
Now that we've explored both the brute-force and efficient approaches, let's analyze their time and space complexities.
Time Complexity
Both solutions have a time complexity of O(row x col), where "row" represents the number of rows in the grid, and "col" represents the number of columns.
This is because we visit each cell only once during the depth-first search, and there are row x col cells in the grid.
Space Complexity
The space complexity for both solutions is O(1), meaning they use a constant amount of extra space.
This is because we do not employ additional data structures that grow with the input size.
The space used is mainly for function call stack frames and loop variables.
Reasoning Behind Our Approach
The efficient DFS approach offers an optimized solution to the Island Perimeter problem.
Here's the reasoning behind our approach:
-
Depth-First Search (DFS): We choose DFS as our algorithm of choice because it allows us to explore all connected land cells efficiently while keeping track of visited cells.
-
Grid Modification: Instead of maintaining a separate set to track visited cells, we modify the original grid.
This not only reduces space complexity but also simplifies the code.
- Perimeter Calculation: We calculate the perimeter as we explore the island cells
.
For each visited cell, we contribute 1 to the perimeter.
We avoid revisiting cells that have been marked as visited by setting their value to -1.
- Efficiency: By utilizing grid modification, we optimize the DFS process.
The code is concise and efficient, offering a linear time complexity.
Related Interview Questions By Company:
Related Interview Questions By Difficulty:
Related Interview Questions By Category:
Conclusion
In this blog post, we tackled the LeetCode problem Island Perimeter We provided a clear problem overview, discussed the constraints, and presented both a brute-force approach and an efficient DFS-based solution.
Our optimized approach utilizes grid modification to streamline the depth-first search process, resulting in an efficient solution with a time complexity of O(row x col).
We hope this guide helps you understand the problem and how to approach it.
Feel free to comment, ask questions, make suggestions, and share this content with others.
Happy coding!
