LeetCode 463: Island Perimeter (Count Land Edges Minus Shared Borders)
LeetCode 463MatrixCountingInterviewToday we solve LeetCode 463 - Island Perimeter.
Source: https://leetcode.com/problems/island-perimeter/
English
Problem Summary
Given a grid where 1 is land and 0 is water, there is exactly one island (no lakes). Return the island perimeter.
Key Insight
Each land cell contributes 4 edges initially. If two land cells are adjacent, they share one border, which removes 2 perimeter edges in total. So we can count land cells and shared adjacencies.
Brute Force and Limitations
For each land cell, checking all 4 neighbors and counting water/out-of-bound sides already works in O(mn). A cleaner counting variant computes 4 * lands - 2 * shared.
Optimal Algorithm Steps
1) Initialize land = 0, shared = 0.
2) Scan every cell.
3) If current cell is land:
- land++
- if upper cell is land, shared++
- if left cell is land, shared++
4) Return 4 * land - 2 * shared.
Complexity Analysis
Time: O(mn).
Space: O(1).
Common Pitfalls
- Double-counting shared borders by checking all 4 directions for the same pair.
- Forgetting boundary checks for top/left neighbors.
- Misreading the problem and trying to handle multiple islands (not needed here).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int islandPerimeter(int[][] grid) {
int land = 0, shared = 0;
int m = grid.length, n = grid[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
land++;
if (i > 0 && grid[i - 1][j] == 1) shared++;
if (j > 0 && grid[i][j - 1] == 1) shared++;
}
}
}
return 4 * land - 2 * shared;
}
}func islandPerimeter(grid [][]int) int {
land, shared := 0, 0
m, n := len(grid), len(grid[0])
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
land++
if i > 0 && grid[i-1][j] == 1 {
shared++
}
if j > 0 && grid[i][j-1] == 1 {
shared++
}
}
}
}
return 4*land - 2*shared
}class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int land = 0, shared = 0;
int m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
++land;
if (i > 0 && grid[i - 1][j] == 1) ++shared;
if (j > 0 && grid[i][j - 1] == 1) ++shared;
}
}
}
return 4 * land - 2 * shared;
}
};class Solution:
def islandPerimeter(self, grid: list[list[int]]) -> int:
land = 0
shared = 0
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
land += 1
if i > 0 and grid[i - 1][j] == 1:
shared += 1
if j > 0 and grid[i][j - 1] == 1:
shared += 1
return 4 * land - 2 * sharedvar islandPerimeter = function(grid) {
let land = 0, shared = 0;
const m = grid.length, n = grid[0].length;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
land += 1;
if (i > 0 && grid[i - 1][j] === 1) shared += 1;
if (j > 0 && grid[i][j - 1] === 1) shared += 1;
}
}
}
return 4 * land - 2 * shared;
};中文
题目概述
给定二维网格，1 表示陆地、0 表示水域，且只有一个岛屿（没有湖）。求该岛屿的周长。
核心思路
每个陆地格子先贡献 4 条边；若两个陆地格子相邻，它们共享一条边，会让总周长减少 2。于是可以统计陆地数量与共享边数量。
暴力解法与不足
逐个陆地检查四个方向并统计“临水/越界边”也能做，复杂度同样是 O(mn)。这里使用更整洁的计数公式：4 * land - 2 * shared。
最优算法步骤
1）初始化 land = 0、shared = 0。
2）遍历整个网格。
3）若当前位置是陆地：
- land++
- 若上方是陆地，shared++
- 若左方是陆地，shared++
4）返回 4 * land - 2 * shared。
复杂度分析
时间复杂度：O(mn)。
空间复杂度：O(1)。
常见陷阱
- 共享边被重复统计（如果四个方向都算同一对邻居）。
- 忘记做边界判断导致越界。
- 误以为要处理多岛屿场景（本题不需要）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int islandPerimeter(int[][] grid) {
int land = 0, shared = 0;
int m = grid.length, n = grid[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
land++;
if (i > 0 && grid[i - 1][j] == 1) shared++;
if (j > 0 && grid[i][j - 1] == 1) shared++;
}
}
}
return 4 * land - 2 * shared;
}
}func islandPerimeter(grid [][]int) int {
land, shared := 0, 0
m, n := len(grid), len(grid[0])
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
land++
if i > 0 && grid[i-1][j] == 1 {
shared++
}
if j > 0 && grid[i][j-1] == 1 {
shared++
}
}
}
}
return 4*land - 2*shared
}class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int land = 0, shared = 0;
int m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
++land;
if (i > 0 && grid[i - 1][j] == 1) ++shared;
if (j > 0 && grid[i][j - 1] == 1) ++shared;
}
}
}
return 4 * land - 2 * shared;
}
};class Solution:
def islandPerimeter(self, grid: list[list[int]]) -> int:
land = 0
shared = 0
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
land += 1
if i > 0 and grid[i - 1][j] == 1:
shared += 1
if j > 0 and grid[i][j - 1] == 1:
shared += 1
return 4 * land - 2 * sharedvar islandPerimeter = function(grid) {
let land = 0, shared = 0;
const m = grid.length, n = grid[0].length;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
land += 1;
if (i > 0 && grid[i - 1][j] === 1) shared += 1;
if (j > 0 && grid[i][j - 1] === 1) shared += 1;
}
}
}
return 4 * land - 2 * shared;
};
Comments