3459. Length of Longest V-Shaped Diagonal Segment LeetCode Solution
In this guide, you will get 3459. Length of Longest V-Shaped Diagonal Segment LeetCode Solution with the best time and space complexity. The solution to Length of Longest V-Shaped Diagonal Segment problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Length of Longest V-Shaped Diagonal Segment
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.
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).
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).
3459. Length of Longest V-Shaped Diagonal Segment LeetCode Solution in C++
class Solution {
public:
int lenOfVDiagonal(vector<vector<int>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
vector<vector<vector<vector<vector<int>>>>> mem(
m, vector<vector<vector<vector<int>>>>(
n, vector<vector<vector<int>>>(
, vector<vector<int>>(2, vector<int>(4, -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 d = 0; d < 4; ++d) {
const auto& [dx, dy] = dirs[d];
res = max(res, 1 + dfs(grid, i + dx, j + dy, /*turned=*/false, 2, d,
mem));
}
return res;
}
private:
static constexpr int dirs[4][2] = {{-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
int dfs(const vector<vector<int>>& grid, int i, int j, bool turned, int num,
int dir, vector<vector<vector<vector<vector<int>>>>>& mem) {
if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size())
return 0;
if (grid[i][j] != num)
return 0;
const int hashNum = max(0, num - 1);
if (mem[i][j][turned][hashNum][dir] != -1)
return mem[i][j][turned][hashNum][dir];
const int nextNum = num == 2 ? 0 : 2;
const auto& [dx, dy] = dirs[dir];
int res = 1 + dfs(grid, i + dx, j + dy, turned, nextNum, dir, mem);
if (!turned) {
const int nextDir = (dir + 1) % 4;
const auto& [nextDx, nextDy] = dirs[nextDir];
res = max(res, 1 + dfs(grid, i + nextDx, j + nextDy, /*turned=*/true,
nextNum, nextDir, mem));
}
return mem[i][j][turned][hashNum][dir] = res;
}
}; /* code provided by PROGIEZ */
3459. Length of Longest V-Shaped Diagonal Segment LeetCode Solution in Java
class Solution {
public int lenOfVDiagonal(int[][] grid) {
final int m = grid.length;
final int n = grid[0].length;
Integer[][][][][] mem = new Integer[m][n][2][2][4];
int ans = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 1)
for (int d = 0; d < 4; ++d) {
final int dx = dirs[d][0];
final int dy = dirs[d][1];
ans = Math.max(ans, 1 + dfs(grid, i + dx, j + dy, /*turned=*/false, 2, d, mem));
}
return ans;
}
private static final int[][] dirs = {{-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
private int dfs(int[][] grid, int i, int j, boolean turned, int num, int dir,
Integer[][][][][] mem) {
if (i < 0 || i == grid.length || j < 0 || j == grid[0].length)
return 0;
if (grid[i][j] != num)
return 0;
final int hashNum = Math.max(0, num - 1);
if (mem[i][j][turned ? 1 : 0][hashNum][dir] != null)
return mem[i][j][turned ? 1 : 0][hashNum][dir];
final int nextNum = num == 2 ? 0 : 2;
final int dx = dirs[dir][0], dy = dirs[dir][1];
int res = 1 + dfs(grid, i + dx, j + dy, turned, nextNum, dir, mem);
if (!turned) {
final int nextDir = (dir + 1) % 4;
final int nextDx = dirs[nextDir][0], nextDy = dirs[nextDir][1];
res = Math.max(res,
+ dfs(grid, i + nextDx, j + nextDy, /*turned=*/true, nextNum, nextDir, mem));
}
return mem[i][j][turned ? 1 : 0][hashNum][dir] = res;
}
} // code provided by PROGIEZ
3459. Length of Longest V-Shaped Diagonal Segment LeetCode Solution in Python
class Solution:
def lenOfVDiagonal(self, grid: list[list[int]]) -> int:
dirs = ((-1, 1), (1, 1), (1, -1), (-1, -1))
@functools.lru_cache(None)
def dfs(i: int, j: int, turned: bool, num: int, dir: int) -> int:
if i < 0 or i == len(grid) or j < 0 or j == len(grid[0]):
return 0
if grid[i][j] != num:
return 0
nextNum = 0 if num == 2 else 2
dx, dy = dirs[dir]
res = 1 + dfs(i + dx, j + dy, turned, nextNum, dir)
if not turned:
nextDir = (dir + 1) % 4
nextDx, nextDy = dirs[nextDir]
res = max(res, 1 + dfs(i + nextDx, j + nextDy, 1, nextNum, nextDir))
return res
return max((1 + dfs(i + dx, j + dy, 0, 2, d)
for i, row in enumerate(grid)
for j, num in enumerate(row)
if num == 1
for d, (dx, dy) in enumerate(dirs)),
default=0) # code by PROGIEZ
