2025-08-27 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's August LeetCoding Challenge with cpp.

August LeetCoding Challenge 27

Description

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.

 

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

class Solution {
  const int MOVES[4][2] = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
  int dfs(
    int i, 
    int j, 
    int k, 
    int canTurn, int target,
    vector<vector<int>>& grid,
    vector<vector<vector<int>>>& memo)
  {
    i += MOVES[k][0];
    j += MOVES[k][1];
    if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != target) {
      return 0;
    }
    int mask = (k << 1) | canTurn;
    if (memo[i][j][mask] > 0) return memo[i][j][mask];

    int res = dfs(i, j, k, canTurn, 2 - target, grid, memo);
    if (canTurn == 1) {
      vector<int> maxs = {int(grid.size() - i - 1), j, i, (int)grid[0].size() - j - 1};
      int nk = (k + 1) % 4;
      if (maxs[nk] > res) {
        res = max(res, dfs(i, j, nk, 0, 2 - target, grid, memo));
      }
    }
    return memo[i][j][mask] = res + 1;
  }
public:
  int lenOfVDiagonal(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<vector<int>>> memo(m, vector<vector<int>>(n, vector<int>(1 << 3, 0)));
    int answer = 0;

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (grid[i][j] != 1) continue;
        vector<int> maxs = {m - i, j + 1, i + 1, n - j};
        for (int k = 0; k < 4; k++) {
          if (maxs[k] > answer) {
            answer = max(answer, dfs(i, j, k, 1, 2, grid, memo) + 1);
          }
        }
      }
    }
    return answer;
  }
};

// Accepted
// 561/561 cases passed (513 ms)
// Your runtime beats 59.5 % of cpp submissions
// Your memory usage beats 19.5 % of cpp submissions (298 MB)
Algorithm