You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.
Grid cells are connected horizontally/vertically (not diagonally). 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. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.
Example 1:
Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]] Output: 16 Explanation: The perimeter is the 16 yellow stripes in the image above.
Example 2:
Input: grid = [[1]] Output: 4
Example 3:
Input: grid = [[1,0]] Output: 4
Constraints:
row == grid.lengthcol == grid[i].length1 <= row, col <= 100grid[i][j] is 0 or 1.grid.This approach involves iterating over every cell in the grid. For each land cell (grid[i][j] == 1), we assume it initially contributes 4 to the perimeter. We then check its neighboring cells (up, down, left, right). If a neighboring cell is also land, we reduce the perimeter by one for each connection to another land cell, since that edge does not contribute to the perimeter.
This C program defines a function that calculates the island perimeter by checking adjacent cells for land. If an adjacent cell is land, the corresponding side does not contribute to the perimeter.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n*m) where n is the number of rows and m is the number of columns in the grid.
Space Complexity: O(1) as we only use a constant amount of extra space.
This approach leverages Depth-First Search to traverse the land cells. Starting from any land cell, we recursively visit all connected land cells and calculate the perimeter contribution for each by checking the edges. If an edge points to water or out of bounds, it contributes to the perimeter.
This C solution uses a DFS approach to calculate the perimeter by tracking visited cells and counting the contribution of each land cell.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n*m), each cell is visited once.
Space Complexity: O(n*m) for the recursion stack.
| Approach | Complexity |
|---|---|
| Iterative Grid Enumeration | Time Complexity: O(n*m) where n is the number of rows and m is the number of columns in the grid. |
| Depth-First Search (DFS) | Time Complexity: O(n*m), each cell is visited once. |
Island Perimeter - Graph - Leetcode 463 • NeetCode • 45,197 views views
Watch 9 more video solutions →Practice Island Perimeter with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor