0353MediumArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix

Widest Moss Patch

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 courtyard is paved with square slabs laid out as grid. Entry grid[r][c] is 1 when that slab is mossy and 0 when it is clean.

A patch is a group of mossy slabs that you can walk between by stepping from one slab to a mossy slab sharing an edge with it, so slabs that only touch at a corner belong to different patches. The size of a patch is how many slabs it holds.

Return the size of the largest patch in the courtyard, or 0 when no slab is mossy.

Examples

Example 1

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

The three slabs in the top-left corner form one patch of size 3. The slabs at (1,3), (2,2), (2,3) and (3,2) share edges and form a patch of size 4, which is the largest.

Example 2

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

The two mossy slabs meet only at a corner, so each is a patch of size 1 on its own.

Example 3

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

No slab is mossy, so there is no patch at all.

Constraints

m == grid.length
n == grid[r].length
1 <= m, n <= 50
grid[r][c] is 0 or 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 max_area_of_island(grid: list[list[int]]) -> int:

Java

public int maxAreaOfIsland(int[][] grid)

The intended approach

Time O(m * n)Space O(m * n)

Scan the courtyard for a mossy slab that has not been visited and flood its whole patch from there, counting slabs as they come off an explicit stack. Marking a slab at the moment it is pushed keeps it out of the stack twice over. The largest count seen across all floods is the answer, and using a stack rather than recursion keeps a patch that fills the courtyard safe.

Pythonentry point: max_area_of_island

def max_area_of_island(grid):
    # Flood fill each unvisited mossy slab with an explicit stack, so a patch that
    # covers every slab of a 50 by 50 yard cannot overflow the call stack.  Slabs are
    # marked the moment they are pushed, so nothing is counted twice.
    # Time O(m * n).  Space O(m * n) for the marks and the stack.
    rows = len(grid)
    cols = len(grid[0])
    best = 0
    for r0 in range(rows):
        for c0 in range(cols):
            if grid[r0][c0] != 1:
                continue
            grid[r0][c0] = 2
            stack = [(r0, c0)]
            size = 0
            while stack:
                r, c = stack.pop()
                size += 1
                if r > 0 and grid[r - 1][c] == 1:
                    grid[r - 1][c] = 2
                    stack.append((r - 1, c))
                if r + 1 < rows and grid[r + 1][c] == 1:
                    grid[r + 1][c] = 2
                    stack.append((r + 1, c))
                if c > 0 and grid[r][c - 1] == 1:
                    grid[r][c - 1] = 2
                    stack.append((r, c - 1))
                if c + 1 < cols and grid[r][c + 1] == 1:
                    grid[r][c + 1] = 2
                    stack.append((r, c + 1))
            if size > best:
                best = size
    return best

The obvious version

Give every slab its own set, union each mossy slab with the mossy slab below it and to its right, then tally how many slabs sit in each root's set and take the biggest tally.

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_widest_patch(grid):
    rows = len(grid)
    cols = len(grid[0])
    parent = list(range(rows * cols))

    def find(a):
        while parent[a] != a:
            parent[a] = parent[parent[a]]
            a = parent[a]
        return a

    def union(a, b):
        ra = find(a)
        rb = find(b)
        if ra != rb:
            parent[ra] = rb

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                if r + 1 < rows and grid[r + 1][c] == 1:
                    union(r * cols + c, (r + 1) * cols + c)
                if c + 1 < cols and grid[r][c + 1] == 1:
                    union(r * cols + c, r * cols + c + 1)
    tally = {}
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                root = find(r * cols + c)
                tally[root] = tally.get(root, 0) + 1
    best = 0
    for value in tally.values():
        if value > best:
            best = value
    return best

How this problem was checked

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