DEV Community

Cover image for 🔥 LeetCode 3459: Length of Longest V-Shaped Diagonal Segment (C++, Python, Java, JavaScript, Go & C#)
Om Shree
Om Shree

Posted on

🔥 LeetCode 3459: Length of Longest V-Shaped Diagonal Segment (C++, Python, Java, JavaScript, Go & C#)

#programming #beginners #tutorial #discuss

We are given a 2D matrix grid of size n × m where each element is 0, 1, or 2.

We must find the length of the longest V-shaped diagonal segment.

A valid V-shaped diagonal segment must follow these rules:

  1. It starts with 1.
  2. It continues with a repeating pattern: 
   2 → 0 → 2 → 0 → ...
Enter fullscreen mode Exit fullscreen mode
  1. The path must move along diagonals (↘, ↙, ↗, ↖).
  2. At most one clockwise 90° turn is allowed. After turning, it must continue straight.

🧩 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
Enter fullscreen mode Exit fullscreen mode

Path:

(0,2) → (1,3) → (2,4) ↘  
turn ↘ → ↙  
(3,3) → (4,2)
Enter fullscreen mode Exit fullscreen mode

Example 2 

Input:
grid = [[1]]
Output: 1
Enter fullscreen mode Exit fullscreen mode

Path is just the starting 1.

🎯 Intuition

This problem is essentially a grid traversal with constraints.

  • Any valid segment must start at a 1.
  • From there, we move diagonally while checking the repeating pattern.
  • We are allowed to make at most one clockwise turn.

  • The traversal stops if:

    • Out of bounds
    • Value does not match expected sequence

This naturally leads to a DFS/backtracking approach:

  • At each step, we check the current value against what’s expected.
  • Move in the current diagonal.
  • If we haven’t turned yet, we also try turning clockwise.
  • Track the maximum length.

🛠 Step-by-Step Approach

  1. Define 4 diagonal directions: 
   0: (1,1)   ↘
   1: (1,-1)  ↙
   2: (-1,1)  ↗
   3: (-1,-1) ↖
Enter fullscreen mode Exit fullscreen mode
  1. Clockwise turn mapping: 
   ↘ (0) → ↙ (1)
   ↙ (1) → ↖ (3)
   ↗ (2) → ↘ (0)
   ↖ (3) → ↗ (2)
Enter fullscreen mode Exit fullscreen mode
  1. DFS exploration:

  • Expected values cycle as:

     step=0 → 1  
 step=1 → 2  
 step=2 → 0  
 step=3 → 2  
 step=4 → 0 ...

  • Continue in the same direction if valid.

  • If not turned yet, try the clockwise turn.

  1. Iterate over all cells:
  • Start DFS only from grid[i][j] == 1.
  • Try all 4 diagonals.
  • Track global maximum.

📜 Implementations

✅ C++ (original approach) 

class Solution {
public:
    int n, m;
    vector<vector<int>> grid;
    vector<pair<int,int>> directions = {{1,1}, {1,-1}, {-1,1}, {-1,-1}};

    int get_clock_wise_turn(int dir) {
        if (dir == 0) return 1;
        if (dir == 1) return 3;
        if (dir == 2) return 0;
        if (dir == 3) return 2;
        return -1;
    }

    int solveRE(int i, int j, int dir, int turned, int step) {
        if (i < 0 || j < 0 || i >= n || j >= m) return 0;

        int expected = (step == 0) ? 1 : ((step % 2 == 1) ? 2 : 0);
        if (grid[i][j] != expected) return 0;

        int best = 1 + solveRE(i + directions[dir].first,
                               j + directions[dir].second,
                               dir, turned, step + 1);

        if (!turned) {
            int new_dir = get_clock_wise_turn(dir);
            best = max(best, 1 + solveRE(i + directions[new_dir].first,
                                         j + directions[new_dir].second,
                                         new_dir, 1, step + 1));
        }
        return best;
    }

    int lenOfVDiagonal(vector<vector<int>>& g) {
        grid = g;
        n = grid.size();
        m = grid[0].size();
        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    for (int dir = 0; dir < 4; dir++) {
                        ans = max(ans, solveRE(i, j, dir, 0, 0));
                    }
                }
            }
        }
        return ans;
    }
};
Enter fullscreen mode Exit fullscreen mode

✅ Python 

class Solution:
    def lenOfVDiagonal(self, grid):
        n, m = len(grid), len(grid[0])
        directions = [(1,1), (1,-1), (-1,1), (-1,-1)]

        def get_turn(dir):
            if dir == 0: return 1
            if dir == 1: return 3
            if dir == 2: return 0
            if dir == 3: return 2

        def dfs(i, j, dir, turned, step):
            if i < 0 or j < 0 or i >= n or j >= m:
                return 0
            expected = 1 if step == 0 else (2 if step % 2 == 1 else 0)
            if grid[i][j] != expected:
                return 0

            di, dj = directions[dir]
            best = 1 + dfs(i+di, j+dj, dir, turned, step+1)

            if not turned:
                new_dir = get_turn(dir)
                di2, dj2 = directions[new_dir]
                best = max(best, 1 + dfs(i+di2, j+dj2, new_dir, True, step+1))
            return best

        ans = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    for dir in range(4):
                        ans = max(ans, dfs(i, j, dir, False, 0))
        return ans
Enter fullscreen mode Exit fullscreen mode

✅ Java 

class Solution {
    int n, m;
    int[][] grid;
    int[][] directions = {{1,1}, {1,-1}, {-1,1}, {-1,-1}};

    int getTurn(int dir) {
        if (dir == 0) return 1;
        if (dir == 1) return 3;
        if (dir == 2) return 0;
        return 2; // dir == 3
    }

