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

lenOfVDiagonal.js

/**
 * @param {number[][]} grid
 * @return {number}
 */
var lenOfVDiagonal = function(grid) {
    const n = grid.length;
    const m = grid[0].length;

    // Diagonal directions: ↘, ↙, ↖, ↗
    const DIRS = [
        [1, 1],   // down-right
        [1, -1],  // down-left
        [-1, -1], // up-left
        [-1, 1]   // up-right
    ];

    // Memoization: memo[i][j][mask] stores longest segment from (i,j) with direction+turn state
    const memo = Array.from({ length: n }, () =>
        Array.from({ length: m }, () => Array(8).fill(0))
    );

    let maxLength = 0;

    // Traverse each cell to find starting points (must be 1)
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (grid[i][j] !== 1) continue;

            // Precompute max steps possible in each direction to prune early
            const maxSteps = [n - i, j + 1, i + 1, m - j];

            for (let dir = 0; dir < 4; dir++) {
                if (maxSteps[dir] > maxLength) {
                    // Start DFS from (i,j) in direction `dir`, with turn allowed, expecting `2` next
                    const length = dfs(i, j, dir, 1, 2);
                    maxLength = Math.max(maxLength, length + 1); // +1 for starting `1`
                }
            }
        }
    }

    return maxLength;

    function dfs(i, j, dir, canTurn, target) {
        // Move to next cell in current direction
        i += DIRS[dir][0];
        j += DIRS[dir][1];

        // Out of bounds or value mismatch
        if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] !== target) return 0;

        // Encode direction and turn state into a bitmask
        const mask = (dir << 1) | canTurn;
        if (memo[i][j][mask] > 0) return memo[i][j][mask];

        // Continue in same direction, flipping target (2 ↔ 0)
        let res = dfs(i, j, dir, canTurn, 2 - target);

        // Try one clockwise turn if allowed
        if (canTurn === 1) {
            const nextDir = (dir + 1) % 4;

            // Precompute max steps to prune unnecessary turns
            const maxSteps = [n - i - 1, j, i, m - j - 1];
            if (maxSteps[nextDir] > res) {
                res = Math.max(res, dfs(i, j, nextDir, 0, 2 - target));
            }
        }

        // Memoize and return result (+1 for current cell)
        return (memo[i][j][mask] = res + 1);
    }
};