Diagonal Traverse

76.Diagonal Traverse

Array

Matrix

Problem Statement:

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

Example:

Input:

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

→

Output:

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

Explanation: Traverse diagonally from top-left to bottom-right.

Algorithm:

1. Initialize a result array to store the traversal.
2. Start at the top-left corner of the matrix (0,0).
3. Iterate through all elements of the result array:
• Store the current matrix element in the result array.
• Check the sum of the current indices i + j to determine the traversal direction:
• If the sum is even, move upward-right.
• If the sum is odd, move downward-left.
• Handle edge cases when hitting the boundaries of the matrix.
4. Return the result array after filling it.

Complexity:

Time: O(m * n) | Space: O(m * n)

Java Implementation:

public int[] findDiagonalOrder(int[][] matrix) {
    if (matrix.length == 0) return new int[0];
    
    int m = matrix.length, n = matrix[0].length;
    int[] result = new int[m * n];
    int i = 0, j = 0;

    for (int idx = 0; idx < result.length; idx++) {
        result[idx] = matrix[i][j];
        
        if ((i + j) % 2 == 0) {
            if (j == n - 1) i++;
            else if (i == 0) j++;
            else { i--; j++; }
        } else {
            if (i == m - 1) j++;
            else if (j == 0) i++;
            else { i++; j--; }
        }
    }
    
    return result;
}

Python Implementation:

def findDiagonalOrder(matrix):
    if not matrix:
        return []
    
    m, n = len(matrix), len(matrix[0])
    result = []
    i, j = 0, 0

    for _ in range(m * n):
        result.append(matrix[i][j])
        if (i + j) % 2 == 0:
            if j == n - 1:
                i += 1
            elif i == 0:
                j += 1
            else:
                i -= 1
                j += 1
        else:
            if i == m - 1:
                j += 1
            elif j == 0:
                i += 1
            else:
                i += 1
                j -= 1
    
    return result

C++ Implementation:

#include 
using namespace std;

vector findDiagonalOrder(vector>& matrix) {
    if (matrix.empty()) return {};
    
    int m = matrix.size(), n = matrix[0].size();
    vector result;
    int i = 0, j = 0;

    for (int idx = 0; idx < m * n; idx++) {
        result.push_back(matrix[i][j]);
        if ((i + j) % 2 == 0) {
            if (j == n - 1) i++;
            else if (i == 0) j++;
            else { i--; j++; }
        } else {
            if (i == m - 1) j++;
            else if (j == 0) i++;
            else { i++; j--; }
        }
    }
    
    return result;
}