This problem is officially posted on LeetCode 463, but I’m bringing it back here for a fresh spin… and will walk you through three different ways to crack it:
- Exploring with Breadth-First Search
- Diving in with Depth-First Search
- Counting Those Borders
Problem
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]is0or1.- There is exactly one island in
grid.
Exploring with Breadth-First Search
The idea is:
- Step one: Find a land cell to start with—any land cell will do, no need to be picky.
- Step two: Start exploring in four directions—up, down, left, right—like an overly excited tourist.
- Step three: Every time you bump into water, stop wandering in that direction and count it toward the perimeter.
- Step four: Keep the exploration going until there’s no land left to check
It’s like trying to find the edges of a pizza slice 🍕… but instead of cheese and crust, it’s land and water
Algorithm
- Initialization:
-
- Initialize perimeter = 0.
- Create a queue to store [row, col] coordinates of cells to visit.
Create a visited set to keep track of land cells already visited, preventing infinite loops and redundant calculations.
-
- Find Entry Land Cell: Iterate through the grid to find the first land cell. This will be the starting point for our BFS.
- Start BFS:
- Add the starting cell’s coordinates [startRow, startCol] to the queue.
- Add the starting cell’s coordinate string “${startRow},${startCol}” to the visited set.
- BFS Loop: While the queue is not empty:
- Dequeue the current cell [row, col].
- Examine its four neighbors (up, down, left, right): [nr, nc].
- For each neighbor [nextRow, nextCol]:
- Check Perimeter Contribution:
- If the neighbor is out of bounds OR the neighbor is water, increment perimeter.
- Check for Exploration:
- If the neighbor is land AND has not been visited yet then:
- Mark the neighbor as visited
- Enqueue the neighbor: queue.push([nextRow, nextCol]).
- If the neighbor is land AND has not been visited yet then:
- Check Perimeter Contribution:
-
Return Result: Once the queue is empty, return the final perimeter count.
function islandPerimeter(grid) {
const rows = grid.length
const cols = grid[0].length
const directions = [
[ 0, 1],
[ 0, -1],
[ 1, 0],
[-1, 0]
] // Right, Left, Down, Up
const visitedCells = new Set() // To store "row,col" strings of visited land cells
const cellsQueue = [] // Queue for BFS: stores [row, col] pairs
let perimeter = 0
// 1. Find the first land cell to start BFS
const [startRow, startCol] = findEntryCell(grid)
// 2. Initialize BFS
cellsQueue.push([startRow, startCol])
visitedCells.add(`${startRow},${startCol}`)
// 3. BFS Loop
while (cellsQueue.length > 0) {
const [row, col] = cellsQueue.shift() // Dequeue the current cell
// 4. Check neighbors
for (const [dr, dc] of directions) {
const nRow = row + dr
const nCol = col + dc
// Check for out of bounds OR water neighbor
if (nRow < 0 || nRow >= rows || nCol < 0 || nCol >= cols || grid[nRow][nCol] === 0) {
perimeter++
} else { // Neighbor is within bounds and is land. Check if we have visited it.
const neighborKey = `${nRow},${nCol}`
if (!visitedCells.has(neighborKey)) {
visitedCells.add(neighborKey)
cellsQueue.push([nRow, nCol])
}
}
}
}
return perimeter
}
function findEntryCell(grid) {
for (let r = 0; r < grid.length; r++) {
for (let c = 0; c < grid[0].length; c++) {
if (grid[r][c] === 1) {
return [r, c] // Return the first land cell found
}
}
}
return [-1, -1] // No land found. This will never happen based on constraints.
}
// Example Usage:
const grid1 = [
[0, 1, 0, 0],
[1, 1, 1, 0],
[0, 1, 0, 0],
[1, 1, 0, 0]
]
console.log('Example 1 Output:', islandPerimeter(grid1)) // Expected: 16
const grid2 = [[1]]
console.log('Example 2 Output:', islandPerimeter(grid2)) // Expected: 4
const grid3 = [[1, 0]]
console.log('Example 3 Output:', islandPerimeter(grid3)) // Expected: 4
Diving in with Depth-First Search
The idea here is the same as island exploring! However, we set off in one direction, exploring as far as we can until we inevitably run into water. Once we hit water, we backtrack to where we started and try another path.
Algorithm
- islandPerimeter(grid) function:
- Handles edge cases (empty grid).
- Finds a starting land cell [startRow, startCol].
- Initializes a visited set (using Set to store “row,col” strings).
- Calls the dfs helper function starting from [startRow, startCol].
- Returns the result of the dfs call.
- dfs(grid, r, c, visitedCells) function:
- Base Case 1 (Perimeter Edge): If the current cell is out of the grid boundaries OR is a water cell. Return 1.
- Base Case 2 (Already Visited): If the current cell is already in the visited set. Return 0.
- Recursive Step:
- Mark the current land cell.
- Initialize perimeterCount = 0.
- Recursively call dfs for all four neighbors (up, down, left, right).
- Add the result returned by each recursive call to perimeterCount.
- Return the total perimeterCount found by exploring from this cell.
// Find entry cell
function findEntryCell(grid) {
for (let r = 0; r < grid.length; r++) {
for (let c = 0; c < grid[0].length; c++) {
if (grid[r][c] === 1) {
return [r, c] // Return the first land cell found
}
}
}
return [-1, -1] // No land found. This will never happen based on constraints.
}
// DFS
function dfs(grid, r, c, visitedCells) {
const rows = grid.length;
const cols = grid[0].length;
// Base Case 1: Out of bounds or water cell -> contributes 1 to perimeter
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === 0) {
return 1;
}
// Base Case 2: Already visitedCells land cell -> contributes 0 (already processed)
const key = `${r},${c}`;
if (visitedCells.has(key)) {
return 0;
}
// Mark current land cell as visited cell
visitedCells.add(key);
let perimeterCount = 0;
// Explore neighbors recursively
perimeterCount += dfs(grid, r + 1, c, visitedCells); // Down
perimeterCount += dfs(grid, r - 1, c, visitedCells); // Up
perimeterCount += dfs(grid, r, c + 1, visitedCells); // Right
perimeterCount += dfs(grid, r, c - 1, visitedCells); // Left
return perimeterCount;
}
/**
* Main function to calculate the island perimeter using DFS.
* @param {number[][]} grid
* @return {number}
*/
function islandPerimeter(grid) {
const [startRow, startCol] = findEntryCell(grid);
const visitedCells = new Set(); // Keep track of visitedCells LAND cells
// Start DFS from the first land cell found
return dfs(grid, startRow, startCol, visitedCells);
};
// Example Usage:
const grid1 = [
[0, 1, 0, 0],
[1, 1, 1, 0],
[0, 1, 0, 0],
[1, 1, 0, 0]
]
console.log("Example 1 Output:", islandPerimeter(grid1)); // Expected: 16
const grid2 = [[1]];
console.log("Example 2 Output:", islandPerimeter(grid2)); // Expected: 4
const grid3 = [[1,0]];
console.log("Example 3 Output:", islandPerimeter(grid3)); // Expected: 4
Counting Those Borders
This approach is straightforward:
- We march through every single cell, scanning the land and adding 4 to the perimeter count.
- But what about its neighbors? If a neighboring cell is also land, we knock off 1 per shared edge.
Essentially, any cozy pair of land cells sharing space will subtract 2 in total, keeping the perimeter count realistic. It’s like a block party where each house claims all four sides until they realize they’ve got friendly neighbors, leading to some fair boundary negotiations! 🎉
Algorithm
- Initialize perimeter to 0.
- Iterate through every cell of the grid.
- If the current cell grid is land:
- Add 4 to the perimeter
- Check its four neighbors (up, down, left, right) for sharing boundary
- Substract 1 for any sharing boundary
/**
* Calculates the perimeter of the single island in the grid using iteration.
* @param {number[][]} grid
* @return {number}
*/
function islandPerimeter(grid) {
const rows = grid.length
const cols = grid[0].length
let perimeter = 0
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
// Check if the current cell is land
if (grid[r][c] === 1) {
perimeter += 4 // Start with 4 sides for a land cell
// Check neighbor above
if (r > 0 && grid[r - 1][c] === 1) {
perimeter -= 1 // Subtract shared edge
}
// Check neighbor below
if (r < rows - 1 && grid[r + 1][c] === 1) {
perimeter -= 1 // Subtract shared edge
}
// Check neighbor left
if (c > 0 && grid[r][c - 1] === 1) {
perimeter -= 1 // Subtract shared edge
}
// Check neighbor right
if (c < cols - 1 && grid[r][c + 1] === 1) {
perimeter -= 1 // Subtract shared edge
}
}
}
}
return perimeter
}
// Example Usage:
const grid1 = [
[0, 1, 0, 0],
[1, 1, 1, 0],
[0, 1, 0, 0],
[1, 1, 0, 0]
]
console.log('Example 1 Output:', islandPerimeter(grid1)) // Expected: 16
const grid2 = [[1]]
console.log('Example 2 Output:', islandPerimeter(grid2)) // Expected: 4
const grid3 = [[1, 0]]
console.log('Example 3 Output:', islandPerimeter(grid3)) // Expected: 4
Talking About Complexity
Time Complexity
No matter which strategy we pick—Couting, DFS, or BFS. We scan through the grid, meeting each land and water cell just once before moving along. So our time complexity is a solid O(R × C)—where R is the number of rows, and C is the number of columns. One-time meet-and-greet with each cell! 🤝
Space Complexity
Counting Solution wins the award of minimalist—it travels light, carries no baggage, and doesn’t need extra storage space. That’s why its space complexity is a sweet O(1) 🏕️
BFS & DFS, these two like to keep track of where they’ve been, so in the worst case, they end up storing R × C visited cells—meaning their space complexity hits O(R × C) 🎒