Island Perimeter

NeetCode: Island Perimeter · LeetCode: 463. Island Perimeter · Difficulty: Easy

You are given a grid where 1 is land and 0 is water. The grid contains exactly one island (connected land, no lakes inside) and is surrounded by water. Return its perimeter. Each cell is a square of side 1.

Example

Text

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

A land cell contributes one unit of perimeter for every side that touches water or the edge of the grid.

Brute force: inspect all four sides of every land cell

For each land cell, look at its four neighbours and add 1 for every neighbour that is out of bounds or water. Java checks array bounds at run time and throws ArrayIndexOutOfBoundsException, so the bounds test must come before the read. This is linear in the grid size; the second approach has the same complexity and counts differently.

Java

class Solution {
    public int islandPerimeter(int[][] grid) {
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int total = 0;
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[r].length; c++) {
                if (grid[r][c] != 1) {
                    continue;
                }
                for (int[] d : dirs) {
                    int nr = r + d[0];
                    int nc = c + d[1];
                    boolean inside = nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[r].length;
                    if (!inside || grid[nr][nc] == 0) {
                        total++;
                    }
                }
            }
        }
        return total;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] grid = {{0, 1, 0, 0}, {1, 1, 1, 0}, {0, 1, 0, 0}, {1, 1, 0, 0}};
        System.out.println(s.islandPerimeter(grid));
        System.out.println(s.islandPerimeter(new int[][]{{1}}));
        System.out.println(s.islandPerimeter(new int[][]{{1, 0}}));
    }
}

Output

16
4
4

Time: O(m * n). Space: O(1).

Optimal: 4 per cell minus 2 per shared edge

Every land cell would have perimeter 4 on its own. Each pair of adjacent land cells hides one side of each cell, so it removes 2. Looking only at the cell above and the cell to the left counts every adjacent pair exactly once, so the answer is 4 * cells - 2 * pairs.

Java

class Solution {
    public int islandPerimeter(int[][] grid) {
        int cells = 0;
        int pairs = 0;
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[r].length; c++) {
                if (grid[r][c] == 1) {
                    cells++;
                    if (r > 0 && grid[r - 1][c] == 1) {
                        pairs++;
                    }
                    if (c > 0 && grid[r][c - 1] == 1) {
                        pairs++;
                    }
                }
            }
        }
        return 4 * cells - 2 * pairs;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] grid = {{0, 1, 0, 0}, {1, 1, 1, 0}, {0, 1, 0, 0}, {1, 1, 0, 0}};
        System.out.println(s.islandPerimeter(grid));
        System.out.println(s.islandPerimeter(new int[][]{{1}}));
        System.out.println(s.islandPerimeter(new int[][]{{1, 0}}));
    }
}

Output

16
4
4

Time: O(m * n). Space: O(1).