Island Perimeter

Question

The task is taken from leetcode

You are given a map in form of a two-dimensional integer grid where 1 represents land and 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" (water inside that 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:

Input:

[[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 below:

My solution

/**
 * @param {number[][]} grid
 * @return {number}
 */
var islandPerimeter = function(grid) {
  const getWaterNeighborAt = position => {
    if (!grid[position.y][position.x]) { return 0; }

    const north = position.y - 1 < 0 ? true : grid[position.y - 1][position.x] === 0;
    const east = position.x + 1 >= grid[0].length ? true : grid[position.y][position.x + 1] === 0;
    const south = position.y + 1 >= grid.length ? true : grid[position.y + 1][position.x] === 0;
    const west = position.x - 1 < 0 ? true : grid[position.y][position.x - 1] === 0;

    return north + east + south + west;
  };
  let perimeter = 0;
  grid.forEach((row, y) => {
    row.forEach((_, x) => {
      perimeter += getWaterNeighborAt({x, y});
    });
  });
  return perimeter;
};

Answer 1

• Objects should be making the code easier to read. The Object you name position provides no behavioral benefit and serves only to bloat the code.

• You should be using good old for loops for this rather than the hacky way you use the array iteration function forEach

• Use function declarations function islandPerimeter(grid). Do not use function expressions var islandPerimeter = function(grid)

Rewrite

Rewriting your coder I would do it as follows

function islandPerimeter(grid) {
    const W = grid[0].length, H = grid.length;
    const countEdges = (x, y) => {
        var res = 0;
        if (grid[y][x]) { 
            res += y - 1 < 0 ? 1 : grid[y - 1][x] === 0;
            res += x + 1 >= W ? 1 : grid[y][x + 1] === 0;
            res += y + 1 >= H ? 1 : grid[y + 1][x] === 0;
            res += x - 1 < 0 ? 1 : grid[y][x - 1] === 0;
        }
        return res;
    };
    var perimeter = 0, x = 0; y = 0;
    for (y = 0; y < H; y ++) {
        for (x = 0; x < W; x ++) {
            perimeter += countEdges(x, y);
        }
    }
    return perimeter;
}

A flaw in the problem

The question states all the land is connected which hints at an optimal solution however the problem is flawed.

There is a solution that is \$O(l)\$ where \$l\$ is the land cell count if you had one extra tit-bit of information, a coordinate of a land cell.

That way you could use a flood fill and thus only need to check land cells.

Without that coordinate you need to search for the land and the worst case would have the land cell the last cell making it \$O(n)\$ where \$n\$ is the cell count.

Performance

You can however improve the performance by counting edges as you cross them. If a cell is different than the cell to the left, or above then there is a edge to count

function islandPerimeter(grid) {
    const W = grid[0].length, H = grid.length;
    var x = 0, y = 0, res = 0, prevRow = 0, prev;
    while (y < H) {
        x = prev = 0;
        const row = grid[y];
        const prevCount = res;
        while (x < W) {
            const cell = row[x];
            res += cell !== prev;
            res += prevRow && prevRow[x] !== cell;
            prev = cell;
            x++;
        }
        res += prev;
        if (res && prevCount === res) { return res }
        prevRow = row;
        y++;
    }
    while (x--) { res += prevRow[x] === 1 }
    res += prevRow[0];
    return res;
}

As the question states that all he land is connected thus I added an early exit if there is an empty row after some land cells have been found.

Flood Fill

And here is a flood fill example. Its just a quick write as it does not really provide an improvement without at least a coordinate of a land cell. There are a few optimizations that could be added and it also needs to modify the map so to not repeat cells

It finds the first cell by stepping over empty cells.

function islandPerimeter(arr) {
    const H = arr.length, W = arr[0].length, SIZE = H * W;
    const EDGES = [[1, 0], [-2, 0], [1, -1], [0, 2]];
    const stack = [];

    const isLand = () => (cell = arr[y] && arr[y][x] || 0) > 0;
    const isLandIdx = () => (x = idx % W, y = idx / W | 0, isLand());
    const checked = () => (stack.push([x,y]), arr[y][x] = 2);
    var x, y, res = 0, idx = 0, cell;
    while (idx < SIZE && !isLandIdx()) { idx++ }
    if (idx < SIZE) {
        checked();
        while (stack.length) {
            [x, y] = stack.pop();
            for (const e of EDGES) {
                x += e[0];
                y += e[1];
                isLand() ? (cell === 1 && checked()) : res++;
            }
        }
    }
    return res;
}