Length of Longest V-Shaped Diagonal Segment

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 thesequence in the same diagonal direction.
  • Makesat 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.

Examples

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

Solution

Intuition

The core idea is to find the longest valid path in the grid, treating it like a graph. A V-shaped segment is a special path that must start with a 1, follow a 2, 0, 2, 0... pattern, and is allowed to make at most one 90-degree clockwise turn.

Since the longest path from any given cell depends on the longest paths from its potential next cells, this problem is a perfect fit for Dynamic Programming. We can explore all possible paths starting from every 1 in the grid using a Depth-First Search (DFS). To avoid re-calculating results for the same state (i.e., the same cell, direction, and turn status), we use memoization.

Approach

1. State Definition: We create a recursive DFS function, dfs(row, col, direction, can_turn, target), that calculates the length of a valid segment starting from the cell (row, col).

   • (row, col): The coordinates of the current cell.
   • direction: The current diagonal direction (0-3).
   • can_turn: A boolean indicating if we are still allowed to make a turn.
   • target: The value we expect the current cell (row, col) to have.

2. Memoization: A 4D array, memo[row][col][direction][can_turn], stores the results of our DFS calls to prevent re-computation.

3. Main Loop: We iterate through every cell (i, j) of the grid. If grid[i][j] == 1, it's a potential starting point. From here, we launch our DFS for all 4 possible initial directions. The initial call will look for a 2 as the next target and will allow a turn.

4. DFS Logic (Recursive Step):

   • Base Case: The recursion stops and returns 0 if the current cell is out of bounds or its value doesn't match the target.
   • Recursive Calls: We explore two possibilities from the current cell:
     1. Continue Straight: Call DFS for the next cell in the same direction.
     2. Turn: If a turn is still allowed (can_turn is true), also call DFS for the next cell after making a 90-degree clockwise turn ((direction + 1) % 4). For this new path, can_turn will be set to false.
   • The result for the current state is 1 + max(path_straight, path_turned). This is stored in our memoization table.

5. Final Result: The answer is the maximum length found across all possible starting points and directions.

Code

C++

#include <vector>
#include <map>
#include <tuple>
#include <algorithm>

using namespace std;

class Solution {
public:
    int m, n;
    vector<vector<int>> grid;
    vector<pair<int, int>> dirs = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
    map<tuple<int, int, int, bool>, int> memo;

    int dfs(int cx, int cy, int direction, bool can_turn, int target) {
        int nx = cx + dirs[direction].first;
        int ny = cy + dirs[direction].second;

        if (nx < 0 || ny < 0 || nx >= m || ny >= n || grid[nx][ny] != target) {
            return 0;
        }

        auto key = make_tuple(nx, ny, direction, can_turn);
        if (memo.count(key)) {
            return memo[key];
        }

        int max_step = dfs(nx, ny, direction, can_turn, 2 - target);
        if (can_turn) {
            max_step = max(max_step, dfs(nx, ny, (direction + 1) % 4, false, 2 - target));
        }
        
        return memo[key] = max_step + 1;
    }

    int lenOfVDiagonal(vector<vector<int>>& grid) {
        this->grid = grid;
        this->m = grid.size();
        this->n = grid[0].size();
        
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    for (int direction = 0; direction < 4; direction++) {
                        res = max(res, dfs(i, j, direction, true, 2) + 1);
                    }
                }
            }
        }
        return res;
    }
};

Go

func lenOfVDiagonal(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    dirs := [][2]int{{1, 1}, {1, -1}, {-1, -1}, {-1, 1}}
    memo := make(map[[4]int]int)

    var dfs func(cx, cy, direction int, can_turn bool, target int) int
    dfs = func(cx, cy, direction int, can_turn bool, target int) int {
        nx := cx + dirs[direction][0]
        ny := cy + dirs[direction][1]

        if nx < 0 || ny < 0 || nx >= m || ny >= n || grid[nx][ny] != target {
            return 0
        }

        turnInt := 0
        if can_turn {
            turnInt = 1
        }
        key := [4]int{nx, ny, direction, turnInt}
        if val, ok := memo[key]; ok {
            return val
        }

        maxStep := dfs(nx, ny, direction, can_turn, 2-target)
        if can_turn {
            maxStep = max(maxStep, dfs(nx, ny, (direction+1)%4, false, 2-target))
        }

        memo[key] = maxStep + 1
        return maxStep + 1
    }

    res := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                for direction := 0; direction < 4; direction++ {
                    res = max(res, dfs(i, j, direction, true, 2)+1)
                }
            }
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Java

class Solution {

    private static final int[][] DIRS = {
        { 1, 1 },
        { 1, -1 },
        { -1, -1 },
        { -1, 1 },
    };
    private int[][][][] memo;
    private int[][] grid;
    private int m, n;

    public int lenOfVDiagonal(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        this.memo = new int[m][n][4][2];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 4; k++) {
                    Arrays.fill(memo[i][j][k], -1);
                }
            }
        }

        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    for (int direction = 0; direction < 4; direction++) {
                        res = Math.max(res, dfs(i, j, direction, true, 2) + 1);
                    }
                }
            }
        }
        return res;
    }

    private int dfs(int cx, int cy, int direction, boolean turn, int target) {
        int nx = cx + DIRS[direction][0];
        int ny = cy + DIRS[direction][1];
        /* If it goes beyond the boundary or the next node's value is not the target value, then return */
        if (nx < 0 || ny < 0 || nx >= m || ny >= n || grid[nx][ny] != target) {
            return 0;
        }

        int turnInt = turn ? 1 : 0;
        if (memo[nx][ny][direction][turnInt] != -1) {
            return memo[nx][ny][direction][turnInt];
        }

        /* Continue walking in the original direction. */
        int maxStep = dfs(nx, ny, direction, turn, 2 - target);
        if (turn) {
            /* Clockwise rotate 90 degrees turn */
            maxStep = Math.max(
                maxStep,
                dfs(nx, ny, (direction + 1) % 4, false, 2 - target)
            );
        }
        memo[nx][ny][direction][turnInt] = maxStep + 1;
        return maxStep + 1;
    }
}

Kotlin

class Solution {
    fun lenOfVDiagonal(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        val dirs = arrayOf(intArrayOf(1, 1), intArrayOf(1, -1), intArrayOf(-1, -1), intArrayOf(-1, 1))
        val memo = mutableMapOf<List<Int>, Int>()

        fun dfs(cx: Int, cy: Int, direction: Int, canTurn: Boolean, target: Int): Int {
            val nx = cx + dirs[direction][0]
            val ny = cy + dirs[direction][1]

            if (nx !in 0 until m || ny !in 0 until n || grid[nx][ny] != target) {
                return 0
            }

            val turnInt = if (canTurn) 1 else 0
            val key = listOf(nx, ny, direction, turnInt)
            memo[key]?.let { return it }

            var maxStep = dfs(nx, ny, direction, canTurn, 2 - target)
            if (canTurn) {
                maxStep = maxOf(maxStep, dfs(nx, ny, (direction + 1) % 4, false, 2 - target))
            }
            
            val result = maxStep + 1
            memo[key] = result
            return result
        }

        var res = 0
        for (i in 0 until m) {
            for (j in 0 until n) {
                if (grid[i][j] == 1) {
                    for (direction in 0..3) {
                        res = maxOf(res, dfs(i, j, direction, true, 2) + 1)
                    }
                }
            }
        }
        return res
    }
}

Python

from functools import lru_cache

class Solution:
    def lenOfVDiagonal(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dirs = [(1, 1), (1, -1), (-1, -1), (-1, 1)]

        @lru_cache(None)
        def dfs(cx, cy, direction, can_turn, target):
            nx, ny = cx + dirs[direction][0], cy + dirs[direction][1]

            if not (0 <= nx < m and 0 <= ny < n and grid[nx][ny] == target):
                return 0

            # Continue in the same direction
            max_step = dfs(nx, ny, direction, can_turn, 2 - target)
            
            # Try turning if allowed
            if can_turn:
                turned_direction = (direction + 1) % 4
                max_step = max(max_step, dfs(nx, ny, turned_direction, False, 2 - target))
            
            return max_step + 1

        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    for direction in range(4):
                        res = max(res, dfs(i, j, direction, True, 2) + 1)
        return res

Rust

use std::collections::HashMap;

impl Solution {
    pub fn len_of_v_diagonal(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let dirs = [(1, 1), (1, -1), (-1, -1), (-1, 1)];
        let mut memo = HashMap::new();

        fn dfs(
            cx: i32,
            cy: i32,
            direction: usize,
            can_turn: bool,
            target: i32,
            grid: &Vec<Vec<i32>>,
            memo: &mut HashMap<(i32, i32, usize, bool), i32>,
            m: usize,
            n: usize,
            dirs: &[(i32, i32); 4],
        ) -> i32 {
            let nx = cx + dirs[direction].0;
            let ny = cy + dirs[direction].1;

            if nx < 0 || ny < 0 || nx as usize >= m || ny as usize >= n || grid[nx as usize][ny as usize] != target {
                return 0;
            }

            let key = (nx, ny, direction, can_turn);
            if let Some(&val) = memo.get(&key) {
                return val;
            }

            let mut max_step = dfs(nx, ny, direction, can_turn, 2 - target, grid, memo, m, n, dirs);
            if can_turn {
                max_step = max_step.max(dfs(nx, ny, (direction + 1) % 4, false, 2 - target, grid, memo, m, n, dirs));
            }
            
            let result = max_step + 1;
            memo.insert(key, result);
            result
        }

        let mut res = 0;
        for i in 0..m {
            for j in 0..n {
                if grid[i][j] == 1 {
                    for direction in 0..4 {
                        res = res.max(dfs(i as i32, j as i32, direction, true, 2, &grid, &mut memo, m, n, &dirs) + 1);
                    }
                }
            }
        }
        res
    }
}

TypeScript

class Solution {
    lenOfVDiagonal(grid: number[][]): number {
        const m = grid.length;
        const n = grid[0].length;
        const dirs = [[1, 1], [1, -1], [-1, -1], [-1, 1]];
        const memo = new Map<string, number>();

        function dfs(cx: number, cy: number, direction: number, canTurn: boolean, target: number): number {
            const nx = cx + dirs[direction][0];
            const ny = cy + dirs[direction][1];

            if (nx < 0 || ny < 0 || nx >= m || ny >= n || grid[nx][ny] !== target) {
                return 0;
            }

            const turnInt = canTurn ? 1 : 0;
            const key = `${nx},${ny},${direction},${turnInt}`;
            if (memo.has(key)) {
                return memo.get(key)!;
            }

            let maxStep = dfs(nx, ny, direction, canTurn, 2 - target);
            if (canTurn) {
                maxStep = Math.max(maxStep, dfs(nx, ny, (direction + 1) % 4, false, 2 - target));
            }
            
            const result = maxStep + 1;
            memo.set(key, result);
            return result;
        }

        let res = 0;
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (grid[i][j] === 1) {
                    for (let direction = 0; direction < 4; direction++) {
                        res = Math.max(res, dfs(i, j, direction, true, 2) + 1);
                    }
                }
            }
        }
        return res;
    }
}

Complexity

• ⏰ Time complexity: O(m*n). The state of our DP is determined by (row, col, direction, can_turn). With memoization, we compute each state only once. The total number of states is m * n * 4 * 2.
• 🧺 Space complexity: O(m*n). This is dominated by the space required for the memoization table and the recursion stack depth.