Show problems as
Classic problem #827HardArrayDepth-First SearchBreadth-First SearchUnion-FindMatrix

Making A Large Island

Real-world version: Plant One Bare Cell
Tracked in this browser only
Read Making A Large Island on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def largest_planted_block(field: list[list[int]]) -> int:
Java
public int largestPlantedBlock(int[][] field)

More on the same topics