algoadvance

You are given a 2D grid of values representing a map of land (1) and water (0). Each cell is square, and the grid is rectangular. The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

Your task is to calculate the perimeter of the island.

Example:

Input:
grid = [
  [0, 1, 0, 0],
  [1, 1, 1, 0],
  [0, 1, 0, 0],
  [1, 1, 0, 0]
]

Output: 16

Clarifying Questions

  1. What are the constraints on the size of the grid?
    • The grid dimensions can range from 1x1 to 100x100.
  2. Can there be multiple islands?
    • No, there is guaranteed to be exactly one island.
  3. Are diagonal connections counted?
    • No, only horizontal and vertical connections are counted.

Strategy

To calculate the perimeter of the island, we can follow these steps:

  1. Initialize a variable perimeter to store the perimeter length.
  2. Iterate through each cell in the grid.
  3. For each cell that contains land (1):
    • Start with 4 potential sides contributing to the perimeter.
    • Subtract 1 for each adjacent land cell (since these sides are shared).
  4. Return the accumulated perimeter count.

Code

def islandPerimeter(grid):
    rows = len(grid)
    cols = len(grid[0])
    perimeter = 0
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                perimeter += 4  # Start with 4 sides for the land cell
                
                # Check and subtract for adjacent land cells
                if r > 0 and grid[r-1][c] == 1:
                    perimeter -= 1
                if r < rows-1 and grid[r+1][c] == 1:
                    perimeter -= 1
                if c > 0 and grid[r][c-1] == 1:
                    perimeter -= 1
                if c < cols-1 and grid[r][c+1] == 1:
                    perimeter -= 1
    
    return perimeter

# Example usage:
grid = [
  [0, 1, 0, 0],
  [1, 1, 1, 0],
  [0, 1, 0, 0],
  [1, 1, 0, 0]
]
print(islandPerimeter(grid))  # Output: 16

Time Complexity

The time complexity of this solution is (O(m \times n)), where m is the number of rows and n is the number of columns in the grid. This is because we are visiting each cell exactly once to compute the perimeter.

The space complexity is (O(1)) as we are only using a few extra variables and not any additional data structures that grow with the input size.

Try our interview co-pilot at AlgoAdvance.com