Length of Longest V-Shaped Diagonal Segment

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 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.

Input & Output

Example 1 — Basic V-Shape

$ Input: grid = [[1,2,0],[0,2,0],[1,0,2]]

› Output: 4

💡 Note: Starting at (0,0) with value 1, go diagonally down-right: 1→2→0→2. This forms a valid V-shaped segment of length 4.

Example 2 — No Valid Segment

$ Input: grid = [[1,1,1],[1,1,1],[1,1,1]]

› Output: 1

💡 Note: Only single cells with value 1 can form segments of length 1, as the sequence 2,0,2,0... cannot be followed.

Example 3 — V-Shape with Turn

$ Input: grid = [[1,0,0],[2,0,0],[0,2,0]]

› Output: 4

💡 Note: Start at (0,0), go down to (1,0), then turn right to (2,1): 1→2→0→2. V-shape with turn, length 4.

Constraints

1 ≤ n, m ≤ 1000
grid[i][j] ∈ {0, 1, 2}
At least one element in the grid

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D matrix with values 0, 1, 2

Pattern Matching

Find segments following 1→2→0→2→0... pattern

V-Shape Formation

Allow one clockwise 90° turn to form V-shape

Key Takeaway

🎯 Key Insight: V-shapes are diagonal paths following a specific pattern with at most one clockwise turn

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that a V-shaped diagonal segment follows a specific pattern (1→2→0→2→0...) and can make at most one clockwise 90-degree turn. The optimal approach uses DFS with memoization to explore all possible paths while caching results to avoid redundant calculations. Time: O(nm × 4 × L × 2), Space: O(nm × 4 × L × 2).

Common Approaches

Approach	Time	Space	Notes
✓ Memoization with DFS	O(nm × 4 × L × 2)	O(nm × 4 × L × 2)	Cache intermediate results to avoid redundant calculations
Brute Force DFS	O(n²m²)	O(nm)	Try all starting positions and explore all possible V-shaped paths

Memoization with DFS — Algorithm Steps

Step 1: Create a memoization cache for (row, col, direction, position, hasTurned)
Step 2: Before recursive calls, check if result is cached
Step 3: Store computed results in cache before returning
Step 4: Return the maximum length found across all starting positions

Visualization

Tap to expand

Step-by-Step Walkthrough

State

Define state as (row, col, direction, position, hasTurned)

Cache

Store computed results in hash map for quick lookup

Reuse

Return cached result if same state visited again

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 1000
#define HASH_SIZE 100007

int directions[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int n, m;

typedef struct HashNode {
    char key[100];
    int value;
    struct HashNode* next;
} HashNode;

HashNode* hashTable[HASH_SIZE];

int hash(char* key) {
    int hash = 0;
    while (*key) {
        hash = (hash * 31 + *key) % HASH_SIZE;
        key++;
    }
    return hash;
}

int getFromHash(char* key) {
    int h = hash(key);
    HashNode* node = hashTable[h];
    while (node) {
        if (strcmp(node->key, key) == 0) {
            return node->value;
        }
        node = node->next;
    }
    return -1; // not found
}

void putInHash(char* key, int value) {
    int h = hash(key);
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    strcpy(node->key, key);
    node->value = value;
    node->next = hashTable[h];
    hashTable[h] = node;
}

int getExpectedValue(int pos) {
    if (pos == 0) return 1;
    return pos % 2 == 1 ? 2 : 0;
}

int getNextDirectionIdx(int currDirIdx) {
    return (currDirIdx + 1) % 4;
}

int dfs(int** grid, int r, int c, int dirIdx, int pos, int hasTurned) {
    if (r < 0 || r >= n || c < 0 || c >= m) return 0;
    
    char state[100];
    sprintf(state, "%d,%d,%d,%d,%d", r, c, dirIdx, pos, hasTurned);
    
    int cached = getFromHash(state);
    if (cached != -1) return cached;
    
    int expected = getExpectedValue(pos);
    if (grid[r][c] != expected) {
        putInHash(state, 0);
        return 0;
    }
    
    int maxLen = 1;
    
    // Continue in same direction
    int nextLen = dfs(grid, r + directions[dirIdx][0], c + directions[dirIdx][1], dirIdx, pos + 1, hasTurned);
    if (1 + nextLen > maxLen) maxLen = 1 + nextLen;
    
    // Try making a turn if we haven't turned yet
    if (!hasTurned) {
        int newDirIdx = getNextDirectionIdx(dirIdx);
        int turnLen = dfs(grid, r + directions[newDirIdx][0], c + directions[newDirIdx][1], newDirIdx, pos + 1, 1);
        if (1 + turnLen > maxLen) maxLen = 1 + turnLen;
    }
    
    putInHash(state, maxLen);
    return maxLen;
}

int solution(int** grid, int rows, int cols) {
    n = rows;
    m = cols;
    
    // Initialize hash table
    for (int i = 0; i < HASH_SIZE; i++) {
        hashTable[i] = NULL;
    }
    
    int maxLength = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 1) {
                for (int k = 0; k < 4; k++) {
                    int length = dfs(grid, i, j, k, 0, 0);
                    if (length > maxLength) maxLength = length;
                }
            }
        }
    }
    
    return maxLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int** grid = (int**)malloc(10 * sizeof(int*));
    for (int i = 0; i < 10; i++) {
        grid[i] = (int*)malloc(10 * sizeof(int));
    }
    
    char* ptr = line + 1;
    int rows = 0, cols = 0;
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            cols = 0;
            while (*ptr && *ptr != ']') {
                if (*ptr >= '0' && *ptr <= '9') {
                    grid[rows][cols++] = *ptr - '0';
                }
                ptr++;
            }
            rows++;
        }
        ptr++;
    }
    
    int result = solution(grid, rows, cols);
    printf("%d\n", result);
    
    for (int i = 0; i < 10; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(nm × 4 × L × 2)

Each cell can be visited at most once for each combination of direction (4), position in pattern (L), and turn status (2)

✓ Linear Growth

Space Complexity

O(nm × 4 × L × 2)

Memoization cache stores results for each unique state combination plus recursion stack

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

240 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoization with DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler