0543EasyArrayDepth-First SearchBreadth-First SearchMatrix

Edge Trim for the Solar Array

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A flat roof is drawn as grid, a rectangle of one-metre squares. grid[i][j] is 1 when a solar panel sits on that square and 0 when the square is bare.

The panels form exactly one array: every panel square can be reached from every other by stepping between squares that share a full edge, never through a corner. An installer runs weatherproof trim along every panel edge that is not shared with another panel, including edges that fall on the outer boundary of the drawing.

Return the total length of trim in metres.

Examples

Example 1

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

Going square by square and counting the edges that face a bare square or the outside of the drawing: 2 at row 0 column 1, 3 at row 0 column 2, 2 at row 1 column 1, 3 at row 2 column 0, 1 at row 2 column 1 and 3 at row 2 column 2. Those come to 14 metres.

Example 2

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

The two top corners each expose 3 edges and the other five squares expose 2 each, which comes to 16 metres. The bare notch at row 0 column 1 and row 1 column 1 is trimmed on both of its sides.

Example 3

Input: grid = [[1, 1], [1, 1]]
Output: 8

Each of the four squares has two edges facing the outside of the drawing and two facing another panel, so the trim runs 2 metres per square, 8 in total.

Constraints

rows == grid.length
cols == grid[i].length
1 <= rows, cols <= 100
grid[i][j] is 0 or 1.
grid holds exactly one panel array, and it holds at least one panel square.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def island_perimeter(grid: list[list[int]]) -> int:

Java

public int islandPerimeter(int[][] grid)

The intended approach

Time O(rows * cols): a fixed amount of work per square.Space O(1) beyond the input grid.

A lone panel square needs four metres of trim. Whenever two panel squares share an edge, that edge stops needing trim on both of them, so the pair costs two metres less than the two squares would separately. Scan the rectangle once, add four for every panel square, and subtract two for each touching pair. Checking only the square to the right and the square below visits each pair exactly once, so nothing is double-counted and no visited table is needed.

Pythonentry point: island_perimeter

def island_perimeter(grid):
    # O(rows*cols) time and O(1) extra space. Every panel tile brings four
    # edges; each place where two tiles touch hides one edge on each of them,
    # so subtract two per touching pair. Looking only right and down counts
    # each pair exactly once.
    rows = len(grid)
    cols = len(grid[0])
    trim = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1:
                continue
            trim += 4
            if c + 1 < cols and grid[r][c + 1] == 1:
                trim -= 2
            if r + 1 < rows and grid[r + 1][c] == 1:
                trim -= 2
    return trim

The obvious version

Walk the array itself with an explicit stack, starting from the first panel square found. For each square popped, look at its four orthogonal neighbours: a neighbour off the drawing or a bare square contributes one metre of trim, while an unvisited panel neighbour is pushed for later.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_island_perimeter(grid):
    rows = len(grid)
    cols = len(grid[0])
    start = None
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                start = (r, c)
                break
        if start is not None:
            break
    if start is None:
        return 0
    seen = [[False] * cols for _ in range(rows)]
    seen[start[0]][start[1]] = True
    stack = [start]
    total = 0
    while stack:
        r, c = stack.pop()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if nr < 0 or nr >= rows or nc < 0 or nc >= cols or grid[nr][nc] == 0:
                total += 1
            elif not seen[nr][nc]:
                seen[nr][nc] = True
                stack.append((nr, nc))
    return total

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in