The largest slab in the quarry

Before a quarry cuts a slab it surveys the face square by square. Clay seams decide how big a slab can be, and the manager wants the biggest one the face will give.

The problem

The survey is a rectangular grid. A square holds 1 where the probe found sound stone and 0 where it found clay.

Two sound squares are part of the same block when they share an edge — up, down, left or right. Squares meeting only at a corner are in different blocks: a clay seam runs between them.

Report the number of squares in the largest block. A face of nothing but clay gives 0.

Input. face — a list of lists of integers, each 0 or 1, every row the same length.

Output. An integer: the size of the largest block.

Example.

face = [[1, 1, 0, 0, 1],
        [1, 0, 0, 1, 1],
        [0, 0, 1, 1, 0],
        [1, 0, 0, 0, 0]]   ->  5

Three blocks: three squares in the top left, one on its own in the bottom left, and five running from the top right corner down and across. Five wins.

A second example, where the sound stone is worth nothing:

face = [[1, 0, 1],
        [0, 1, 0],
        [1, 0, 1]]   ->  1

Five sound squares, but every one of them touches the others at a corner only, so no two are in a block together. Allowing corners would answer 5.

face = [[0, 0],
        [0, 0]]   ->  0

Constraints.

• 1 <= len(face) <= 400
• 1 <= len(face[0]) <= 400, every row the same length
• every entry is 0 or 1

Hints

Approach

Brute force

For every sound square, walk its whole block counting squares, and keep the largest count. Without marking, the same block is re-walked from each of its squares: a solid 400 × 400 face costs 160,000 walks of 160,000 squares.

The insight

Treat each sound square as its own block of one and merge it with the sound square to its right and the one below, carrying the size of every block at its root; the answer is then the largest size any root holds.

Merging is enough because a block is exactly a set of squares joined by a chain of shared edges, and each edge is one merge. Keeping the count at the root is what makes a join O(1): the two roots are known, the smaller group is hung under the larger and one addition transfers its whole count. Nothing is ever recounted.

Algorithm

1. Number the squares r * cols + c, and give every square its own group of size 1.
2. Sweep the grid. Skip clay. For a sound square, merge it with the square to its right and the square below when those are sound.
3. To merge: find both roots, stop if they match, hang the smaller under the larger and add its size onto the new root.
4. Sweep again, and for each sound square read the size at its root, keeping the largest seen.

Complexity

Time O(r · c · α(r · c)) — two sweeps of the grid, each square doing at most two merges and one lookup, and α is under 5 for any grid that fits in memory. Space O(r · c) for the parent and size arrays.

Solution

"""The largest slab in the quarry — merge neighbouring sound squares, then read the biggest group."""


def find(parent, cell):
    while parent[cell] != cell:
        parent[cell] = parent[parent[cell]]     # halve the path on the way up
        cell = parent[cell]
    return cell


def union(parent, size, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra == rb:
        return
    if size[ra] < size[rb]:
        ra, rb = rb, ra
    parent[rb] = ra
    size[ra] += size[rb]      # invariant: only a root carries the count of its group


def solve(face):
    rows, cols = len(face), len(face[0])
    parent = list(range(rows * cols))
    size = [1] * (rows * cols)

    for r in range(rows):
        for c in range(cols):
            if face[r][c] == 0:
                continue
            here = r * cols + c
            # right and down only: every shared edge is merged once, from its
            # left-hand or upper square
            if c + 1 < cols and face[r][c + 1] == 1:
                union(parent, size, here, here + 1)
            if r + 1 < rows and face[r + 1][c] == 1:
                union(parent, size, here, here + cols)

    largest = 0
    for r in range(rows):
        for c in range(cols):
            if face[r][c] == 1:
                largest = max(largest, size[find(parent, r * cols + c)])
    return largest

TESTS = [
    (([[1, 1, 0, 0, 1], [1, 0, 0, 1, 1], [0, 0, 1, 1, 0], [1, 0, 0, 0, 0]],), 5),
    (([[1, 0, 1], [0, 1, 0], [1, 0, 1]],), 1),      # corners do not join squares
    (([[0, 0], [0, 0]],), 0),                       # all clay
    (([[1, 1], [1, 1]],), 4),
    (([[1, 1, 1], [1, 0, 1], [1, 1, 1]],), 8),      # a ring around one clay square
    (([[1, 1, 0, 1, 1, 1]],), 3),
    (([[1]],), 1),
    (([[0]],), 0),
]

Pitfalls

• Taking the largest size over every square rather than every sound square. Clay squares are never merged and keep their starting size of 1, so a face of solid clay answers 1 instead of 0.
• Reading a size off a square that is not a root. Only the root's count is the block's; ask the square at row 2, column 2 in the first example and it still says 1.
• Merging squares that meet at a corner. The second example becomes one block and answers 5.

Variants

• The trunk line survey — the same merging, counting the groups instead of measuring them.
• Union-find — why hanging the smaller group under the larger keeps the lookups flat.