Length of Longest V-Shaped Diagonal Segment
Source: leetcode
Difficulty: Hard
Tags: array, dynamic-programming, memoization, matrix

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.leetcode.com/uploads/2025/01/11/length_of_longest3.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.leetcode.com/uploads/2024/12/09/matrix_1-2.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.leetcode.com/uploads/2024/12/09/matrix_2.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.leetcode.com/uploads/2024/12/09/matrix_3.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`.




C++ solution:
class Solution {
public:
    int lenOfVDiagonal(vector<vector<int>>& grid) {
        int n = grid.size();
        if (n == 0) return 0;
        int m = grid[0].size();
        if (m == 0) return 0;

        vector<vector<vector<int>>> len(4, vector<vector<int>>(n, vector<int>(m, 0)));
        vector<pair<int, int>> dirs = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

        for (int d = 0; d < 4; ++d) {
            int dx = dirs[d].first;
            int dy = dirs[d].second;

            int i_start = (dx == 1) ? (n - 1) : 0;
            int i_end = (dx == 1) ? -1 : n;
            int i_step = (dx == 1) ? -1 : 1;

            int j_start = (dy == 1) ? (m - 1) : 0;
            int j_end = (dy == 1) ? -1 : m;
            int j_step = (dy == 1) ? -1 : 1;

            for (int i = i_start; i != i_end; i += i_step) {
                for (int j = j_start; j != j_end; j += j_step) {
                    int v = grid[i][j];
                    int next_expected;

                    if (v == 1) {
                        next_expected = 2;
                    } else if (v == 2) {
                        next_expected = 0;
                    } else if (v == 0) {
                        next_expected = 2;
                    } else {
                        next_expected = -1;
                    }

                    int next_i = i + dx;
                    int next_j = j + dy;

                    if (next_i >= 0 && next_i < n && next_j >= 0 && next_j < m && grid[next_i][next_j] == next_expected) {
                        len[d][i][j] = 1 + len[d][next_i][next_j];
                    } else {
                        len[d][i][j] = (v == 1 || v == 2 || v == 0) ? 1 : 0;
                    }
                }
            }
        }

        int max_length = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] != 1) continue;

                for (int d = 0; d < 4; ++d) {
                    int dx = dirs[d].first;
                    int dy = dirs[d].second;

                    int len1 = len[d][i][j];
                    if (len1 == 0) continue;

                    int current_max = len1;

                    for (int k = 0; k < len1; ++k) {
                        int x = i + k * dx;
                        int y = j + k * dy;

                        if (x < 0 || x >= n || y < 0 || y >= m) break;

                        int next_val;
                        if (k == 0) {
                            next_val = 2;
                        } else {
                            next_val = (k % 2 == 1) ? 0 : 2;
                        }

                        int new_dx = dy;
                        int new_dy = -dx;

                        int new_d = -1;
                        for (int nd = 0; nd < 4; ++nd) {
                            if (dirs[nd].first == new_dx && dirs[nd].second == new_dy) {
                                new_d = nd;
                                break;
                            }
                        }
                        if (new_d == -1) continue;

                        int next_x = x + new_dx;
                        int next_y = y + new_dy;

                        if (next_x < 0 || next_x >= n || next_y < 0 || next_y >= m) continue;
                        if (grid[next_x][next_y] != next_val) continue;

                        int len2 = len[new_d][next_x][next_y];
                        current_max = max(current_max, (k + 1) + len2);
                    }

                    max_length = max(max_length, current_max);
                }
            }
        }

        return max_length;
    }
};

Go solution:
func lenOfVDiagonal(grid [][]int) int {
    n := len(grid)
    if n == 0 {
        return 0
    }
    m := len(grid[0])
    if m == 0 {
        return 0
    }

    directions := [4][2]int{{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}

    steps0 := make([][][]int, n)
    steps2 := make([][][]int, n)
    for i := range steps0 {
        steps0[i] = make([][]int, m)
        steps2[i] = make([][]int, m)
        for j := range steps0[i] {
            steps0[i][j] = make([]int, 4)
            steps2[i][j] = make([]int, 4)
        }
    }

    for d := 0; d < 4; d++ {
        dx, dy := directions[d][0], directions[d][1]
        startX, endX, stepX := n-1, -1, -1
        if dx == -1 {
            startX, endX, stepX = 0, n, 1
        }
        startY, endY, stepY := m-1, -1, -1
        if dy == -1 {
            startY, endY, stepY = 0, m, 1
        }

        for x := startX; x != endX; x += stepX {
            for y := startY; y != endY; y += stepY {
                if grid[x][y] == 0 {
                    steps0[x][y][d] = 1
                    nx, ny := x+dx, y+dy
                    if nx >= 0 && nx < n && ny >= 0 && ny < m {
                        steps0[x][y][d] += steps2[nx][ny][d]
                    }
                } else {
                    steps0[x][y][d] = 0
                }

                if grid[x][y] == 2 {
                    steps2[x][y][d] = 1
                    nx, ny := x+dx, y+dy
                    if nx >= 0 && nx < n && ny >= 0 && ny < m {
                        steps2[x][y][d] += steps0[nx][ny][d]
                    }
                } else {
                    steps2[x][y][d] = 0
                }
            }
        }
    }

    maxLen := 0
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if grid[i][j] != 1 {
                continue
            }

            for d := 0; d < 4; d++ {
                dx, dy := directions[d][0], directions[d][1]
                nextI, nextJ := i+dx, j+dy
                pre := 1
                if nextI >= 0 && nextI < n && nextJ >= 0 && nextJ < m {
                    pre += steps2[nextI][nextJ][d]
                }

                if pre == 0 {
                    continue
                }

                currentMax := pre
                for s := 1; s <= pre; s++ {
                    newX := i + (s-1)*dx + directions[d][1]
                    newY := j + (s-1)*dy - directions[d][0]

                    if newX < 0 || newX >= n || newY < 0 || newY >= m {
                        continue
                    }

                    nextExpected := 2
                    if s%2 == 0 {
                        nextExpected = 0
                    }

                    ndx := directions[d][1]
                    ndy := -directions[d][0]
                    newD := -1
                    for nd := 0; nd < 4; nd++ {
                        if directions[nd][0] == ndx && directions[nd][1] == ndy {
                            newD = nd
                            break
                        }
                    }
                    if newD == -1 {
                        continue
                    }

                    var post int
                    if nextExpected == 0 {
                        post = steps0[newX][newY][newD]
                    } else {
                        post = steps2[newX][newY][newD]
                    }

                    if s+post > currentMax {
                        currentMax = s + post
                    }
                }

                if currentMax > maxLen {
                    maxLen = currentMax
                }
            }
        }
    }

    return maxLen
}

Java solution:
class Solution {
    public int lenOfVDiagonal(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][] dirs = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        int max = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] != 1) continue;
                
                for (int[] dir : dirs) {
                    int dx = dir[0];
                    int dy = dir[1];
                    int steps = 0;
                    
                    while (true) {
                        int nextX = i + (steps + 1) * dx;
                        int nextY = j + (steps + 1) * dy;
                        if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m) break;
                        int step = steps + 1;
                        int expected = (step % 2 == 1) ? 2 : 0;
                        if (grid[nextX][nextY] == expected) {
                            steps++;
                        } else {
                            break;
                        }
                    }
                    
                    int currentMax = steps + 1;
                    
                    for (int t = 0; t <= steps; t++) {
                        int ndx = dy;
                        int ndy = -dx;
                        int x = i + t * dx + ndx;
                        int y = j + t * dy + ndy;
                        if (x < 0 || x >= n || y < 0 || y >= m) continue;
                        int stepInTurn = t + 1;
                        int expected = (stepInTurn % 2 == 1) ? 2 : 0;
                        if (grid[x][y] != expected) continue;
                        
                        int s = 0;
                        while (true) {
                            int nextX = x + (s + 1) * ndx;
                            int nextY = y + (s + 1) * ndy;
                            if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m) break;
                            int step = stepInTurn + (s + 1);
                            expected = (step % 2 == 1) ? 2 : 0;
                            if (grid[nextX][nextY] == expected) {
                                s++;
                            } else {
                                break;
                            }
                        }
                        
                        int total = (t + 1) + (s + 1);
                        if (total > currentMax) {
                            currentMax = total;
                        }
                    }
                    
                    if (currentMax > max) {
                        max = currentMax;
                    }
                }
            }
        }
        
        return max;
    }
}

JavaScript solution:
var lenOfVDiagonal = function(grid) {
    const n = grid.length;
    if (n === 0) return 0;
    const m = grid[0].length;
    let maxLen = 0;
    const directions = [
        { dx: 1, dy: 1 },   // down-right
        { dx: 1, dy: -1 },  // down-left
        { dx: -1, dy: 1 },  // up-right
        { dx: -1, dy: -1 }, // up-left
    ];
    const turnDir = [1, 3, 0, 2]; // new direction after turn for each original direction index

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (grid[i][j] !== 1) continue;
            for (let dirIdx = 0; dirIdx < 4; dirIdx++) {
                const { dx, dy } = directions[dirIdx];
                let s = 0;
                let ci = i, cj = j;
                while (true) {
                    const expected = s === 0 ? 1 : (s - 1) % 2 === 0 ? 2 : 0;
                    if (ci < 0 || ci >= n || cj < 0 || cj >= m) break;
                    if (grid[ci][cj] !== expected) break;
                    s++;
                    ci += dx;
                    cj += dy;
                }
                maxLen = Math.max(maxLen, s);
                for (let t = 1; t <= s; t++) {
                    const currI = i + (t - 1) * dx;
                    const currJ = j + (t - 1) * dy;
                    const newDirIdx = turnDir[dirIdx];
                    const { dx: newDx, dy: newDy } = directions[newDirIdx];
                    let mSteps = 0;
                    let ni = currI, nj = currJ;
                    while (true) {
                        const expected = (t - 1 + mSteps) % 2 === 0 ? 2 : 0;
                        ni += newDx;
                        nj += newDy;
                        if (ni < 0 || ni >= n || nj < 0 || nj >= m) break;
                        if (grid[ni][nj] !== expected) break;
                        mSteps++;
                    }
                    maxLen = Math.max(maxLen, t + mSteps);
                }
            }
        }
    }
    return maxLen;
};

Python solution:
class Solution:
    def lenOfVDiagonal(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n == 0:
            return 0
        m = len(grid[0])
        if m == 0:
            return 0
        
        directions = [ (1, 1), (1, -1), (-1, 1), (-1, -1) ]
        dp = [ [ [ [0]*2 for _ in range(4)] for __ in range(m) ] for ___ in range(n) ]
        
        for dr_idx in range(4):
            dr, dc = directions[dr_idx]
            if dr == 1:
                row_order = range(n-1, -1, -1)
            else:
                row_order = range(n)
            if dc == 1:
                col_order = range(m-1, -1, -1)
            else:
                col_order = range(m)
            
            for x in row_order:
                for y in col_order:
                    for e_idx, e in enumerate([0, 2]):
                        if grid[x][y] != e:
                            dp[x][y][dr_idx][e_idx] = 0
                        else:
                            next_x = x + dr
                            next_y = y + dc
                            if 0 <= next_x < n and 0 <= next_y < m:
                                next_e = 0 if e == 2 else 2
                                next_e_idx = 0 if next_e == 0 else 1
                                dp[x][y][dr_idx][e_idx] = 1 + dp[next_x][next_y][dr_idx][next_e_idx]
                            else:
                                dp[x][y][dr_idx][e_idx] = 1
        
        max_len = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] != 1:
                    continue
                current_max = 1
                for dr_idx in range(4):
                    dr, dc = directions[dr_idx]
                    next_i = i + dr
                    next_j = j + dc
                    if 0 <= next_i < n and 0 <= next_j < m:
                        len1 = 1 + dp[next_i][next_j][dr_idx][1]
                    else:
                        len1 = 1
                    current_max = max(current_max, len1)
                    
                    for s in range(len1):
                        x = i + dr * s
                        y = j + dc * s
                        new_dr = dc
                        new_dc = -dr
                        new_x = x + new_dr
                        new_y = y + new_dc
                        if 0 <= new_x < n and 0 <= new_y < m:
                            k = s + 1
                            e = 2 if k % 2 == 1 else 0
                            if grid[new_x][new_y] != e:
                                continue
                            new_dr_idx = [1, 3, 0, 2][dr_idx]
                            e_idx = 1 if e == 2 else 0
                            len2 = dp[new_x][new_y][new_dr_idx][e_idx]
                            total = (s + 1) + len2
                            current_max = max(current_max, total)
                max_len = max(max_len, current_max)
        
        return max_len

Ruby solution:
def len_of_v_diagonal(grid)
  n = grid.size
  return 0 if n == 0
  m = grid[0].size
  dp = Array.new(4) { Array.new(n) { Array.new(m, 0) } }
  dirs = [[1, 1], [1, -1], [-1, 1], [-1, -1]]
  (0...4).each do |d|
    dx, dy = dirs[d][0], dirs[d][1]
    i_range = dx == 1 ? (n - 1).downto(0) : (0...n)
    j_range = dy == 1 ? (m - 1).downto(0) : (0...m)
    i_range.each do |i|
      j_range.each do |j|
        v = grid[i][j]
        nxt = v == 1 ? 2 : (v == 2 ? 0 : 2)
        ni, nj = i + dx, j + dy
        if ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] == nxt
          dp[d][i][j] = 1 + dp[d][ni][nj]
        else
          dp[d][i][j] = 1
        end
      end
    end
  end
  max_len = 0
  turn = [1, 3, 0, 2]
  (0...n).each do |i|
    (0...m).each do |j|
      next if grid[i][j] != 1
      (0...4).each do |d|
        dx, dy = dirs[d][0], dirs[d][1]
        arm1 = dp[d][i][j]
        max_len = arm1 if arm1 > max_len
        new_d = turn[d]
        ndx, ndy = dirs[new_d][0], dirs[new_d][1]
        s = 1
        while s <= arm1
          x = i + (s - 1) * dx
          y = j + (s - 1) * dy
          new_i = x + ndx
          new_j = y + ndy
          if new_i >= 0 && new_i < n && new_j >= 0 && new_j < m
            exp_val = (s & 1) == 1 ? 2 : 0
            if grid[new_i][new_j] == exp_val
              candidate = s + dp[new_d][new_i][new_j]
              max_len = candidate if candidate > max_len
            end
          end
          s += 1
        end
      end
    end
  end
  max_len
end