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 thesequence in the same diagonal direction.
    • Makesat 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

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6
7

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

1
2
3
4
5

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.

Examples

Solution

Method 1 – DP with Memoization and Diagonal Traversal

Intuition

We need to find the longest V-shaped diagonal segment, which can start in any of the four diagonal directions and make at most one clockwise turn. The sequence must alternate as 1,2,0,2,0,… and the turn must be tracked. We use DP with memoization to avoid recomputation for each cell, direction, and turn state.

Approach

  1. Define directions for all four diagonals: (1,1), (1,-1), (-1,1), (-1,-1).
  2. For each cell, try starting a segment if the value is 1.
  3. Use a recursive DP function with memoization: dp(r, c, dir, turned, idx) where:
    • r, c: current cell
    • dir: current direction (0-3)
    • turned: whether a turn has been made (0 or 1)
    • idx: index in the sequence (0 for 1, 1 for 2, 2 for 0, then alternate 1/2)
  4. At each step, try to continue in the same direction, or if not turned yet, make a clockwise turn to the next diagonal direction.
  5. Only proceed if the cell matches the expected value in the sequence.
  6. Track and return the maximum segment length found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int longestVSegment(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<pair<int,int>> dirs = {{1,1},{1,-1},{-1,1},{-1,-1}};
        map<tuple<int,int,int,int,int>,int> memo;
        function<int(int,int,int,int,int)> dp = [&](int r, int c, int d, int turned, int idx) -> int {
            if (r < 0 || r >= n || c < 0 || c >= m) return 0;
            int expect = idx == 0 ? 1 : (idx%2 ? 2 : 0);
            if (grid[r][c] != expect) return 0;
            auto key = make_tuple(r,c,d,turned,idx);
            if (memo.count(key)) return memo[key];
            int res = 1;
            // Continue in same direction
            res = max(res, 1 + dp(r+dirs[d].first, c+dirs[d].second, d, turned, idx==0?1:3-idx));
            // Try turn if not turned yet
            if (!turned) {
                int nd = (d+1)%4;
                res = max(res, 1 + dp(r+dirs[nd].first, c+dirs[nd].second, nd, 1, idx==0?1:3-idx));
            }
            return memo[key] = res;
        };
        int ans = 0;
        for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (grid[i][j] == 1)
            for (int d = 0; d < 4; ++d)
                ans = max(ans, dp(i,j,d,0,0));
        return ans >= 2 ? ans : 0;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

func longestVSegment(grid [][]int) int {
    n, m := len(grid), len(grid[0])
    dirs := [][2]int{{1,1},{1,-1},{-1,1},{-1,-1}}
    memo := map[[5]int]int{}
    var dp func(r, c, d, turned, idx int) int
    dp = func(r, c, d, turned, idx int) int {
        if r < 0 || r >= n || c < 0 || c >= m { return 0 }
        expect := 1
        if idx != 0 { if idx%2 == 1 { expect = 2 } else { expect = 0 } }
        if grid[r][c] != expect { return 0 }
        key := [5]int{r,c,d,turned,idx}
        if v, ok := memo[key]; ok { return v }
        res := 1
        ni, nj := r+dirs[d][0], c+dirs[d][1]
        nextIdx := 1; if idx != 0 { nextIdx = 3-idx }
        res = max(res, 1+dp(ni, nj, d, turned, nextIdx))
        if turned == 0 {
            nd := (d+1)%4
            ni2, nj2 := r+dirs[nd][0], c+dirs[nd][1]
            res = max(res, 1+dp(ni2, nj2, nd, 1, nextIdx))
        }
        memo[key] = res
        return res
    }
    ans := 0
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if grid[i][j] == 1 {
                for d := 0; d < 4; d++ {
                    ans = max(ans, dp(i,j,d,0,0))
                }
            }
        }
    }
    if ans < 2 { return 0 }
    return ans
}
func max(a, b int) int { if a > b { return a } else { return b } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    public int longestVSegment(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[][] dirs = {{1,1},{1,-1},{-1,1},{-1,-1}};
        Map<String,Integer> memo = new HashMap<>();
        class Dp {
            int call(int r, int c, int d, int turned, int idx) {
                if (r < 0 || r >= n || c < 0 || c >= m) return 0;
                int expect = idx == 0 ? 1 : (idx%2 == 1 ? 2 : 0);
                if (grid[r][c] != expect) return 0;
                String key = r+","+c+","+d+","+turned+","+idx;
                if (memo.containsKey(key)) return memo.get(key);
                int res = 1;
                int ni = r+dirs[d][0], nj = c+dirs[d][1];
                int nextIdx = idx==0?1:3-idx;
                res = Math.max(res, 1+call(ni, nj, d, turned, nextIdx));
                if (turned == 0) {
                    int nd = (d+1)%4;
                    int ni2 = r+dirs[nd][0], nj2 = c+dirs[nd][1];
                    res = Math.max(res, 1+call(ni2, nj2, nd, 1, nextIdx));
                }
                memo.put(key, res);
                return res;
            }
        }
        int ans = 0;
        Dp dp = new Dp();
        for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (grid[i][j] == 1)
            for (int d = 0; d < 4; ++d)
                ans = Math.max(ans, dp.call(i,j,d,0,0));
        return ans >= 2 ? ans : 0;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    fun longestVSegment(grid: Array<IntArray>): Int {
        val n = grid.size; val m = grid[0].size
        val dirs = arrayOf(intArrayOf(1,1), intArrayOf(1,-1), intArrayOf(-1,1), intArrayOf(-1,-1))
        val memo = mutableMapOf<List<Int>,Int>()
        fun dp(r: Int, c: Int, d: Int, turned: Int, idx: Int): Int {
            if (r !in 0 until n || c !in 0 until m) return 0
            val expect = if (idx == 0) 1 else if (idx%2 == 1) 2 else 0
            if (grid[r][c] != expect) return 0
            val key = listOf(r,c,d,turned,idx)
            memo[key]?.let { return it }
            var res = 1
            val ni = r+dirs[d][0]; val nj = c+dirs[d][1]
            val nextIdx = if (idx == 0) 1 else 3-idx
            res = maxOf(res, 1+dp(ni, nj, d, turned, nextIdx))
            if (turned == 0) {
                val nd = (d+1)%4
                val ni2 = r+dirs[nd][0]; val nj2 = c+dirs[nd][1]
                res = maxOf(res, 1+dp(ni2, nj2, nd, 1, nextIdx))
            }
            memo[key] = res
            return res
        }
        var ans = 0
        for (i in 0 until n) for (j in 0 until m) if (grid[i][j] == 1)
            for (d in 0..3)
                ans = maxOf(ans, dp(i,j,d,0,0))
        return if (ans >= 2) ans else 0
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def longestVSegment(self, grid: list[list[int]]) -> int:
        from functools import lru_cache
        n, m = len(grid), len(grid[0])
        dirs = [(1,1),(1,-1),(-1,1),(-1,-1)]
        @lru_cache(maxsize=None)
        def dp(r: int, c: int, d: int, turned: int, idx: int) -> int:
            if not (0 <= r < n and 0 <= c < m): return 0
            expect = 1 if idx == 0 else (2 if idx%2 else 0)
            if grid[r][c] != expect: return 0
            res = 1
            ni, nj = r+dirs[d][0], c+dirs[d][1]
            next_idx = 1 if idx == 0 else 3-idx
            res = max(res, 1+dp(ni, nj, d, turned, next_idx))
            if not turned:
                nd = (d+1)%4
                ni2, nj2 = r+dirs[nd][0], c+dirs[nd][1]
                res = max(res, 1+dp(ni2, nj2, nd, 1, next_idx))
            return res
        ans = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    for d in range(4):
                        ans = max(ans, dp(i,j,d,0,0))
        return ans if ans >= 2 else 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

impl Solution {
    pub fn longest_v_segment(grid: Vec<Vec<i32>>) -> i32 {
        use std::collections::HashMap;
        let n = grid.len();
        let m = grid[0].len();
        let dirs = [(1,1),(1,-1),(-1,1),(-1,-1)];
        let mut memo = HashMap::new();
        fn dp(r: i32, c: i32, d: usize, turned: i32, idx: i32, grid: &Vec<Vec<i32>>, memo: &mut HashMap<(i32,i32,usize,i32,i32),i32>) -> i32 {
            let n = grid.len() as i32;
            let m = grid[0].len() as i32;
            if r < 0 || r >= n || c < 0 || c >= m { return 0; }
            let expect = if idx == 0 { 1 } else if idx%2 == 1 { 2 } else { 0 };
            if grid[r as usize][c as usize] != expect { return 0; }
            let key = (r,c,d,turned,idx);
            if let Some(&v) = memo.get(&key) { return v; }
            let mut res = 1;
            let (dr, dc) = dirs[d];
            let ni = r+dr; let nj = c+dc;
            let next_idx = if idx == 0 { 1 } else { 3-idx };
            res = res.max(1+dp(ni, nj, d, turned, next_idx, grid, memo));
            if turned == 0 {
                let nd = (d+1)%4;
                let (ndr, ndc) = dirs[nd];
                let ni2 = r+ndr; let nj2 = c+ndc;
                res = res.max(1+dp(ni2, nj2, nd, 1, next_idx, grid, memo));
            }
            memo.insert(key, res);
            res
        }
        let mut ans = 0;
        for i in 0..n as i32 {
            for j in 0..m as i32 {
                if grid[i as usize][j as usize] == 1 {
                    for d in 0..4 {
                        ans = ans.max(dp(i,j,d,0,0,&grid,&mut memo));
                    }
                }
            }
        }
        if ans >= 2 { ans } else { 0 }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    longestVSegment(grid: number[][]): number {
        const n = grid.length, m = grid[0].length;
        const dirs = [[1,1],[1,-1],[-1,1],[-1,-1]];
        const memo = new Map<string, number>();
        function dp(r: number, c: number, d: number, turned: number, idx: number): number {
            if (r < 0 || r >= n || c < 0 || c >= m) return 0;
            const expect = idx === 0 ? 1 : (idx%2 ? 2 : 0);
            if (grid[r][c] !== expect) return 0;
            const key = `${r},${c},${d},${turned},${idx}`;
            if (memo.has(key)) return memo.get(key)!;
            let res = 1;
            const [dr, dc] = dirs[d];
            const ni = r+dr, nj = c+dc;
            const nextIdx = idx === 0 ? 1 : 3-idx;
            res = Math.max(res, 1+dp(ni, nj, d, turned, nextIdx));
            if (!turned) {
                const nd = (d+1)%4;
                const [ndr, ndc] = dirs[nd];
                const ni2 = r+ndr, nj2 = c+ndc;
                res = Math.max(res, 1+dp(ni2, nj2, nd, 1, nextIdx));
            }
            memo.set(key, res);
            return res;
        }
        let ans = 0;
        for (let i = 0; i < n; ++i) for (let j = 0; j < m; ++j) if (grid[i][j] === 1)
            for (let d = 0; d < 4; ++d)
                ans = Math.max(ans, dp(i,j,d,0,0));
        return ans >= 2 ? ans : 0;
    }
}

Complexity

  • ⏰ Time complexity: O(n*m*4*2*2), where n, m are grid dimensions. Each state is memoized.
  • 🧺 Space complexity: O(n*m*4*2*2), for the memoization table.