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.
Examples
Example 1
$$ \Huge \begin{array}{|c|c|c|c|c|} \hline 2 & 2 & \colorbox{blue}1 & 2 & 2 \\ \hline 2 & 0 & 2 & \colorbox{blue}2 & 0 \\ \hline 2 & 0 & 1 & 1 & \colorbox{blue}0 \\ \hline 1 & 0 & 2 & \colorbox{blue}2 & 2 \\ \hline 2 & 0 & \colorbox{blue}0 & 2 & 2 \\ \hline \end{array} $$
|
|
Example 2
$$ \Huge \begin{array}{|c|c|c|c|c|} \hline 2 & 2 & 2 & 2 & 2 \\ \hline \colorbox{blue}2 & 0 & 2 & 2 & 0 \\ \hline 2 & \colorbox{blue}0 & 1 & \colorbox{blue}1 & 0 \\ \hline 1 & 0 & \colorbox{blue}2 & 2 & 2 \\ \hline 2 & 0 & 0 & 2 & 2 \\ \hline \end{array} $$
|
|
Example 3
$$ \Huge \begin{array}{|c|c|c|c|c|} \hline \colorbox{blue}1 & 2 & 2 & 2 & 2 \\ \hline 2 & \colorbox{blue}2 & 2 & 2 & 0 \\ \hline 2 & 0 & \colorbox{blue}0 & 0 & 0 \\ \hline 0 & 0 & 2 & \colorbox{blue}2 & 2 \\ \hline 2 & 0 & 0 & 2 & \colorbox{blue}0 \\ \hline \end{array} $$
|
|
Example 4
$$ \Huge \begin{array}{|c|} \hline \colorbox{blue}1 \\ \hline \end{array} $$
|
|
Constraints
n == grid.length
m == grid[i].length
1 <= n, m <= 500
grid[i][j]
is either0
,1
or2
.
Solution
Intuition
The core idea is to find the longest valid path in the grid, treating it like a graph. A V-shaped segment is a special path that must start with a 1
, follow a 2, 0, 2, 0...
pattern, and is allowed to make at most one 90-degree clockwise turn.
Since the longest path from any given cell depends on the longest paths from its potential next cells, this problem is a perfect fit for Dynamic Programming. We can explore all possible paths starting from every 1
in the grid using a Depth-First Search (DFS). To avoid re-calculating results for the same state (i.e., the same cell, direction, and turn status), we use memoization.
Approach
-
State Definition: We create a recursive DFS function,
dfs(row, col, direction, can_turn, target)
, that calculates the length of a valid segment starting from the cell(row, col)
.(row, col)
: The coordinates of the current cell.direction
: The current diagonal direction (0-3).can_turn
: A boolean indicating if we are still allowed to make a turn.target
: The value we expect the current cell(row, col)
to have.
-
Memoization: A 4D array,
memo[row][col][direction][can_turn]
, stores the results of our DFS calls to prevent re-computation. -
Main Loop: We iterate through every cell
(i, j)
of the grid. Ifgrid[i][j] == 1
, it’s a potential starting point. From here, we launch our DFS for all 4 possible initial directions. The initial call will look for a2
as the next target and will allow a turn. -
DFS Logic (Recursive Step):
- Base Case: The recursion stops and returns
0
if the current cell is out of bounds or its value doesn’t match thetarget
. - Recursive Calls: We explore two possibilities from the current cell:
- Continue Straight: Call DFS for the next cell in the same
direction
. - Turn: If a turn is still allowed (
can_turn
is true), also call DFS for the next cell after making a 90-degree clockwise turn ((direction + 1) % 4
). For this new path,can_turn
will be set tofalse
.
- Continue Straight: Call DFS for the next cell in the same
- The result for the current state is
1 + max(path_straight, path_turned)
. This is stored in our memoization table.
- Base Case: The recursion stops and returns
-
Final Result: The answer is the maximum length found across all possible starting points and directions.
Code
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(m*n)
. The state of our DP is determined by(row, col, direction, can_turn)
. With memoization, we compute each state only once. The total number of states ism * n * 4 * 2
. - 🧺 Space complexity:
O(m*n)
. This is dominated by the space required for the memoization table and the recursion stack depth.