Perimeter of Shapes in Binary Matrix

Problem Overview

Each 1-cell on its own has four sides.

Intuition

Each 1-cell on its own has four sides. When two 1-cells touch along a side, that side is inside the shape, so it disappears from both cells and the total drops by two. The answer is four times the number of 1-cells minus two times the number of touching pairs. Counting only the neighbor above and the neighbor to the left visits every touching pair exactly once, so one scan of the grid is enough and no flood fill is needed.

Algorithm

1Start the perimeter at 0 and scan every cell row by row.
2Skip any cell that is not 1.
3For a 1-cell, add 4.
4If the cell above is also 1, subtract 2. If the cell to the left is also 1, subtract 2.
5Return the total after the scan.

Example Walkthrough

Input: mat = [[0,1,0,0,0],[1,1,1,0,0],[1,0,0,0,0]]

1. There are five 1-cells, which gives 20 sides.
2. The cells touch in four places: the top cell with the center below it, the center with its left and right neighbors, and the left cell with the one below it.
3. Each touching pair removes 2, so the perimeter is 20 minus 8.

Output: 12

Common Pitfalls

• Check only up and left. Checking all four directions counts each shared side twice.
• Separate shapes do not need separate handling, because the formula adds up every shape at once.
• A recursive flood fill can overflow the stack on a large connected shape.
• Marking visited cells by overwriting the input changes the caller matrix. The counting pass leaves it alone.

Perimeter of Shapes in Binary Matrix.java

Java

// Approach: Each 1-cell adds 4 sides. Every shared side between two
// neighboring 1-cells hides one side from each, so it removes 2. Checking
// only the cell above and the cell to the left counts each shared side once.
// No recursion and no changes to the input.
// Complexity: O(n * m) time, O(1) extra space.
class Solution {
    static int findPerimeter(int[][] mat) {
        int perimeter = 0;
        for (int i = 0; i < mat.length; i++) {
            int[] row = mat[i];
            for (int j = 0; j < row.length; j++) {
                if (row[j] != 1)
                    continue;
                perimeter += 4;
                if (i > 0 && mat[i - 1][j] == 1)
                    perimeter -= 2;
                if (j > 0 && row[j - 1] == 1)
                    perimeter -= 2;
            }
        }
        return perimeter;
    }
}

Was this solution helpful?