1108MediumArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix

Patches of Dry Ground Ringed by Water

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 map marsh holds only 0 and 1, where 0 marks dry ground and 1 marks water. Two dry cells belong to the same patch when they share a side, so up, down, left or right; touching only at a corner does not join them.

A patch is enclosed when none of its cells lies on the outer edge of the map, which means water rings it on every side.

Return how many patches are enclosed.

Examples

Example 1

Input: marsh = [[1, 1, 1, 1], [1, 0, 1, 1], [1, 1, 0, 1], [1, 1, 1, 1]]
Output: 2

The two dry cells meet only at a corner, which does not join them, so each is a patch of its own. Neither lies on the outer edge, so both are enclosed.

Example 2

Input: marsh = [[1, 1, 1], [1, 0, 0], [1, 1, 0]]
Output: 0

The three dry cells form one patch and two of them sit in the map's last column, so the patch is open.

Example 3

Input: marsh = [[1, 1, 1, 1, 1], [1, 0, 0, 0, 1], [1, 0, 1, 0, 1], [1, 0, 0, 0, 1], [1, 1, 1, 1, 1]]
Output: 1

The eight dry cells form a single ring around a water cell in the middle. None of them touches the outer edge, so the ring counts once.

Constraints

1 <= marsh.length <= 100
1 <= marsh[i].length <= 100
0 <= marsh[i][j] <= 1

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 closed_island(marsh: list[list[int]]) -> int:

Java

public int closedIsland(int[][] marsh)

The intended approach

Time O(rows * cols) over the map.Space O(rows * cols) for the visited marks and the stack.

Being enclosed is a fact about a whole patch, not about any one cell, so the patch has to be gathered before the verdict can be given. Sweep the map and, at the first unvisited dry cell, spread out over its entire patch by pushing side-sharing dry neighbours onto a stack and marking them visited as they go on. Marking on the way in rather than on the way out keeps each cell out of the stack more than once. While spreading, watch for any cell in the top row, bottom row, first column or last column. One such cell is enough to disqualify the patch, so carry a single flag through the spread rather than deciding cell by cell. Count the patch when the spread finishes with the flag still standing. Visited marks are never cleared, so every cell is entered once and the whole map is handled in one sweep plus the spreads.

Pythonentry point: closed_island

def closed_island(marsh):
    rows = len(marsh)
    cols = len(marsh[0])
    seen = [[False] * cols for _ in range(rows)]
    total = 0
    for r in range(rows):
        for c in range(cols):
            if marsh[r][c] != 0 or seen[r][c]:
                continue
            stack = [(r, c)]
            seen[r][c] = True
            shut = True
            while stack:
                y, x = stack.pop()
                if y == 0 or x == 0 or y == rows - 1 or x == cols - 1:
                    shut = False
                for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    ny = y + dy
                    nx = x + dx
                    if 0 <= ny < rows and 0 <= nx < cols:
                        if marsh[ny][nx] == 0 and not seen[ny][nx]:
                            seen[ny][nx] = True
                            stack.append((ny, nx))
            if shut:
                total += 1
    return total

The obvious version

Give every dry cell its own number, then sweep the map over and over pulling each cell's number down to the smallest among itself and its side-sharing dry neighbours, until a whole sweep changes nothing. Cells of one patch end up sharing a number. Count the distinct numbers, take away those that appear anywhere on the outer edge, and what is left is the answer. Costs a sweep per round and the rounds grow with the longest patch.

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_closed_island(marsh):
    rows = len(marsh)
    cols = len(marsh[0])
    tag = [[-1] * cols for _ in range(rows)]
    nxt = 0
    for r in range(rows):
        for c in range(cols):
            if marsh[r][c] == 0:
                tag[r][c] = nxt
                nxt += 1
    moving = True
    while moving:
        moving = False
        for r in range(rows):
            for c in range(cols):
                if marsh[r][c] != 0:
                    continue
                low = tag[r][c]
                for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    ny = r + dy
                    nx = c + dx
                    if 0 <= ny < rows and 0 <= nx < cols:
                        if marsh[ny][nx] == 0 and tag[ny][nx] < low:
                            low = tag[ny][nx]
                if low != tag[r][c]:
                    tag[r][c] = low
                    moving = True
    every = set()
    edging = set()
    for r in range(rows):
        for c in range(cols):
            if marsh[r][c] != 0:
                continue
            every.add(tag[r][c])
            if r == 0 or c == 0 or r == rows - 1 or c == cols - 1:
                edging.add(tag[r][c])
    return len(every) - len(edging)

How this problem was checked

Reference solution executed against 15 test cases — 15 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