Problem Description
You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water. 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. Determine the perimeter of the island.
Key Insights
- Each land cell contributes up to 4 to the perimeter.
- The actual contribution to the perimeter from each cell is reduced by the number of neighboring land cells (up, down, left, right).
- The grid is guaranteed to contain exactly one island, simplifying our approach to perimeter calculation.
Space and Time Complexity
Time Complexity: O(n * m), where n is the number of rows and m is the number of columns in the grid. Each cell is processed once. Space Complexity: O(1), as we are using a few variables for counting the perimeter and not using any additional data structures that scale with input size.
Solution
To solve the problem, we will iterate through each cell in the grid. For each land cell (grid[i][j]), we will check its four possible neighbors (up, down, left, right). For each neighbor that is also land, we will decrease the perimeter contribution for that side. The total perimeter is initialized to 0 and incremented by 4 for each land cell, with decrements for each adjacent land neighbor.