Length of Longest V-Shaped Diagonal Segment

Hard
1675.

Length of Longest V-Shaped Diagonal Segment

Length of Longest V-Shaped Diagonal Segment is a hard coding problem on arrays, dynamic programming and matrix, asked in Google interviews.

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.length
  • m == grid[i].length
  • 1 <= n, m <= 500
  • grid[i][j] is 0, 1 or 2
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var lenOfVDiagonal = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • m == grid[i].length
  • 1 <= n, m <= 500
  • grid[i][j] is 0, 1 or 2

Hints for Length of Longest V-Shaped Diagonal Segment

  1. 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.

  2. Hint 2

    Define f(i, j, d, canTurn) = the longest continuation that starts at cell (i, j) (already part of the segment) moving in direction d. It either steps forward in d or, if canTurn, steps in the clockwise-next direction and gives up the turn.

  3. Hint 3

    Memoise f over n · m · 4 · 2 states, and take max 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

  1. Order the directions clockwise: (1,1), (1,-1), (-1,-1), (-1,1); a turn goes from d to (d + 1) mod 4.
  2. Let f(i, j, d, t) be the length of the longest continuation from (i, j) inclusive. The next value needed is 0 if grid[i][j] == 2, else 2.
  3. 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 neighbour f = 1.
  4. Answer max f(i, j, d, 1) over cells with grid[i][j] == 1 and all d, 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 ans

Java

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