We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Island Perimeter

Number: 463

Difficulty: Easy

Paid? No

Companies: Meta, Oracle, Amazon, Microsoft, Google, Apple, Bloomberg, Yandex, Adobe

Problem Description

Given a 2D grid where 1 represents land and 0 represents water, there is exactly one island (one or more connected 1's in horizontal/vertical directions). The grid is completely surrounded by water. The task is to calculate the perimeter of the island. A cell contributes to the perimeter if its neighbor in any of the four directions (up, down, left, right) is water or lies outside the grid boundaries.

Key Insights

  • Each land cell contributes 4 edges if isolated.
  • For every adjacent pair of land cells (neighbors horizontally or vertically), the shared edge should be subtracted from the total perimeter.
  • Instead of DFS/BFS, we can iterate the grid and check the four neighbors for each land cell.
  • Alternatively, one may use DFS/BFS to visit all connected cells if needed, but an iterative solution is straightforward with O(rows*cols) time complexity.

Space and Time Complexity

Time Complexity: O(n * m), where n is the number of rows and m is the number of columns. Space Complexity: O(1) for the iterative solution (excluding the input storage).

Solution

We iterate through every cell in the grid. For each land cell, we initially add 4 to the perimeter. Then we check its four neighbors (up, down, left, right). For every neighbor that is also land, we subtract 1 from the current cell’s contribution since that side is not exposed. This simple approach ensures that shared borders between adjacent land cells are not over-counted.

Code Solutions

# Python solution for Island Perimeter
def islandPerimeter(grid):
    # Initialize perimeter to 0
    perimeter = 0
    
    # Get number of rows and columns
    rows = len(grid)
    cols = len(grid[0])
    
    # Iterate through each cell in the grid
    for i in range(rows):
        for j in range(cols):
            # Only process if current cell is land
            if grid[i][j] == 1:
                # Each land cell contributes 4 edges initially
                cell_perimeter = 4
                
                # Check if the upper neighbor is also land
                if i > 0 and grid[i-1][j] == 1:
                    cell_perimeter -= 1
                # Check if the lower neighbor is also land
                if i < rows - 1 and grid[i+1][j] == 1:
                    cell_perimeter -= 1
                # Check if the left neighbor is also land
                if j > 0 and grid[i][j-1] == 1:
                    cell_perimeter -= 1
                # Check if the right neighbor is also land
                if j < cols - 1 and grid[i][j+1] == 1:
                    cell_perimeter -= 1
                
                # Add the effective perimeter of the current cell to the overall perimeter
                perimeter += cell_perimeter
                
    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 should be 16
← Back to All Questions