Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

After the initial one, the required values alternate between two and zero. A continuation is determined by its cell, expected value, diagonal direction, and whether the single clockwise turn has been used. Many starting points can share the same continuation, so memoization avoids repeating that work.

Approach

List the four diagonal directions in clockwise order. Define a cached search that returns zero for an out-of-bounds cell or a wrong value. For a matching cell, count it and switch the next expected value between two and zero.

Always try continuing in the same direction. If the turn is still unused, also try the next direction in clockwise order and mark the turn used. Return the longer continuation. From every cell containing one, try each initial direction toward an expected two and add one for the starting cell.

Take the largest result. A lone one is valid because failed continuations contribute zero; a grid without any one returns zero. The state permits at most one clockwise turn and never a counterclockwise turn.

class Solution:
    def lenOfVDiagonal(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        dirs = [(-1, -1), (-1, 1), (1, 1), (1, -1)] # follow clockwise order | tl, tr, br, bl

        @cache
        def dfs(i, j, target, turn, dir):
            if i < 0 or i >= n or j < 0 or j >= m or grid[i][j] != target:
                return 0

            target = 0 if target == 2 else 2
            ni = i + dirs[dir][0]
            nj = j + dirs[dir][1]
            total = 0
            if turn:
                # move in the same direction
                total = max(total, dfs(ni, nj, target, True, dir) + 1)
            else:
                # move in the same direction
                total = max(total, dfs(ni, nj, target, False, dir) + 1)
                # change direction
                new_d = (dir + 1) % 4
                ni = i + dirs[new_d][0]
                nj = j + dirs[new_d][1]
                total = max(total, dfs(ni, nj, target, True, new_d) + 1)

            return total

        res = 0

        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    for d in range(4):
                        res = max(res, dfs(i + dirs[d][0], j + dirs[d][1], 2, False, d) + 1)

        return res

Complexity analysis

Let r and c be the grid dimensions. Time: O(r * c) because direction, turn, and target state counts are constant. Auxiliary space: O(r * c) for memoized DFS states and recursion.