Domain 1EasyCORE

Island Perimeter

The problem requires calculating the perimeter of an island in a grid where land cells are represented by `1` and water cells by `0`. The grid is surrounded entirely by water, and there is exactly one island. The island does not contain any lakes, meaning all internal water cells are not connected to the surrounding water.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table

463. Island Perimeter

Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 1
Acceptance rate: 66.8%


Problem Breakdown

The problem requires calculating the perimeter of an island in a grid where land cells are represented by 1 and water cells by 0. The grid is surrounded entirely by water, and there is exactly one island. The island does not contain any lakes, meaning all internal water cells are not connected to the surrounding water.

Inputs:

  • A 2D list (grid) where each element is either 0 (water) or 1 (land).

Outputs:

  • An integer representing the perimeter of the island.

Implicit Constraints and Edge Cases:

  • The grid dimensions are between 1x1 and 100x100.
  • There is exactly one island in the grid.
  • The island is rectangular, with no diagonal connections between land cells.
  • The grid is completely surrounded by water.

Intuition

A brute-force approach would involve checking each cell of the grid to determine if it contributes to the perimeter. However, this approach would be inefficient as it would require examining all four sides of every cell, leading to a time complexity of O(n^2 * 4) = O(n^2), where n is the number of cells in the grid.

A more efficient approach involves iterating through each land cell and checking its neighboring cells. For each land cell, we add 4 to the perimeter initially (since it has four sides). If a neighboring cell is also land, we subtract 1 from the perimeter for each shared side between the two cells. This reduces the number of checks needed and optimizes the solution.

Approach

  1. Initialize a variable perimeter to 0.
  2. Iterate through each cell in the grid using nested loops.
  3. For each land cell (grid[i][j] == 1):
    • Add 4 to the perimeter (since it has four sides).
    • Check the neighboring cells:
      • If the top neighbor is also land, subtract 1 from the perimeter.
      • If the left neighbor is also land, subtract 1 from the perimeter.
  4. Return the final value of perimeter.

Complexity Analysis

  • Time Complexity: O(n * m), where n is the number of rows and m is the number of columns in the grid. We iterate through each cell once.
  • Space Complexity: O(1). We use a constant amount of extra space regardless of the input size.

Solution

def islandPerimeter(grid):
    perimeter = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                # Start with 4 sides
                perimeter += 4
                
                # Subtract 1 for each adjacent land cell
                if i > 0 and grid[i - 1][j] == 1:  # Check top neighbor
                    perimeter -= 1
                if j > 0 and grid[i][j - 1] == 1:  # Check left neighbor
                    perimeter -= 1
    
    return perimeter

Edge Cases Handled

  • Single Cell Island: If the grid contains only one land cell, the perimeter is correctly calculated as 4.
  • Island with No Neighbors: If the island has no adjacent land cells (e.g., a single column or row of land), the perimeter is correctly calculated as the sum of all four sides.
  • Grid with Multiple Rows and Columns: The solution handles grids of varying sizes, ensuring that each cell’s contribution to the perimeter is accurately computed.

The provided solution is correct, efficient, and clear. It adheres to the problem constraints and handles all edge cases appropriately.