1128HardArrayDynamic ProgrammingMemoizationMatrix

The Longest Bend Across the Mosaic

Tracked in this browser only

Trains the technique from

LeetCode 3459Length of Longest V-Shaped Diagonal Segment

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 mosaic mosaic holds only the marks 0, 1 and 2.

A bend is a run of tiles where each tile after the first sits diagonally beside the one before it, so one row up or down together with one column left or right. A bend has to satisfy all of the following:

The first tile is marked 1.
The marks after it run 2, 0, 2, 0 and onwards without end.
Every step goes in the same diagonal direction, except that the run may change direction once, and only by turning a quarter turn clockwise.

The four diagonal directions in clockwise order are down-and-right, down-and-left, up-and-left, up-and-right, and then back round to down-and-right. A quarter turn clockwise moves from one to the next in that cycle.

A single tile marked 1 is a bend of length one. Return the length of the longest bend, or 0 when the mosaic holds no 1 at all.

Examples

Example 1

Input: mosaic = [[0, 0, 1, 0], [0, 0, 0, 2], [0, 0, 0, 0], [0, 2, 0, 0]]
Output: 4

The only 1 sits in the top row. Stepping down and right onto the 2, then turning a quarter turn clockwise to run down and left through the 0 and the 2, gives four tiles. Without the turn the run leaves the mosaic after two.

Example 2

Input: mosaic = [[1, 0, 0], [0, 2, 0], [0, 0, 0]]
Output: 3

From the 1 in the corner the run reaches the 2 and then the 0 going down and right, three tiles in all. Turning at the 2 reaches the other 0 instead, which is no longer.

Example 3

Input: mosaic = [[1, 1], [1, 1]]
Output: 1

Every tile is marked 1, so no run can take a second step, and a lone 1 counts as a bend of one.

Constraints

1 <= mosaic.length <= 500
1 <= mosaic[i].length <= 500
mosaic[i][j] is 0, 1 or 2

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 len_of_v_diagonal(mosaic: list[list[int]]) -> int:

Java

public int lenOfVDiagonal(int[][] mosaic)

The intended approach

Time O(rows * cols) with a fixed number of tables.Space O(rows * cols) per table.

How far a bend can carry on from a tile depends on four things and nothing else: the tile, the direction of travel, whether the turn has been spent, and which mark is due next. The mark due next is only ever `2` or `0`, so that is four states per tile and thirty-two tables in total, each holding the longest run onwards. Two of those states matter differently. With the turn already spent, a tile's run onwards depends only on the next tile in the same direction, so those tables settle by themselves. With the turn still in hand, a tile's run onwards is the better of carrying straight on, which needs the same table, and turning, which needs the turned direction's spent table. So fill every spent table first and every unspent one after, and nothing is ever wanted before it is ready. Within one table the order is settled by the row. A direction moves the row by one, always the same way, so sweeping the rows against that movement means the tile a state depends on is already filled. Columns need no ordering of their own, since the row always changes. The answer then reads off the unspent tables: for each tile marked `1`, step once in each of the four directions and take one plus whatever that neighbour promises with `2` due next. A lone `1` with nowhere to go still counts as one.

Pythonentry point: len_of_v_diagonal

def len_of_v_diagonal(mosaic):
    rows = len(mosaic)
    cols = len(mosaic[0])
    steps = ((1, 1), (1, -1), (-1, -1), (-1, 1))
    turn = (1, 2, 3, 0)
    marks = (2, 0)
    table = {}
    for bent in (1, 0):
        for d in range(4):
            dr, dc = steps[d]
            if dr == 1:
                sweep = range(rows - 1, -1, -1)
            else:
                sweep = range(rows)
            pair = [[[0] * cols for _ in range(rows)], [[0] * cols for _ in range(rows)]]
            for r in sweep:
                for c in range(cols):
                    for w in (0, 1):
                        if mosaic[r][c] != marks[w]:
                            continue
                        run = 1
                        nr = r + dr
                        nc = c + dc
                        if 0 <= nr < rows and 0 <= nc < cols:
                            tail = 1 + pair[1 - w][nr][nc]
                            if tail > run:
                                run = tail
                        if bent == 0:
                            e = turn[d]
                            er, ec = steps[e]
                            nr = r + er
                            nc = c + ec
                            if 0 <= nr < rows and 0 <= nc < cols:
                                tail = 1 + table[(e, 1)][1 - w][nr][nc]
                                if tail > run:
                                    run = tail
                        pair[w][r][c] = run
            table[(d, bent)] = pair
    answer = 0
    for r in range(rows):
        for c in range(cols):
            if mosaic[r][c] != 1:
                continue
            if answer < 1:
                answer = 1
            for d in range(4):
                dr, dc = steps[d]
                nr = r + dr
                nc = c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    run = 1 + table[(d, 0)][0][nr][nc]
                    if run > answer:
                        answer = run
    return answer

The obvious version

Walk every bend out by hand. From each tile marked `1`, set off in each of the four directions and follow the run tile by tile, checking the mark due next, and at every tile also try spending the turn and following the turned direction to its end. Nothing is remembered between walks, so the same tiles are re-walked over and over.

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_len_of_v_diagonal(mosaic):
    rows = len(mosaic)
    cols = len(mosaic[0])
    steps = ((1, 1), (1, -1), (-1, -1), (-1, 1))
    turn = (1, 2, 3, 0)

    def walk(r, c, d, bent, want):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return 0
        if mosaic[r][c] != want:
            return 0
        due = 2 if want == 0 else 0
        dr, dc = steps[d]
        run = 1 + walk(r + dr, c + dc, d, bent, due)
        if not bent:
            e = turn[d]
            er, ec = steps[e]
            other = 1 + walk(r + er, c + ec, e, True, due)
            if other > run:
                run = other
        return run

    answer = 0
    for r in range(rows):
        for c in range(cols):
            if mosaic[r][c] != 1:
                continue
            if answer < 1:
                answer = 1
            for d in range(4):
                dr, dc = steps[d]
                run = 1 + walk(r + dr, c + dc, d, False, 2)
                if run > answer:
                    answer = run
    return answer

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