3459. Length of Longest V-Shaped Diagonal Segment

Description

You are given a 2D integer matrix grid of size n x m, where each element is either 0, 1, or 2.

A V-shaped diagonal segment is defined as:

• The segment starts with 1.
• The subsequent elements follow this infinite sequence: 2, 0, 2, 0, ....
• The segment:
  • Starts along a diagonal direction (top-left to bottom-right, bottom-right to top-left, top-right to bottom-left, or bottom-left to top-right).
  • Continues the sequence in the same diagonal direction.
  • Makes at most one clockwise 90-degree turn to another diagonal direction while maintaining the sequence.

Return the length of the longest V-shaped diagonal segment. If no valid segment exists, return 0.

 

Example 1:

Input: grid = [[2,2,1,2,2],[2,0,2,2,0],[2,0,1,1,0],[1,0,2,2,2],[2,0,0,2,2]]

Output: 5

Explanation:

The longest V-shaped diagonal segment has a length of 5 and follows these coordinates: (0,2) → (1,3) → (2,4), takes a 90-degree clockwise turn at (2,4), and continues as (3,3) → (4,2).

Example 2:

Input: grid = [[2,2,2,2,2],[2,0,2,2,0],[2,0,1,1,0],[1,0,2,2,2],[2,0,0,2,2]]

Output: 4

Explanation:

The longest V-shaped diagonal segment has a length of 4 and follows these coordinates: (2,3) → (3,2), takes a 90-degree clockwise turn at (3,2), and continues as (2,1) → (1,0).

Example 3:

Input: grid = [[1,2,2,2,2],[2,2,2,2,0],[2,0,0,0,0],[0,0,2,2,2],[2,0,0,2,0]]

Output: 5

Explanation:

The longest V-shaped diagonal segment has a length of 5 and follows these coordinates: (0,0) → (1,1) → (2,2) → (3,3) → (4,4).

Example 4:

Input: grid = [[1]]

Output: 1

Explanation:

The longest V-shaped diagonal segment has a length of 1 and follows these coordinates: (0,0).

 

Constraints:

• n == grid.length
• m == grid[i].length
• 1 <= n, m <= 500
• grid[i][j] is either 0, 1 or 2.

Solutions

Solution 1

Python3JavaC++Go

class Solution:
    def lenOfVDiagonal(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        next_digit = {1: 2, 2: 0, 0: 2}

        def within_bounds(i, j):
            return 0 <= i < m and 0 <= j < n

        @cache
        def f(i, j, di, dj, turned):
            result = 1
            successor = next_digit[grid[i][j]]

            if within_bounds(i + di, j + dj) and grid[i + di][j + dj] == successor:
                result = 1 + f(i + di, j + dj, di, dj, turned)

            if not turned:
                di, dj = dj, -di
                if within_bounds(i + di, j + dj) and grid[i + di][j + dj] == successor:
                    result = max(result, 1 + f(i + di, j + dj, di, dj, True))

            return result

        directions = ((1, 1), (-1, 1), (1, -1), (-1, -1))
        result = 0

        for i in range(m):
            for j in range(n):
                if grid[i][j] != 1:
                    continue
                for di, dj in directions:
                    result = max(result, f(i, j, di, dj, False))

        return result

Comments