4
\$\begingroup\$

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: enter image description here

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;
};
\$\endgroup\$
3
\$\begingroup\$
  • 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;
}
\$\endgroup\$
  • \$\begingroup\$ Why not use function expressions? \$\endgroup\$ – thadeuszlay May 19 at 16:37
  • \$\begingroup\$ @thadeuszlay Because they are more verbose and because they only become available after the expression, while declared functions are available anywhere and any time (after parsed) in the scope they are in. \$\endgroup\$ – Blindman67 May 19 at 17:03
  • \$\begingroup\$ Objects should be making the code easier to read: Robert C. Martin (Uncle Bob) once mentioned that ideally functions should have only one parameter. I tried to follow that. Would you still advice against it? \$\endgroup\$ – thadeuszlay May 19 at 17:08
  • 1
    \$\begingroup\$ y - 1 < 0 ? 1 : grid[y - 1][x] === 0;: Do you think this is a good style to mix Number and Boolean a value can take? It's working because addition/subtraction converts Boolean values to Numbers. But I got the impression that's kind of messy. \$\endgroup\$ – thadeuszlay May 19 at 17:14
  • \$\begingroup\$ const W = grid[0].length, H = grid.length;: Why did you wrote W and H in capital letters? Because they are constants? \$\endgroup\$ – thadeuszlay May 19 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.