LeetCode 3459 - Length of Longest V-Shaped Diagonal Segment
We are given an n x m matrix whose entries are only 0, 1, or 2. A valid V-shaped diagonal segment must satisfy two independent requirements: First, the values along the path must follow a very specific sequence. The first cell must contain 1.
Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Memoization, Matrix
Solution
Problem Understanding
We are given an n x m matrix whose entries are only 0, 1, or 2.
A valid V-shaped diagonal segment must satisfy two independent requirements:
First, the values along the path must follow a very specific sequence. The first cell must contain 1. Every subsequent cell must alternate between 2 and 0 forever:
1, 2, 0, 2, 0, 2, 0, ...
Second, the movement must follow diagonal directions only. There are four possible diagonal directions:
↘ (1, 1)
↙ (1, -1)
↖ (-1, -1)
↗ (-1, 1)
The path starts moving along one diagonal direction. It may continue forever in that same direction, or it may make exactly one clockwise 90-degree turn and then continue in the new diagonal direction while still respecting the required value sequence.
The clockwise turns are:
↘ -> ↙
↙ -> ↖
↖ -> ↗
↗ -> ↘
The task is to return the maximum length of any valid segment.
The constraints are important:
1 <= n, m <= 500
The matrix may contain up to:
500 * 500 = 250,000 cells
This is far too large for any solution that repeatedly explores long paths from every starting position. We need something close to linear in the number of cells.
Several edge cases are worth identifying immediately.
A single cell containing 1 is itself a valid segment of length 1.
A matrix may contain many 1s but no valid continuation with 2, in which case the answer is still 1.
A path may never turn, because the definition says "at most one" clockwise turn.
The turn can occur at any point along the path, including near the end.
The matrix is guaranteed to contain only 0, 1, and 2, which allows us to hardcode the expected next value relationship.
Approaches
Brute Force
A straightforward solution would try every cell containing 1 as a starting point.
For each starting cell, we could try all four diagonal directions. While following the required sequence, we would continue moving forward. At every position we could additionally consider whether to perform the single allowed clockwise turn.
This approach is correct because it explicitly enumerates every valid V-shaped segment.
Unfortunately, it is far too slow. A path can have length O(min(n,m)), and we may explore many such paths from every cell. The resulting complexity becomes roughly quadratic in the number of cells.
Key Observation
The crucial observation is that every state is determined by:
- Current cell
- Current diagonal direction
- Whether the clockwise turn is still available
From a given state, the future is completely fixed by local decisions.
This makes the problem a dynamic programming problem.
Even better, movement along a fixed diagonal direction is acyclic. For example, when moving ↘, every step increases both row and column. We never return to a previously visited state.
Therefore we can compute DP values in reverse topological order for each direction.
We build two DP tables:
straight[d][cell]
The longest valid alternating sequence starting from this cell if we must continue in direction d forever.
turn[d][cell]
The longest valid alternating sequence starting from this cell if we are currently moving in direction d and still have the option to make one clockwise turn.
Once the straight tables are known, the turn tables can be computed efficiently.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(nm · min(n,m)) or worse | O(1) | Repeatedly explores the same paths |
| Optimal DP | O(nm) | O(nm) | Computes every state exactly once |
Algorithm Walkthrough
- Define the four diagonal directions:
0 = ↘ = (1, 1)
1 = ↙ = (1, -1)
2 = ↖ = (-1, -1)
3 = ↗ = (-1, 1)
Direction (d + 1) % 4 is the clockwise 90-degree turn.
2. Define the expected next value.
If the current value is:
1 -> next must be 2
2 -> next must be 0
0 -> next must be 2
This completely determines whether a neighboring cell can be part of the segment.
3. Compute straight[d].
For every direction and every cell, store the longest valid alternating sequence beginning at that cell while continuing forever in direction d.
The recurrence is:
straight[d][cell] =
1 + straight[d][next]
if the next cell exists and contains the required value.
Otherwise:
straight[d][cell] = 1
- Process cells in reverse movement order.
For example, when computing direction ↘, the dependency lies farther down and right, so rows and columns must be processed from large to small.
This guarantees that every dependency has already been computed.
5. Compute turn[d].
This represents the longest valid segment starting at the current cell while moving in direction d and still having the option to make one clockwise turn.
There are two choices.
Continue straight:
1 + turn[d][next_in_same_direction]
Turn now:
1 + straight[cw_direction][next_in_cw_direction]
Take the maximum.
6. Scan every cell containing 1.
A valid segment must start with 1, so only these cells can be answers.
For each of the four starting directions, update the global maximum using turn[d][cell].
Why it works
straight[d][cell] correctly stores the longest valid alternating path when no future turn is allowed because the recurrence exactly matches the only legal continuation in that direction.
turn[d][cell] considers the only two possibilities available from the current state: either continue without using the turn, or use the turn immediately and continue straight afterward. Since every future state is represented by another DP value, the recurrence explores all valid V-shaped segments exactly once.
Because movement along a diagonal direction is acyclic, every DP dependency is computed before it is needed. Therefore all DP values are correct, and the maximum over all starting 1 cells is the desired answer.
Python Solution
from typing import List
from array import array
class Solution:
def lenOfVDiagonal(self, grid: List[List[int]]) -> int:
n, m = len(grid), len(grid[0])
size = n * m
dirs = [
(1, 1), # ↘
(1, -1), # ↙
(-1, -1), # ↖
(-1, 1), # ↗
]
next_value = {1: 2, 2: 0, 0: 2}
def idx(r: int, c: int) -> int:
return r * m + c
# straight[d][i]
straight = [array('I', [1]) * size for _ in range(4)]
orders = [
(range(n - 1, -1, -1), range(m - 1, -1, -1)), # ↘
(range(n - 1, -1, -1), range(m)), # ↙
(range(n), range(m)), # ↖
(range(n), range(m - 1, -1, -1)), # ↗
]
for d, (dr, dc) in enumerate(dirs):
row_order, col_order = orders[d]
dp = straight[d]
for r in row_order:
for c in col_order:
cur = grid[r][c]
want = next_value[cur]
nr = r + dr
nc = c + dc
pos = idx(r, c)
if (
0 <= nr < n and
0 <= nc < m and
grid[nr][nc] == want
):
dp[pos] = 1 + dp[idx(nr, nc)]
# turn[d][i]
turn = [array('I', [1]) * size for _ in range(4)]
for d, (dr, dc) in enumerate(dirs):
cw = (d + 1) % 4
cdr, cdc = dirs[cw]
row_order, col_order = orders[d]
dp = turn[d]
for r in row_order:
for c in col_order:
cur = grid[r][c]
want = next_value[cur]
best = 1
nr = r + dr
nc = c + dc
if (
0 <= nr < n and
0 <= nc < m and
grid[nr][nc] == want
):
best = max(
best,
1 + dp[idx(nr, nc)]
)
tr = r + cdr
tc = c + cdc
if (
0 <= tr < n and
0 <= tc < m and
grid[tr][tc] == want
):
best = max(
best,
1 + straight[cw][idx(tr, tc)]
)
dp[idx(r, c)] = best
answer = 0
for r in range(n):
for c in range(m):
if grid[r][c] != 1:
continue
pos = idx(r, c)
for d in range(4):
answer = max(answer, turn[d][pos])
return answer
The implementation follows the DP construction described above.
The first phase builds four straight tables. Each table corresponds to one diagonal direction and stores the longest alternating sequence obtainable without turning.
The second phase builds four turn tables. Each state considers the two legal actions: continue straight or consume the single clockwise turn.
Finally, only cells containing 1 are considered as valid starting points. The maximum value among all starting directions is returned.
Using array('I') instead of Python integers inside nested lists dramatically reduces memory usage and allows the solution to fit comfortably within the problem constraints.
Go Solution
func lenOfVDiagonal(grid [][]int) int {
n := len(grid)
m := len(grid[0])
size := n * m
dirs := [][2]int{
{1, 1}, // ↘
{1, -1}, // ↙
{-1, -1}, // ↖
{-1, 1}, // ↗
}
nextValue := [3]int{2, 2, 0}
idx := func(r, c int) int {
return r*m + c
}
straight := make([][]int, 4)
for d := 0; d < 4; d++ {
straight[d] = make([]int, size)
for i := range straight[d] {
straight[d][i] = 1
}
}
process := func(d int, fn func(r, c int)) {
switch d {
case 0: // ↘
for r := n - 1; r >= 0; r-- {
for c := m - 1; c >= 0; c-- {
fn(r, c)
}
}
case 1: // ↙
for r := n - 1; r >= 0; r-- {
for c := 0; c < m; c++ {
fn(r, c)
}
}
case 2: // ↖
for r := 0; r < n; r++ {
for c := 0; c < m; c++ {
fn(r, c)
}
}
case 3: // ↗
for r := 0; r < n; r++ {
for c := m - 1; c >= 0; c-- {
fn(r, c)
}
}
}
}
for d := 0; d < 4; d++ {
dr, dc := dirs[d][0], dirs[d][1]
process(d, func(r, c int) {
want := nextValue[grid[r][c]]
nr, nc := r+dr, c+dc
if nr >= 0 && nr < n && nc >= 0 && nc < m &&
grid[nr][nc] == want {
straight[d][idx(r, c)] =
1 + straight[d][idx(nr, nc)]
}
})
}
turn := make([][]int, 4)
for d := 0; d < 4; d++ {
turn[d] = make([]int, size)
for i := range turn[d] {
turn[d][i] = 1
}
}
for d := 0; d < 4; d++ {
dr, dc := dirs[d][0], dirs[d][1]
cw := (d + 1) % 4
cdr, cdc := dirs[cw][0], dirs[cw][1]
process(d, func(r, c int) {
want := nextValue[grid[r][c]]
best := 1
nr, nc := r+dr, c+dc
if nr >= 0 && nr < n && nc >= 0 && nc < m &&
grid[nr][nc] == want {
val := 1 + turn[d][idx(nr, nc)]
if val > best {
best = val
}
}
tr, tc := r+cdr, c+cdc
if tr >= 0 && tr < n && tc >= 0 && tc < m &&
grid[tr][tc] == want {
val := 1 + straight[cw][idx(tr, tc)]
if val > best {
best = val
}
}
turn[d][idx(r, c)] = best
})
}
ans := 0
for r := 0; r < n; r++ {
for c := 0; c < m; c++ {
if grid[r][c] != 1 {
continue
}
pos := idx(r, c)
for d := 0; d < 4; d++ {
if turn[d][pos] > ans {
ans = turn[d][pos]
}
}
}
}
return ans
}
The Go implementation mirrors the Python solution almost exactly. The primary difference is that Go uses slices of int rather than Python's array('I'). Memory usage remains acceptable because each DP table stores only one integer per cell and direction.
Worked Examples
Example 1
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]
]
The optimal path is:
(0,2)=1
(1,3)=2
(2,4)=0
turn
(3,3)=2
(4,2)=0
Length:
5
At (2,4) the DP state evaluates:
| Choice | Length |
|---|---|
| Continue ↘ | 1 |
| Turn to ↙ | 3 |
| Best | 3 |
Working backward causes the starting state at (0,2) to become:
| Cell | DP Value |
|---|---|
| (4,2) | 1 |
| (3,3) | 2 |
| (2,4) | 3 |
| (1,3) | 4 |
| (0,2) | 5 |
Therefore the answer is 5.
Example 2
The optimal segment is:
(2,3)=1
(3,2)=2
turn
(2,1)=0
(1,0)=2
Length:
4
The DP discovers that turning at (3,2) yields a longer continuation than staying in the original direction.
Example 3
The main diagonal already follows:
1 -> 2 -> 0 -> 2 -> 0
Coordinates:
(0,0)
(1,1)
(2,2)
(3,3)
(4,4)
No turn is needed.
The straight DP in direction ↘ becomes:
| Cell | Length |
|---|---|
| (4,4) | 1 |
| (3,3) | 2 |
| (2,2) | 3 |
| (1,1) | 4 |
| (0,0) | 5 |
Answer:
5
Example 4
grid = [[1]]
No move is possible.
The single cell itself is a valid segment.
Answer:
1
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(nm) | Four directions are processed a constant number of times |
| Space | O(nm) | Eight DP tables of size n * m |
The algorithm performs a constant amount of work for each cell in each of the four directions. Therefore the total running time is linear in the number of matrix cells.
The DP tables store one integer per cell per direction. Since the number of directions is constant, the overall memory requirement remains O(nm).
Test Cases
s = Solution()
assert s.lenOfVDiagonal([[1]]) == 1 # single valid starting cell
assert s.lenOfVDiagonal([
[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]
]) == 5 # example 1
assert s.lenOfVDiagonal([
[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]
]) == 4 # example 2
assert s.lenOfVDiagonal([
[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]
]) == 5 # example 3
assert s.lenOfVDiagonal([
[0]
]) == 0 # no starting 1 exists
assert s.lenOfVDiagonal([
[1,2],
[2,0]
]) == 2 # simple diagonal extension
assert s.lenOfVDiagonal([
[1,2,0],
[2,0,2],
[0,2,0]
]) == 3 # straight path without turn
assert s.lenOfVDiagonal([
[1,2,2],
[2,0,0],
[2,2,0]
]) >= 1 # multiple choices
assert s.lenOfVDiagonal([
[1,1],
[1,1]
]) == 1 # all starts, no continuation
assert s.lenOfVDiagonal([
[2,2,2],
[2,2,2],
[2,2,2]
]) == 0 # no valid start
| Test | Why |
|---|---|
[[1]] |
Smallest valid input |
| Example 1 | Turn produces optimum |
| Example 2 | Different turn location |
| Example 3 | No turn required |
[[0]] |
No starting cell exists |
| Small 2x2 diagonal | Basic continuation |
| Straight alternating diagonal | Verifies no-turn case |
| Multiple choices | Ensures max path chosen |
| All ones | Cannot continue sequence |
| No ones | Answer must be 0 |
Edge Cases
Single Cell Matrix
A matrix containing only [[1]] is a valid input. There are no neighboring cells, so any implementation that assumes at least one move exists would fail. The DP initializes every state to length 1, which correctly handles this situation.
No Starting Cell
The problem requires every valid segment to begin with a 1. If the matrix contains only 0 and 2, then no valid segment exists and the answer must be 0. The final scan only considers cells containing 1, so the result remains zero.
Valid Path Without a Turn
The definition allows "at most one" turn, not "exactly one" turn. A common bug is forcing a turn somewhere along the path. The turn DP always includes the option to continue straight, so paths that never turn are naturally handled.
Turn Near the Boundary
The optimal path may turn immediately before reaching the edge of the matrix. Boundary checks are performed before every transition, both for straight movement and for turning, ensuring that no out-of-bounds access occurs and that edge turns are evaluated correctly.
Multiple Starting Directions
A cell containing 1 may have several possible diagonal continuations. The algorithm evaluates all four starting directions independently and takes the maximum, guaranteeing that no valid V-shaped segment is overlooked.