Diagonal Traverse - Practice Coding Problems

Diagonal Traverse - Problem

Given an m x n matrix mat, return an array of all the elements of the matrix traversed in diagonal order.

The diagonal traversal follows a zigzag pattern: starting from the top-left corner, move diagonally up-right, then when hitting a boundary, move to the next diagonal and go down-left, alternating this pattern until all elements are visited.

Example: For matrix [[1,2,3],[4,5,6],[7,8,9]], the diagonal order is [1,2,4,7,5,3,6,8,9].

Input & Output

Example 1 — Basic 3x3 Matrix

$ Input: mat = [[1,2,3],[4,5,6],[7,8,9]]

› Output: [1,2,4,7,5,3,6,8,9]

💡 Note: Start at (0,0)=1, move up-right to (0,1)=2, hit top boundary so switch to down-left: (1,0)=4, hit left boundary so switch to up-right: (2,0)=7, (1,1)=5, (0,2)=3, and so on following the diagonal zigzag pattern.

Example 2 — Rectangular Matrix

$ Input: mat = [[1,2],[3,4]]

› Output: [1,2,3,4]

💡 Note: Start at (0,0)=1, move to (0,1)=2, hit right boundary so move down to (1,0)=3, then to (1,1)=4. The diagonal pattern handles rectangular matrices correctly.

Example 3 — Single Row

$ Input: mat = [[1,2,3,4]]

› Output: [1,2,3,4]

💡 Note: With only one row, we traverse left to right since each element forms its own diagonal.

Constraints

m == mat.length
n == mat[i].length
1 ≤ m, n ≤ 10⁴
1 ≤ m * n ≤ 10⁴
-10⁵ ≤ mat[i][j] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

3x3 matrix with elements 1-9

Diagonal Pattern

Follow diagonals, alternating up-right and down-left

Output Array

Elements collected in diagonal order

Key Takeaway

🎯 Key Insight: Track diagonal direction and handle boundary conditions to simulate the zigzag traversal pattern efficiently

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is to simulate the diagonal traversal directly by tracking direction and handling boundary conditions. The optimal approach uses direct simulation with O(m×n) time and O(1) space by maintaining current position and direction state while traversing each diagonal path.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Direct Simulation	O(m×n)	O(1)	Single pass traversal with direction tracking and boundary handling
Brute Force - Diagonal by Diagonal	O(m×n)	O(m×n)	Process each diagonal separately, collecting elements in the correct order

Optimized - Direct Simulation — Algorithm Steps

Step 1: Start at top-left, moving up-right
Step 2: When hitting boundary, switch direction and move to next diagonal
Step 3: Continue until all elements visited

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Up-Right

Begin at (0,0) moving diagonally up-right

Hit Boundary

Change direction when reaching matrix edge

Continue Pattern

Alternate between up-right and down-left

Code -

solution.c — C

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

int* solution(int** mat, int matSize, int* matColSize, int* returnSize) {
    if (matSize == 0 || matColSize[0] == 0) {
        *returnSize = 0;
        return NULL;
    }
    
    int m = matSize, n = matColSize[0];
    int* result = (int*)malloc(m * n * sizeof(int));
    int row = 0, col = 0;
    int goingUp = 1;
    
    for (int i = 0; i < m * n; i++) {
        result[i] = mat[row][col];
        
        if (goingUp) {
            // Moving diagonally up-right
            if (col == n - 1) {  // Hit right boundary
                row++;
                goingUp = 0;
            } else if (row == 0) {  // Hit top boundary
                col++;
                goingUp = 0;
            } else {  // Continue up-right
                row--;
                col++;
            }
        } else {
            // Moving diagonally down-left
            if (row == m - 1) {  // Hit bottom boundary
                col++;
                goingUp = 1;
            } else if (col == 0) {  // Hit left boundary
                row++;
                goingUp = 1;
            } else {  // Continue down-left
                row++;
                col--;
            }
        }
    }
    
    *returnSize = m * n;
    return result;
}

int main() {
    // Simplified parsing for demonstration
    int mat[3][3] = {{1,2,3}, {4,5,6}, {7,8,9}};
    int* matPtrs[3] = {mat[0], mat[1], mat[2]};
    int colSizes[3] = {3, 3, 3};
    
    int returnSize;
    int* result = solution(matPtrs, 3, colSizes, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Visit each element exactly once during traversal

✓ Linear Growth

Space Complexity

O(1)

Only use constant extra space for direction and position tracking

✓ Linear Space

78.0K Views

Medium Frequency

~15 min Avg. Time

2.2K 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

Optimized - Direct Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler