#3459

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Length of Longest V-Shaped Diagonal Segment

Compute the maximum length of a V-shaped diagonal segment in a 2D integer matrix using state transition dynamic programming.

array dynamic programming memoization matrix

Problem Statement

You are given a 2D integer matrix grid of size n x m with elements 0, 1, or 2. A V-shaped diagonal segment consists of two diagonal lines meeting at a single 90-degree turn, forming a V. The segment must follow the diagonals exactly and may change direction only once at the turning point.

Return the length of the longest V-shaped diagonal segment present in the grid. If no valid V-shaped segment exists, return 0. Each segment must start and end within the bounds of the grid and include the turning point in its total length.

Examples

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

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

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

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) .

Constraints

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

Solution Approach

Dynamic Programming Forward Scan

Compute the length of diagonals in both top-left to bottom-right and top-right to bottom-left directions. Use a DP matrix to record the longest diagonal segments ending at each cell. This precomputation enables fast calculation of combined V-shaped lengths.

Identify Optimal Turning Points

Iterate through all cells as potential turning points. At each cell, combine precomputed diagonal lengths from forward and backward DP arrays to evaluate the total length of a V-shaped segment. Keep track of the maximum value encountered.

Memoization for Efficiency

Use memoization to store intermediate results for each diagonal direction to avoid recomputation. This ensures the algorithm scales efficiently with large grids, maintaining O(n*m) time complexity while preventing redundant recalculation of overlapping diagonals.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n m) because each cell is processed once in both forward and backward DP passes. Space complexity is O(n m) for the memoization matrices storing diagonal lengths in both directions.

What Interviewers Usually Probe

Candidate identifies the DP pattern connecting diagonals and turning points.
Candidate efficiently combines forward and backward memoized paths.
Candidate correctly handles edge cells and ensures proper boundary checks.

Common Pitfalls or Variants

Common pitfalls

Forgetting to include the turning point in the total length calculation.
Confusing diagonal directions leading to incorrect segment lengths.
Inefficient recomputation of overlapping diagonals without memoization.

Follow-up variants

Compute longest inverted V-shaped or Λ-shaped segments.
Find longest diagonal segments without a turn for simpler DP.
Determine longest segment allowing multiple 90-degree turns.

FAQ

What defines a V-shaped diagonal segment in this problem?

A V-shaped diagonal segment consists of two diagonal lines meeting at a 90-degree turn, forming a V, fully within the grid.

What is the primary approach for Length of Longest V-Shaped Diagonal Segment?

Use state transition dynamic programming with memoization to calculate longest diagonal segments and combine them at each potential turning point.

How do I handle grid boundaries when scanning diagonals?

Ensure each diagonal scan stays within the grid limits and avoid indexing beyond 0 to n-1 or 0 to m-1.

Can a V-shaped segment consist of a single diagonal without a turn?

No, a valid V-shaped segment requires two connected diagonals with exactly one 90-degree turn.

What are common mistakes in this problem?

Common mistakes include not counting the turning cell, confusing diagonal directions, and recomputing lengths without memoization.

terminal

Solution

Solution 1: Memoized Search

We design a function $\text{dfs}(i, j, k, \textit{cnt})$ that returns the length of the longest V-shaped diagonal segment, where $(i, j)$ is the previous position, $k$ is the current direction, and $\textit{cnt}$ is the remaining number of allowed turns.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def lenOfVDiagonal(self, grid: List[List[int]]) -> int:
        @cache
        def dfs(i: int, j: int, k: int, cnt: int) -> int:
            x, y = i + dirs[k], j + dirs[k + 1]
            target = 2 if grid[i][j] == 1 else (2 - grid[i][j])
            if not 0 <= x < m or not 0 <= y < n or grid[x][y] != target:
                return 0
            res = dfs(x, y, k, cnt)
            if cnt > 0:
                res = max(res, dfs(x, y, (k + 1) % 4, 0))
            return 1 + res

        m, n = len(grid), len(grid[0])
        dirs = (1, 1, -1, -1, 1)
        ans = 0
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x == 1:
                    for k in range(4):
                        ans = max(ans, dfs(i, j, k, 1) + 1)
        return ans

Continue Practicing

#2713 maximum strictly increasing cells in a matrix #3418 maximum amount of money robot can earn #3393 count paths with the given xor value