0109HardArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix

Plant One Bare Cell

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.

An orchard occupies a square plot laid out as the n x n grid field. A cell holds 1 where a tree already stands and 0 where the ground is still bare.

Two trees belong to the same stand when you can get from one to the other by stepping between trees that share a full side of their cells, moving up, down, left or right. Cells that merely touch at a corner are not linked. The size of a stand is the count of trees in it.

The grower may plant a tree on one bare cell, or may plant nothing at all. Return the size of the biggest stand the orchard can end up with after that single choice.

Examples

Example 1

Input: field = [[1, 1, 0], [0, 0, 1], [1, 0, 1]]
Output: 5

Planting the bare cell in the top right corner joins the pair of trees along the top row with the pair down the right edge, giving a stand of five.

Example 2

Input: field = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
Output: 9

Eight trees already ring a single bare cell in the middle, and planting it pulls the whole ring plus the new tree into one stand of nine.

Example 3

Input: field = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
Output: 3

The three trees only touch at corners, so none of them are linked. The best single planting bridges two of them for a stand of three.

Constraints

n == field.length
n == field[i].length
1 <= n <= 500
field[i][j] is either 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 largest_planted_block(field: list[list[int]]) -> int:

Java

public int largestPlantedBlock(int[][] field)

The intended approach

Time O(n^2)Space O(n^2)

Sweep the grid once and stamp every stand with its own label while recording how many trees carry that label. Then visit each bare cell and gather the labels of its four side neighbours into a set, so a stand that wraps around the cell and touches it twice is still counted once; the candidate answer is one plus the sizes of those distinct labels. Keep the largest such candidate alongside the largest untouched stand, which covers the case where planting nothing is best.

Pythonentry point: largest_planted_block

def largest_planted_block(field):
    n = len(field)
    tag = [[0] * n for _ in range(n)]
    sizes = {}
    label = 1
    steps = ((1, 0), (-1, 0), (0, 1), (0, -1))
    for r in range(n):
        for c in range(n):
            if field[r][c] == 1 and tag[r][c] == 0:
                label += 1
                tag[r][c] = label
                stack = [(r, c)]
                count = 0
                while stack:
                    y, x = stack.pop()
                    count += 1
                    for dy, dx in steps:
                        ny = y + dy
                        nx = x + dx
                        if 0 <= ny < n and 0 <= nx < n and field[ny][nx] == 1 and tag[ny][nx] == 0:
                            tag[ny][nx] = label
                            stack.append((ny, nx))
                sizes[label] = count
    best = 0
    for count in sizes.values():
        if count > best:
            best = count
    for r in range(n):
        for c in range(n):
            if field[r][c] == 0:
                touching = set()
                for dy, dx in steps:
                    ny = r + dy
                    nx = c + dx
                    if 0 <= ny < n and 0 <= nx < n and tag[ny][nx] != 0:
                        touching.add(tag[ny][nx])
                total = 1
                for label in touching:
                    total += sizes[label]
                if total > best:
                    best = total
    return best

The obvious version

Measure the biggest stand from scratch, then for every bare cell copy the grid, plant that cell, and measure again from scratch. Keep the largest figure seen. O(n^4).

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_largest_planted_block(field):
    n = len(field)
    steps = ((1, 0), (-1, 0), (0, 1), (0, -1))

    def biggest(grid):
        seen = [[False] * n for _ in range(n)]
        top = 0
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1 and not seen[r][c]:
                    seen[r][c] = True
                    queue = [(r, c)]
                    head = 0
                    while head < len(queue):
                        y, x = queue[head]
                        head += 1
                        for dy, dx in steps:
                            ny = y + dy
                            nx = x + dx
                            if 0 <= ny < n and 0 <= nx < n and grid[ny][nx] == 1 and not seen[ny][nx]:
                                seen[ny][nx] = True
                                queue.append((ny, nx))
                    if len(queue) > top:
                        top = len(queue)
        return top

    best = biggest(field)
    for r in range(n):
        for c in range(n):
            if field[r][c] == 0:
                trial = [row[:] for row in field]
                trial[r][c] = 1
                got = biggest(trial)
                if got > best:
                    best = got
    return best

How this problem was checked

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