This solution seeks to find the perimeter of an island in a grid. The problem considers a grid where each cell represents land (1) or water (0). In addition, the function calculates the total perimeter of the connected land (island) in the grid.
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
"""
Calculates the perimeter of the island in a 2D grid.
Args:
grid (List[List[int]]): A 2D list representing the grid, where grid[i][j] is 1 for land and 0 for water.
Returns:
int: The total perimeter length of the island in the grid.
"""
visited = set() # Set to keep track of visited cells
def dfs(row: int, col: int) -> int:
"""
Performs a Depth-First Search (DFS) traversal to explore the island and calculate its perimeter.
Args:
row (int): The row index of the current cell.
col (int): The column index of the current cell.
Returns:
int: The perimeter contribution of the current cell (1 if on the edge, 0 otherwise).
"""
if (row >= len(grid) or col >= len(grid[0]) or # Check for out-of-bounds
row < 0 or col < 0 or
grid[row][col] == 0): # Check for water cell
return 1
if (row, col) in visited: # Skip already visited cell
return 0
visited.add((row, col)) # Mark cell as visited
perimeter = dfs(row, col + 1) # Explore right neighbor
perimeter += dfs(row, col - 1) # Explore left neighbor
perimeter += dfs(row + 1, col) # Explore down neighbor
perimeter += dfs(row - 1, col) # Explore up neighbor
return perimeter
# Start DFS from any land cell to find the island
for row in range(len(grid)):
for col in range(len(grid[0])):
if grid[row][col] == 1:
return dfs(row, col)
# If no land is found, the perimeter is 0
return 0
The thought process behind this solution is to calculate the perimeter of an island represented in a 2D grid using Depth-First Search (DFS). Here’s a detailed breakdown of the logic and reasoning:
- Island Definition: The island is represented by cells with value
1, and water is represented by cells with value0. - Each land cell contributes to the perimeter if it is adjacent to a water cell or the boundary of the grid. Specifically:
- A cell at the grid boundary contributes an edge to the perimeter.
- A land cell adjacent to a water cell contributes an edge to the perimeter for each water cell it touches.
- Traversal Strategy: Use Depth-First Search (DFS) to traverse the island, ensuring that each cell is visited only once. DFS is chosen because it effectively explores all connected components of the island.
- Edge Calculation: For each land cell, check its four neighbors (up, down, left, right). If a neighbor is out of bounds or a water cell, it contributes to the perimeter.
- Tracking Visited Cells: Use a set to track visited cells to avoid redundant calculations and infinite loops.
- Loop through each cell in the grid. Start DFS from the first land cell found, which initiates the traversal and perimeter calculation for the entire island.
Time Complexity
The time complexity of the solution is determined by how many times each cell in the grid is visited and processed.
Initial Loop: The initial double loop to find the first land cell runs in O(m by n), where m is the number of rows and n is the number of columns in the grid.
DFS Traversal: Each land cell (with value 1) is visited exactly once, and for each land cell, the algorithm checks its four neighbors. Thus, the DFS traversal will also run in O(m by n) time in the worst case, where every cell in the grid island.
Space Complexity
The space complexity is influenced by the storage needed for the visited set and the call stack for the recursive DFS.
Visited Set: In the worst case, the visited set could store every cell in the grid if all cells are land. Thus, the space required for the visited set is O(m by n).
DFS Call Stack: The depth of the recursion stack for DFS can go up to O(m by n) in the worst case, where the grid forms a single narrow strip of land.
Unit Tests
Here's the tests to examine the accuracy & robustness of this solution.
class TestislandPerimeter(unittest.TestCase):
def setUp(self):
self.sol = Solution()
def test_islandPerimeter(self):
grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
self.assertEqual(self.sol.islandPerimeter(grid), 16)
def test_empty_grid(self):
"""Tests the function with an empty grid."""
solution = Solution()
grid = []
result = solution.islandPerimeter(grid)
self.assertEqual(result, 0)
def test_single_cell_island(self):
"""Tests the function with a grid containing a single land cell."""
solution = Solution()
grid = [[1]]
result = solution.islandPerimeter(grid)
self.assertEqual(result, 4) # Perimeter of a single cell
def test_horizontal_island(self):
"""Tests the function with a horizontal island of connected land cells."""
solution = Solution()
grid = [[1, 1, 1, 1]]
result = solution.islandPerimeter(grid)
self.assertEqual(result, 10) # 3 edges shared internally
def test_vertical_island(self):
"""Tests the function with a vertical island of connected land cells."""
solution = Solution()
grid = [[1],
[1],
[1]]
result = solution.islandPerimeter(grid)
self.assertEqual(result, 8) #
def test_complex_island(self):
"""Tests the function with a complex island with various shapes."""
solution = Solution()
grid = [[0, 1, 0, 0],
[1, 1, 1, 0],
[0, 1, 0, 1],
[0, 0, 0, 0]]
result = solution.islandPerimeter(grid)
# todo
# one island is 12 while another is 4
self.assertEqual(result, 16)
def test_no_island(self):
"""Tests the function with a grid containing only water cells."""
solution = Solution()
grid = [[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
result = solution.islandPerimeter(grid)
self.assertEqual(result, 0)
if __name__ == '__main__':
unittest.main()