3459. Length of Longest V-Shaped Diagonal Segment
Hard
50 Points
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:
Return the length of the longest V-shaped diagonal segment. If no valid segment exists, return 0.
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
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.lengthm == grid[i].length1 <= n, m <= 500grid[i][j] is either 0, 1 or 2.
3459. Length of Longest V-Shaped Diagonal Segment
Hard
50 Points
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:
Return the length of the longest V-shaped diagonal segment. If no valid segment exists, return 0.
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
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.lengthm == grid[i].length1 <= n, m <= 500grid[i][j] is either 0, 1 or 2.