Leetcode #463. Island Perimeter

tags:Matrix DFS BFS Easy

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.

Sample Input and Output

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 2

Input: grid = [[1,0]]
Output: 4

---

Solutions

Most Votes

DFS: iterate over grid and measure the perimeter if the cell value is 1

var islandPerimeter = function(grid) {
  if (grid === null) return 0;
  for (let i = 0 ; i < grid.length ; i++){
      for (let j = 0 ; j < grid[0].length ; j++){
          if (grid[i][j] === 1) {
              return getPerimeter(grid,i,j);
          }
      }
  }
  return 0;  
};

function getPerimeter(grid, i, j){
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {
        return 1;
    }

    if (grid[i][j] === 0) {
        return 1;
    }

    if (grid[i][j] === -1) return 0;

    let count = 0;
    grid[i][j] = -1;

    count += getPerimeter(grid, i-1, j);
    count += getPerimeter(grid, i, j-1);
    count += getPerimeter(grid, i, j+1);
    count += getPerimeter(grid, i+1, j);

    return count;

}

BFS: for each land cell add up the perimeter

var islandPerimeter = function(grid) {
    const rows = grid.length;
    const cols = grid[0].length;
    
    let perimeter = 0;
    
    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            if (!grid[row][col]) continue;
            
            perimeter += 4;
            
            if (row > 0 && grid[row - 1][col]) perimeter -= 2;
            if (col > 0 && grid[row][col - 1]) perimeter -= 2;
        }
    }
    
    return perimeter;
};

Complexity analysis

Time complexity : O(mn)
where m is the length of the row, n is the length of the column

Space complexity (extra) : O(1)

---

Everyone's

DFS

東

/*
    Time O(m*n) | Space O(m*n) 
    m is the number of row of input grid
    n is the number of colomn of input grid
*/
var islandPerimeter = function(grid) {
   const rowCnt = grid.length;
   const colCnt = grid[0].length;
   let perimeter = 0;
   const visited = new Array(rowCnt).fill().map(() => new Array(colCnt).fill(false));

   function depthFirstTraverse(rowIdx, colIdx){
        if(rowIdx < 0 || rowIdx > rowCnt - 1 || colIdx < 0 || colIdx > colCnt - 1 || grid[rowIdx][colIdx] === 0){
            return 1;
            }
        else if(!visited[rowIdx][colIdx]) {
                visited[rowIdx][colIdx] = true;
                let currPerim = 0;
                currPerim += depthFirstTraverse(rowIdx + 1, colIdx);
                currPerim += depthFirstTraverse(rowIdx, colIdx + 1);
                currPerim += depthFirstTraverse(rowIdx - 1, colIdx);
                currPerim += depthFirstTraverse(rowIdx, colIdx - 1);
                perimeter += currPerim;
            }
        return 0;
    }

   for(let i = 0; i < rowCnt; i++){
       for(let j = 0; j < colCnt; j++){
           if(grid[i][j] === 1){
               depthFirstTraverse(i, j);
               return perimeter;
           }
       }
   }
};

BFS

月

/* Time: O(n*m) | Space: O(1)
   n, m is the length and width of the island.
*/
var islandPerimeter = function(grid) {
  let perimeter = 0;
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j]) {
        perimeter += 4;
        if (grid[i - 1] && grid[i - 1][j]) perimeter--;
        if (grid[i + 1] && grid[i + 1][j]) perimeter--;
        if (grid[i] && grid[i][j - 1]) perimeter--;
        if (grid[i] && grid[i][j + 1]) perimeter--;
      }
    }
  }
  return perimeter;
}

YC

let subtracted = 0;
let land = 0;

var islandPerimeter = function(grid) {

    const x = grid.length;
    const y = grid[0].length;
    
    for(let i = 0; i < x; i++){
        for(let j = 0; j < y; j++){
            if(grid[i][j] !== 1) continue;
            
            land++;
            
            checkAdjacent(i-1, j, grid);
            checkAdjacent(i+1, j, grid);
            checkAdjacent(i, j-1, grid);
            checkAdjacent(i, j+1, grid);
        }
    }
    
    return land * 4 - subtracted;
};

function checkAdjacent(i, j, grid){
    if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) return;
    if(grid[i][j] === 0) return;
    
    subtracted++;
}

backlog

Hao

---

Supplement / Discussion