# Length of Longest V-Shaped Diagonal Segment
**Difficulty:** HARD
[External](https://leetcode.com/problems/length-of-longest-v-shaped-diagonal-segment)
Canonical: https://scaleengineer.com/dsa/problems/length-of-longest-v-shaped-diagonal-segment
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Data structures:** Array, Matrix
**Companies:** [Visa](https://scaleengineer.com/companies/visa)
---
## Problem
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.

![](https://assets.glich.co/dsa/length-of-longest-v-shaped-diagonal-segment/image0.jpg)

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:**

![](https://assets.glich.co/dsa/length-of-longest-v-shaped-diagonal-segment/image1.jpg)

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:**

**![](https://assets.glich.co/dsa/length-of-longest-v-shaped-diagonal-segment/image2.jpg)**

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:**

**![](https://assets.glich.co/dsa/length-of-longest-v-shaped-diagonal-segment/image3.jpg)**

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

# Approaches
## Dynamic Programming with Iteration
This approach improves upon a pure brute-force solution by using dynamic programming to pre-calculate the lengths of all possible straight diagonal segments that start with a `1` and follow the required sequence. After this pre-computation, it iterates through every cell, considering it as a potential turning point for a V-shape. For each potential turn, it combines a pre-calculated segment (the first leg) with a second leg whose length is found by iterative traversal.
**Time:** O(n * m * (n + m)). The pre-computation of the four DP tables takes O(n * m) time. The main cost comes from the V-shape calculation, where we iterate through each of the n*m cells. At each cell, we potentially start an iterative search for the second leg, which can take up to O(n + m) time in the worst case. · **Space:** O(n * m) to store the four DP tables for the lengths of straight segments.
**Pros:** Much more efficient than a naive brute-force approach.; Systematically explores all possibilities without redundant calculations of the first leg of the V-shape.
**Cons:** The second leg of the V-shape is calculated iteratively for each potential turning point, leading to repeated traversals over the same cells.; The time complexity can be prohibitive for very large grids, although it might pass for the given constraints.
### Explanation
The core idea is to break down the problem into two main parts: finding all valid straight segments and then combining them to form V-shapes.

1.  **Pre-computation of Straight Segments:**
    We use four 2D DP arrays, one for each of the four diagonal directions (Top-Left to Bottom-Right, Top-Right to Bottom-Left, etc.). Let's denote them `L_tl`, `L_tr`, `L_bl`, `L_br`. `L_tl[r][c]` will store the length of a valid straight diagonal segment ending at cell `(r, c)` and arriving from the top-left.

    The calculation is as follows: To compute `L_tl[r][c]`, we look at the previous cell in that diagonal, `(r-1, c-1)`. If a valid segment of length `k` ends there (i.e., `L_tl[r-1][c-1] = k > 0`), and the value at `grid[r][c]` matches the expected value at index `k` of the sequence (`1, 2, 0, 2, 0, ...`), then we can extend the segment. The new length at `(r, c)` becomes `k + 1`. If `grid[r][c]` is `1`, it can start a new segment of length 1. Otherwise, no valid segment ends at `(r, c)` from this direction.

    We fill these four DP tables by iterating through the grid in appropriate orders. While filling, we also keep track of the maximum length found so far, which covers all straight-line segments (V-shapes with zero turns).

2.  **Finding V-Shapes:**
    After the DP tables are filled, we iterate through every cell `(r, c)` in the grid, treating it as a potential pivot point of a V-shape. For each of the four possible incoming diagonal directions, we get the length of the first leg from our pre-computed DP tables (e.g., `len1 = L_tl[r][c]`).

    If a valid first leg exists (`len1 > 0`), we then simulate the second leg. A 90-degree clockwise turn from the incoming direction determines the direction of the second leg. We then iteratively traverse from `(r, c)` in this new direction, checking if the grid values match the required sequence, which now continues from index `len1`. The length of this second leg (`len2`) is calculated. The total length of the V-shape is `len1 + len2`. We update our global maximum length with this value.

This process is repeated for all cells and all four possible turns at each cell.
### Algorithm
1.  Initialize `maxLength = 0`.
2.  Define a helper function `getExpectedValue(index)` that returns the expected grid value for a given position in the sequence (`1` for index 0, `2` for odd indices > 0, `0` for even indices > 0).
3.  Create four 2D DP arrays of size `n x m`: `L_tl`, `L_tr`, `L_bl`, `L_br` to store lengths of straight segments ending at `(r, c)` from the four diagonal directions.
4.  **Pre-computation Pass:**
    -   Calculate `L_tl` and `L_tr` by iterating `r` from `0` to `n-1` and `c` from `0` to `m-1`.
    -   Calculate `L_bl` and `L_br` by iterating `r` from `n-1` to `0` and `c` from `m-1` to `0` (or any other valid traversal order).
    -   For each cell `(r, c)`, update the DP value based on the previous diagonal cell's DP value and `grid[r][c]`. If `grid[r][c] == 1`, a new segment of length 1 starts.
    -   Update `maxLength = max(maxLength, dp_value)` after each calculation.
5.  **V-Shape Pass:**
    -   Iterate through each cell `(r, c)` from `(0, 0)` to `(n-1, m-1)`.
    -   For each of the four incoming directions (e.g., from Top-Left):
        a.  Get the length of the first leg, `len1`, from the corresponding DP table (e.g., `L_tl[r][c]`).
        b.  If `len1 > 0`:
            i.  Determine the new direction `(dr, dc)` after a 90-degree clockwise turn.
            ii. Initialize `len2 = 0`, `currentIndex = len1`, `currR = r`, `currC = c`.
            iii. Loop: Move to `(currR + dr, currC + dc)`. If it's in bounds and the value matches `getExpectedValue(currentIndex)`, increment `len2` and `currentIndex`, and update `(currR, currC)`. Otherwise, break.
            iv. Update `maxLength = max(maxLength, len1 + len2)`.
6.  Return `maxLength`.

## Full Dynamic Programming
This is the most efficient approach, which uses dynamic programming to pre-calculate the lengths of all possible segments, both for the first and second legs of a V-shape. By investing in a more comprehensive pre-computation phase, we can find the length of the longest V-shape by simply combining the pre-calculated values in constant time for each potential turning point, thus avoiding any iterative traversals during the final combination step.
**Time:** O(n * m). Each of the 12 DP tables is computed in O(n * m) time. The final combination step also takes O(n * m) time as it involves a simple lookup for each cell and direction. The total time complexity is dominated by these linear scans of the grid. · **Space:** O(n * m). We use 12 DP tables, each of size n x m. The space required is therefore proportional to the size of the grid.
**Pros:** Optimal time complexity.; Each phase of the algorithm (pre-computation, combination) is clean and efficient.; Avoids all redundant computations by leveraging DP tables for all segment types.
**Cons:** Requires significant memory to store 12 DP tables, which might be an issue for extremely large grids, though acceptable for the given constraints.; The implementation is more complex due to the need to manage multiple DP tables and different traversal orders.
### Explanation
This approach extends the previous one by eliminating the iterative search for the second leg of the V-shape. It does so by pre-calculating the lengths of all possible second legs as well.

We define three sets of DP tables:
1.  **`L[r][c][dir]`**: Stores the length of a valid segment starting with `1` (`1, 2, 0, ...` sequence) that *ends* at `(r, c)`, arriving from direction `dir`. This is identical to the DP tables in the previous approach and represents the first leg of a V-shape.

2.  **`S[r][c][dir]`**: Stores the length of a valid segment that *starts* at `(r, c)` with the value `2` and continues with the sequence `0, 2, 0, ...` along direction `dir`.

3.  **`T[r][c][dir]`**: Stores the length of a valid segment that *starts* at `(r, c)` with the value `0` and continues with the sequence `2, 0, 2, ...` along direction `dir`.

The `S` and `T` tables are mutually dependent. For example, to calculate `S` for a direction (e.g., towards bottom-right), `S_br[r][c]` will be `1 + T_br[r+1][c+1]` if `grid[r][c]` is `2`, and `0` otherwise. Similarly, `T_br[r][c]` depends on `S_br` at the next cell. These tables can be filled by iterating through the grid in the reverse order of the direction of traversal.

**The Algorithm:**
1.  **Pre-computation:**
    -   First, compute the four `L` tables, one for each incoming direction, just like in the previous approach. While doing so, update a `maxLength` variable to account for all straight-line segments.
    -   Next, compute the `S` and `T` tables. For each of the four diagonal directions, we need one `S` and one `T` table (total of 8 tables). These are computed by iterating in the reverse direction (e.g., for segments going towards the bottom-right, we iterate from the bottom-right of the grid backwards).

2.  **Combination:**
    -   Iterate through every cell `(r, c)` of the grid, considering it as the pivot of a V-shape.
    -   For each of the four possible incoming directions `d_in`:
        a.  Get the length of the first leg: `len1 = L[r][c][d_in]`.
        b.  If `len1 > 0`, it means a valid first leg ends at `(r, c)`.
        c.  The second leg starts at the cell adjacent to `(r, c)` in the turned direction `d_out`. The expected value at this next cell depends on `len1`. If `len1` is odd, the next value should be `2`; if even, it should be `0`.
        d.  We check if the value at the next cell matches the expectation. If it does, we can find the length of the rest of the second leg (`len2`) in `O(1)` time by looking it up in the pre-computed `S` or `T` tables for direction `d_out` at that next cell's coordinates.
        e.  The total length is `len1 + len2`. We update `maxLength` with this combined length.

After checking all cells as potential pivots, `maxLength` will hold the length of the longest V-shaped segment.
### Algorithm
1.  Initialize `maxLength = 0`, grid dimensions `n`, `m`.
2.  Define direction vectors `dr`, `dc` for the four diagonal directions.
3.  Create DP tables:
    -   `L[n][m][4]`: For first legs (sequence `1, 2, 0, ...`).
    -   `S[n][m][4]`: For second legs starting with `2` (`2, 0, 2, ...`).
    -   `T[n][m][4]`: For second legs starting with `0` (`0, 2, 0, ...`).
4.  **Compute `L` tables:**
    -   Iterate through the grid (e.g., top-to-bottom, left-to-right for directions from top) and fill `L` tables. Update `maxLength` with each `L` value.
5.  **Compute `S` and `T` tables:**
    -   Iterate through the grid in reverse orders (e.g., bottom-to-top, right-to-left for directions towards bottom-right) and fill `S` and `T` tables based on their recursive definitions.
6.  **Combine for V-shapes:**
    -   Iterate `r` from `0` to `n-1` and `c` from `0` to `m-1`.
    -   For each incoming direction `d_in` from `0` to `3`:
        a.  `len1 = L[r][c][d_in]`.
        b.  If `len1 > 0`:
            i.  `d_out = (d_in + 1) % 4` (clockwise turn).
            ii. `nextR = r + dr[d_out]`, `nextC = c + dc[d_out]`.
            iii. If `(nextR, nextC)` is in bounds:
                -   `expected = (len1 % 2 == 1) ? 2 : 0`.
                -   If `grid[nextR][nextC] == expected`:
                    -   `len2 = (expected == 2) ? S[nextR][nextC][d_out] : T[nextR][nextC][d_out]`.
                    -   `maxLength = max(maxLength, len1 + len2)`.
7.  Return `maxLength`.

# Solutions
### Python

```python
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

```