    int dfs(int i, int j, int dir, boolean turned, int step) {
        if (i < 0 || j < 0 || i >= n || j >= m) return 0;
        int expected = (step == 0) ? 1 : ((step % 2 == 1) ? 2 : 0);
        if (grid[i][j] != expected) return 0;

        int best = 1 + dfs(i + directions[dir][0], j + directions[dir][1], dir, turned, step+1);
        if (!turned) {
            int newDir = getTurn(dir);
            best = Math.max(best, 1 + dfs(i + directions[newDir][0], j + directions[newDir][1], newDir, true, step+1));
        }
        return best;
    }

    public int lenOfVDiagonal(int[][] g) {
        grid = g;
        n = grid.length;
        m = grid[0].length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    for (int dir = 0; dir < 4; dir++) {
                        ans = Math.max(ans, dfs(i, j, dir, false, 0));
                    }
                }
            }
        }
        return ans;
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ JavaScript 

var lenOfVDiagonal = function(grid) {
    const n = grid.length, m = grid[0].length;
    const dirs = [[1,1],[1,-1],[-1,1],[-1,-1]];

    const getTurn = (dir) => {
        if (dir === 0) return 1;
        if (dir === 1) return 3;
        if (dir === 2) return 0;
        return 2;
    };

    const dfs = (i, j, dir, turned, step) => {
        if (i < 0 || j < 0 || i >= n || j >= m) return 0;
        const expected = step === 0 ? 1 : (step % 2 === 1 ? 2 : 0);
        if (grid[i][j] !== expected) return 0;

        let [di, dj] = dirs[dir];
        let best = 1 + dfs(i+di, j+dj, dir, turned, step+1);

        if (!turned) {
            const newDir = getTurn(dir);
            [di, dj] = dirs[newDir];
            best = Math.max(best, 1 + dfs(i+di, j+dj, newDir, true, step+1));
        }
        return best;
    };

    let ans = 0;
    for (let i=0; i<n; i++) {
        for (let j=0; j<m; j++) {
            if (grid[i][j] === 1) {
                for (let dir=0; dir<4; dir++) {
                    ans = Math.max(ans, dfs(i, j, dir, false, 0));
                }
            }
        }
    }
    return ans;
};
Enter fullscreen mode Exit fullscreen mode

✅ Go 

func LenOfVDiagonal(grid [][]int) int {
    n, m := len(grid), len(grid[0])
    dirs := [][]int{{1,1},{1,-1},{-1,1},{-1,-1}}

    getTurn := func(dir int) int {
        if dir == 0 { return 1 }
        if dir == 1 { return 3 }
        if dir == 2 { return 0 }
        return 2
    }

    var dfs func(i, j, dir int, turned bool, step int) int
    dfs = func(i, j, dir int, turned bool, step int) int {
        if i < 0 || j < 0 || i >= n || j >= m { return 0 }
        expected := 1
        if step > 0 {
            if step%2 == 1 { expected = 2 } else { expected = 0 }
        }
        if grid[i][j] != expected { return 0 }

        di, dj := dirs[dir][0], dirs[dir][1]
        best := 1 + dfs(i+di, j+dj, dir, turned, step+1)

        if !turned {
            nd := getTurn(dir)
            di2, dj2 := dirs[nd][0], dirs[nd][1]
            if t := 1 + dfs(i+di2, j+dj2, nd, true, step+1); t > best {
                best = t
            }
        }
        return best
    }

    ans := 0
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if grid[i][j] == 1 {
                for dir := 0; dir < 4; dir++ {
                    if t := dfs(i, j, dir, false, 0); t > ans {
                        ans = t
                    }
                }
            }
        }
    }
    return ans
}
Enter fullscreen mode Exit fullscreen mode

✅ C Sharp 

public class Solution {
    int n, m;
    int[][] grid;
    int[][] dirs = new int[][] { new int[]{1,1}, new int[]{1,-1}, new int[]{-1,1}, new int[]{-1,-1} };

    int GetTurn(int dir) {
        if (dir == 0) return 1;
        if (dir == 1) return 3;
        if (dir == 2) return 0;
        return 2;
    }

    int Dfs(int i, int j, int dir, bool turned, int step) {
        if (i < 0 || j < 0 || i >= n || j >= m) return 0;
        int expected = (step == 0) ? 1 : (step % 2 == 1 ? 2 : 0);
        if (grid[i][j] != expected) return 0;

        int best = 1 + Dfs(i + dirs[dir][0], j + dirs[dir][1], dir, turned, step+1);
        if (!turned) {
            int newDir = GetTurn(dir);
            best = Math.Max(best, 1 + Dfs(i + dirs[newDir][0], j + dirs[newDir][1], newDir, true, step+1));
        }
        return best;
    }

    public int LenOfVDiagonal(int[][] g) {
        grid = g;
        n = g.Length;
        m = g[0].Length;
        int ans = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (grid[i][j] == 1) {
                    for (int dir=0; dir<4; dir++) {
                        ans = Math.Max(ans, Dfs(i,j,dir,false,0));
                    }
                }
            }
        }
        return ans;
    }
}
Enter fullscreen mode Exit fullscreen mode

📊 Complexity Analysis

  • Time Complexity:

    • For each cell (n × m), we explore up to 4 directions.
    • Each DFS is bounded by grid size → O(n × m × max(n, m)).
    • In practice, most paths terminate early.

  • Space Complexity:

    • Recursion depth = diagonal length (≤ min(n, m)).
    • Extra space = O(min(n, m)).

💡 Key Takeaways

  • Grid traversal problems often become easier when you formalize directions and turns.
  • Using step indexing (step % 2) simplifies sequence tracking.
  • "At most one turn" is handled by a boolean flag in recursion.
  • Same algorithm works across languages once intuition is clear.

Top comments (0)