Length of Longest V-Shaped Diagonal Segment — Solution
Length of Longest V-Shaped Diagonal Segment solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Length of Longest V-Shaped Diagonal Segment is a hard coding problem on arrays, dynamic programming and matrix, asked in Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Matrix, Memoization
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an n x m matrix grid whose cells hold 0, 1 or 2.
A V-shaped diagonal segment is a path of cells that:
- starts at a cell holding
1; - continues with the repeating sequence
2, 0, 2, 0, ...; - moves along one of the four diagonal directions (down-right, down-left, up-left, up-right) — every step goes one cell in the current direction;
- may make at most one clockwise 90° turn to the next diagonal direction (down-right → down-left → up-left → up-right → down-right), and then keeps going in the new direction while still following the sequence.
Return the length (number of cells) of the longest V-shaped diagonal segment, or 0 if there is none.
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: (0,2) → (1,3) → (2,4) going down-right, a clockwise turn, then (3,3) → (4,2) going down-left: 1, 2, 0, 2, 0.
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: (2,3) → (3,2), turn, → (2,1) → (1,0): 1, 2, 0, 2.
Example 3
Input: grid = [[1]]
Output: 1
Explanation: A lone 1 is a segment of length 1.
Constraints
n == grid.lengthm == grid[i].length1 <= n, m <= 500grid[i][j] is 0, 1 or 2
Hints for Length of Longest V-Shaped Diagonal Segment
Hint 1
A segment is determined by its start, its first direction, and where (if anywhere) it turns. The value expected at the next cell depends only on the current cell's value: after 1 or 0 comes 2, after 2 comes 0.
Hint 2
Define
f(i, j, d, canTurn)= the longest continuation that starts at cell(i, j)(already part of the segment) moving in directiond. It either steps forward indor, ifcanTurn, steps in the clockwise-next direction and gives up the turn.Hint 3
Memoise
fovern · m · 4 · 2states, and takemax f(i, j, d, true)over every cell holding 1 and every direction.
How to solve Length of Longest V-Shaped Diagonal Segment
The future of a segment depends only on where it is, which way it is heading, what value comes next (fixed by the current cell) and whether the turn is still available. That is 8 states per cell, so memoised search over them visits each state once.
Approach
- Order the directions clockwise:
(1,1), (1,-1), (-1,-1), (-1,1); a turn goes fromdto(d + 1) mod 4. - Let
f(i, j, d, t)be the length of the longest continuation from(i, j)inclusive. The next value needed is 0 ifgrid[i][j] == 2, else 2. f = 1 + max(f(next in d), and if t: f(next in d + 1 with t = 0)), counting only neighbours inside the grid that hold the needed value; with no valid neighbourf = 1.- Answer
max f(i, j, d, 1)over cells withgrid[i][j] == 1and alld, or 0 when there is no 1.
Why it works
Every V-shaped segment is a straight run, an optional clockwise turn at some cell, and a second straight run — exactly the choices f branches on. Because the needed value at a cell is determined by that cell's own value (a 1 only appears at the start), the state (cell, direction, turn left) captures everything that affects the rest of the segment.
Complexity
- Time —
O(n · m) - Space —
O(n · m)
Pitfalls
- Only clockwise turns count, and only one: track the turn in the state.
- The sequence after the start is 2, 0, 2, 0 — a 1 never appears again, so the needed value never depends on the position along the segment.
- Deep recursion on a 500 × 500 grid: raise the recursion limit or iterate.
Reference solution
Python
from typing import List
import sys
def lenOfVDiagonal(grid: List[List[int]]) -> int:
sys.setrecursionlimit(10000)
n, m = len(grid), len(grid[0])
DR = (1, 1, -1, -1)
DC = (1, -1, -1, 1)
memo = {}
def f(i, j, d, t):
key = ((i * m + j) * 4 + d) * 2 + t
if key in memo:
return memo[key]
need = 0 if grid[i][j] == 2 else 2
best = 1
r, c = i + DR[d], j + DC[d]
if 0 <= r < n and 0 <= c < m and grid[r][c] == need:
best = 1 + f(r, c, d, t)
if t:
d2 = (d + 1) % 4
r, c = i + DR[d2], j + DC[d2]
if 0 <= r < n and 0 <= c < m and grid[r][c] == need:
best = max(best, 1 + f(r, c, d2, 0))
memo[key] = best
return best
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, f(i, j, d, 1))
return ansJava
static final int[] DR = {1, 1, -1, -1};
static final int[] DC = {1, -1, -1, 1};
static int[] memo;
static int[][] g;
static int rows, cols;
static int walk(int i, int j, int d, int t) {
int key = ((i * cols + j) * 4 + d) * 2 + t;
if (memo[key] != 0) return memo[key];
int need = g[i][j] == 2 ? 0 : 2;
int best = 1;
int r = i + DR[d], c = j + DC[d];
if (r >= 0 && r < rows && c >= 0 && c < cols && g[r][c] == need) best = 1 + walk(r, c, d, t);
if (t == 1) {
int d2 = (d + 1) % 4;
r = i + DR[d2];
c = j + DC[d2];
if (r >= 0 && r < rows && c >= 0 && c < cols && g[r][c] == need) best = Math.max(best, 1 + walk(r, c, d2, 0));
}
memo[key] = best;
return best;
}
public static int lenOfVDiagonal(int[][] grid) {
g = grid;
rows = grid.length;
cols = grid[0].length;
memo = new int[rows * cols * 8];
int ans = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] != 1) continue;
for (int d = 0; d < 4; d++) ans = Math.max(ans, walk(i, j, d, 1));
}
}
return ans;
}C++
int lenOfVDiagonal(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
const int DR[4] = {1, 1, -1, -1}, DC[4] = {1, -1, -1, 1};
vector<int> memo(n * m * 8, 0);
function<int(int, int, int, int)> f = [&](int i, int j, int d, int t) -> int {
int key = ((i * m + j) * 4 + d) * 2 + t;
if (memo[key]) return memo[key];
int need = grid[i][j] == 2 ? 0 : 2;
int best = 1;
int r = i + DR[d], c = j + DC[d];
if (r >= 0 && r < n && c >= 0 && c < m && grid[r][c] == need) best = 1 + f(r, c, d, t);
if (t) {
int d2 = (d + 1) % 4;
r = i + DR[d2];
c = j + DC[d2];
if (r >= 0 && r < n && c >= 0 && c < m && grid[r][c] == need) best = max(best, 1 + f(r, c, d2, 0));
}
return memo[key] = best;
};
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, f(i, j, d, 1));
return ans;
}JavaScript
var lenOfVDiagonal = function(grid) {
var n = grid.length, m = grid[0].length;
var DR = [1, 1, -1, -1], DC = [1, -1, -1, 1];
var memo = new Array(n * m * 8).fill(0);
var f = function(i, j, d, t) {
var key = ((i * m + j) * 4 + d) * 2 + t;
if (memo[key]) return memo[key];
var need = grid[i][j] === 2 ? 0 : 2;
var best = 1;
var r = i + DR[d], c = j + DC[d];
if (r >= 0 && r < n && c >= 0 && c < m && grid[r][c] === need) best = 1 + f(r, c, d, t);
if (t) {
var d2 = (d + 1) % 4;
r = i + DR[d2]; c = j + DC[d2];
if (r >= 0 && r < n && c >= 0 && c < m && grid[r][c] === need) best = Math.max(best, 1 + f(r, c, d2, 0));
}
memo[key] = best;
return best;
};
var ans = 0;
for (var i = 0; i < n; i++) {
for (var j = 0; j < m; j++) {
if (grid[i][j] !== 1) continue;
for (var d = 0; d < 4; d++) ans = Math.max(ans, f(i, j, d, 1));
}
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming