Length of longest v shaped diagonal segment

Array Dynamic Programming Memoization Matrix

56.3% acceptance

Feb 25, 2026

374

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn len_of_v_diagonal(grid: Vec<Vec<i32>>) -> i32 {
    let n = grid.len(); let m = grid[0].len();
    // dirs[di] = (dr, dc); clockwise turn: dirs[di] -> dirs[(di+1)%4]
    // (1,1) -> (1,-1) -> (-1,-1) -> (-1,1) -> (1,1)
    let dirs: [(i32,i32);4] = [(1,1),(1,-1),(-1,-1),(-1,1)];
    // seq(k): position k in the required sequence 1, 2, 0, 2, 0, ...
    let seq = |k: usize| -> i32 { if k==0 {1} else if k%2==1 {2} else {0} };

    // dp_nt[r][c][d] = max length of sequence ending at (r,c) going direction d, no turn yet
    let mut dp_nt = vec![vec![[0i32;4];m];n];

    // First pass: compute dp_nt for all directions independently
    for di in 0..4usize {
      let (dr, dc) = dirs[di];
      let row_range: Vec<usize> = if dr > 0 { (0..n).collect() } else { (0..n).rev().collect() };
      let col_range: Vec<usize> = if dc > 0 { (0..m).collect() } else { (0..m).rev().collect() };
      for &r in &row_range {
        for &c in &col_range {
          let val = grid[r][c];
          if val == 1 { dp_nt[r][c][di] = 1; }
          let pr = r as i32 - dr; let pc = c as i32 - dc;
          if pr >= 0 && pr < n as i32 && pc >= 0 && pc < m as i32 {
            let pr = pr as usize; let pc = pc as usize;
            let prev = dp_nt[pr][pc][di];
            if prev > 0 && val == seq(prev as usize) {
              dp_nt[r][c][di] = dp_nt[r][c][di].max(prev + 1);
            }
          }
        }
      }
    }

    // dp_t[r][c][d] = max length of sequence ending at (r,c) going direction d, with one turn
    // The turn happens at the predecessor cell: prev was going turn_from, turned to di, now at (r,c).
    // turn_from is the direction that clockwise-turns into di: turn_from = (di+3)%4
    let mut dp_t = vec![vec![[0i32;4];m];n];

    // Second pass: compute dp_t using already-complete dp_nt
    for di in 0..4usize {
      let (dr, dc) = dirs[di];
      let turn_from = (di + 3) % 4; // direction that clockwise-turns into di
      let row_range: Vec<usize> = if dr > 0 { (0..n).collect() } else { (0..n).rev().collect() };
      let col_range: Vec<usize> = if dc > 0 { (0..m).collect() } else { (0..m).rev().collect() };
      for &r in &row_range {
        for &c in &col_range {
          let val = grid[r][c];
          let pr = r as i32 - dr; let pc = c as i32 - dc;
          if pr >= 0 && pr < n as i32 && pc >= 0 && pc < m as i32 {
            let pr = pr as usize; let pc = pc as usize;
            // Turn happened at prev: prev was end of a no-turn segment in turn_from direction
            let prev_nt_tf = dp_nt[pr][pc][turn_from];
            if prev_nt_tf > 0 && val == seq(prev_nt_tf as usize) {
              dp_t[r][c][di] = dp_t[r][c][di].max(prev_nt_tf + 1);
            }
            // Extend an already-turned segment arriving at prev going di
            let prev_t = dp_t[pr][pc][di];
            if prev_t > 0 && val == seq(prev_t as usize) {
              dp_t[r][c][di] = dp_t[r][c][di].max(prev_t + 1);
            }
          }
        }
      }
    }

    let mut ans = 0i32;
    for r in 0..n {
      for c in 0..m {
        for di in 0..4 {
          ans = ans.max(dp_nt[r][c][di]).max(dp_t[r][c][di]);
        }
      }
    }
    ans
  }
}