Length of Longest V-Shaped Diagonal Segment solution and explanation
Google
9 more videos on this problem
Length of Longest V-Shaped Diagonal Segment | Made Easy | Leetcode 3459 | codestorywithMIKcodestorywithMIK · 43:36 · 7K views
3459. Length of Longest V-Shaped Diagonal Segment | Simple Explanation DP | Leetcode Daily ChallengeEye on AI and DSA · 28:25 · 2K views
3459. Length of Longest V-Shaped Diagonal Segment | Leetcode Daily - PythonLeetcode Daily · 6:35 · 1K views
3459. Length of Longest V-Shaped Diagonal Segment (Leetcode Hard)Programming Live with Larry · 30:53 · 701 views
Daily Leetcode #1975: Aug 27, 2025 - 3459. Length of Longest V-Shaped Diagonal SegmentProgramming Live with Larry · 17:06 · 588 views
Length of Longest V Shaped Diagonal Segment | LeetCode 3459 - Pythonimpoldev · 14:16 · 502 views
3459. Length of Longest V-Shaped Diagonal Segment | Leetcode | Weekly COntest 437Amit Choraria · 18:01 · 412 views
Length of Longest V-Shaped Diagonal Segment | Detailed Thought Process | Leetcode 3459 | Hard MarkedCodeWith_Kedar · 15:38 · 393 views
Leetcode 3459. Length of Longest V-Shaped Diagonal Segment | Best ApproachExpertFunda · 44:21 · 373 views
Leetcode 3459. Length of Longest V-Shaped Diagonal Segment | DFS + Memoization | Python SolutionStatLearn Tech · 22:33 · 328 views
The 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 the sequence in the same diagonal direction.
- Makes at 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:
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 either0,1or2.
Approach overview
Problem Overview: You are given a matrix and need to find the maximum length of a segment that forms a V shape along diagonals. A valid segment starts on a diagonal direction, continues for some length, then changes to another diagonal direction exactly once to form the V. The task is to scan the grid and compute the longest such path.
Approach 1: Brute Force Diagonal Exploration (O(m*n*L), O(1) space)
Start from every cell and attempt to extend a segment along all four diagonal directions. At each step, continue moving diagonally until you decide to switch to the other diagonal direction to form the V. Track the length while validating bounds and constraints. This approach repeatedly recomputes overlapping paths because the same diagonal subpaths are explored from multiple starting points. For larger grids this quickly becomes expensive since every extension may scan up to L cells along diagonals.
Approach 2: Memoized Search with Dynamic Programming (O(m*n), O(m*n) space)
The optimal approach treats the grid as a state graph and uses DFS with memoization. Each state is defined by (row, col, direction, turned) where direction is one of the four diagonals and turned indicates whether the V turn has already happened. From each state you attempt two transitions: continue in the same diagonal or switch direction if the turn has not yet been used. Store results in a memo table so every state is computed once. This removes repeated exploration and reduces the runtime to linear in the number of cells multiplied by constant directional states.
The memoized DFS behaves like classic grid dynamic programming. Each diagonal extension builds on previously solved states. Because transitions only move to neighboring cells, the recursion depth is limited by grid size and the DP cache ensures optimal substructure reuse.
This technique is similar to path problems solved using memoization on top of DFS over a matrix. The key insight is representing the "turn" as part of the state so the algorithm knows whether the V pivot has already occurred.
Recommended for interviews: Interviewers expect the memoized search solution. A brute-force exploration shows you understand the geometric constraint of the V shape, but the optimized DFS + memoization demonstrates strong dynamic programming skills and awareness of overlapping subproblems. The final solution runs in O(m*n) time with O(m*n) caching, which scales comfortably even for large matrices.
Solution
We design a function dfs(i, j, k, cnt) that returns the length of the longest V-shaped diagonal segment, where (i, j) is the previous position, k is the current direction, and cnt is the remaining number of allowed turns.
The logic of the dfs function is as follows:
First, based on the previous position and the current direction, we calculate the current position (x, y) and determine the target value target. If x or y is out of bounds, or if grid[x][y] neq target, we return 0.
Otherwise, we have two choices:
Continue moving in the current direction.
Make a 90-degree clockwise turn at the current position and then continue moving.
To implement the turn, if the current direction is k, the new direction after a 90-degree clockwise turn is (k + 1) bmod 4. We take the maximum result from these two choices as the result for the current state.
In the main function, we iterate over the entire matrix. For each position with value 1, we try searching in all four directions and update the answer.
After the traversal, we return the answer.
To avoid repeated calculations, we use memoization to cache intermediate results.
The time complexity is O(m times n), and the space complexity is O(m times n), where m and n are the number of rows and columns in the matrix, respectively.
class Solution:
def lenOfVDiagonal(self, grid: List[List[int]]) -> int:
@cache
def dfs(i: int, j: int, k: int, cnt: int) -> int:
x, y = i + dirs[k], j + dirs[k + 1]
target = 2 if grid[i][j] == 1 else (2 - grid[i][j])
if not 0 <= x < m or not 0 <= y < n or grid[x][y] != target:
return 0
res = dfs(x, y, k, cnt)
if cnt > 0:
res = max(res, dfs(x, y, (k + 1) % 4, 0))
return 1 + res
m, n = len(grid), len(grid[0])
dirs = (1, 1, -1, -1, 1)
ans = 0
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x == 1:
for k in range(4):
ans = max(ans, dfs(i, j, k, 1) + 1)
return ansclass Solution {
private int m, n;
private final int[] dirs = {1, 1, -1, -1, 1};
private Integer[][][][] f;
public int lenOfVDiagonal(int[][] grid) {
m = grid.length;
n = grid[0].length;
f = new Integer[m][n][4][2];
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
for (int k = 0; k < 4; k++) {
ans = Math.max(ans, dfs(grid, i, j, k, 1) + 1);
}
}
}
}
return ans;
}
private int dfs(int[][] grid, int i, int j, int k, int cnt) {
if (f[i][j][k][cnt] != null) {
return f[i][j][k][cnt];
}
int x = i + dirs[k];
int y = j + dirs[k + 1];
int target = grid[i][j] == 1 ? 2 : (2 - grid[i][j]);
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != target) {
f[i][j][k][cnt] = 0;
return 0;
}
int res = dfs(grid, x, y, k, cnt);
if (cnt > 0) {
res = Math.max(res, dfs(grid, x, y, (k + 1) % 4, 0));
}
f[i][j][k][cnt] = 1 + res;
return 1 + res;
}
}class Solution {
public:
static constexpr int MAXN = 501;
int f[MAXN][MAXN][4][2];
int lenOfVDiagonal(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int dirs[5] = {1, 1, -1, -1, 1};
memset(f, -1, sizeof(f));
auto dfs = [&](this auto&& dfs, int i, int j, int k, int cnt) -> int {
if (f[i][j][k][cnt] != -1) {
return f[i][j][k][cnt];
}
int x = i + dirs[k];
int y = j + dirs[k + 1];
int target = grid[i][j] == 1 ? 2 : (2 - grid[i][j]);
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != target) {
f[i][j][k][cnt] = 0;
return 0;
}
int res = dfs(x, y, k, cnt);
if (cnt > 0) {
res = max(res, dfs(x, y, (k + 1) % 4, 0));
}
f[i][j][k][cnt] = 1 + res;
return 1 + res;
};
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
for (int k = 0; k < 4; ++k) {
ans = max(ans, dfs(i, j, k, 1) + 1);
}
}
}
}
return ans;
}
};func lenOfVDiagonal(grid [][]int) int {
m, n := len(grid), len(grid[0])
dirs := []int{1, 1, -1, -1, 1}
f := make([][][4][2]int, m)
for i := range f {
f[i] = make([][4][2]int, n)
}
var dfs func(i, j, k, cnt int) int
dfs = func(i, j, k, cnt int) int {
if f[i][j][k][cnt] != 0 {
return f[i][j][k][cnt]
}
x := i + dirs[k]
y := j + dirs[k+1]
var target int
if grid[i][j] == 1 {
target = 2
} else {
target = 2 - grid[i][j]
}
if x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != target {
f[i][j][k][cnt] = 0
return 0
}
res := dfs(x, y, k, cnt)
if cnt > 0 {
res = max(res, dfs(x, y, (k+1)%4, 0))
}
f[i][j][k][cnt] = res + 1
return res + 1
}
ans := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
for k := 0; k < 4; k++ {
ans = max(ans, dfs(i, j, k, 1)+1)
}
}
}
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Diagonal Exploration | O(m*n*L) | O(1) | Useful for understanding the V-shape constraint and validating logic on small grids |
| DFS with Memoization (Dynamic Programming) | O(m*n) | O(m*n) | Best general solution. Avoids recomputation of diagonal paths and scales well for large matrices |
Frequently asked questions
Is Length of Longest V-Shaped Diagonal Segment easy or hard?
Length of Longest V-Shaped Diagonal Segment is classified as Hard because it combines matrix traversal, directional constraints, and dynamic programming with memoization. Recognizing the correct state representation is the main challenge.
Length of Longest V-Shaped Diagonal Segment Python/Java solution
Implement a DFS that explores diagonal moves and store intermediate results in a memo table keyed by (row, column, direction, turned). The same logic works in Python, Java, C++, and Go by using recursion plus a hash map or multidimensional DP array.
How to solve Length of Longest V-Shaped Diagonal Segment in O(n)?
Treat the grid as a state graph and run DFS with memoization. Define states as (row, col, direction, turned). Continue along the same diagonal or switch direction once to form the V shape. Because each state is computed once, the total complexity becomes O(m*n).
What is the best approach for Length of Longest V-Shaped Diagonal Segment?
The most efficient approach uses DFS with memoization. Each state represents a cell, the current diagonal direction, and whether the V turn has already been used. Caching results for these states avoids recomputation and reduces the total complexity to O(m*n) with O(m*n) space.
Is Length of Longest V-Shaped Diagonal Segment asked at Google/Amazon/Meta?
Matrix path problems with direction constraints and dynamic programming frequently appear in interviews at companies like Amazon, Google, and Meta. Variations often involve grid traversal with restricted moves and memoization to avoid repeated computation.
What data structure is used in Length of Longest V-Shaped Diagonal Segment?
The solution primarily uses a matrix combined with recursion and a memoization table (DP cache). The cache stores results for each cell, direction, and turn state to avoid recomputing diagonal path lengths.
What is the time complexity of Length of Longest V-Shaped Diagonal Segment?
The optimized memoized search runs in O(m*n) time because each grid cell is processed with a constant number of directional states. A naive brute-force approach can degrade to O(m*n*L) where L is the maximum diagonal path length.