LeetCodee

498. Diagonal Traverse

Jump to Solution: Python Java C++ JavaScript C#

Problem Description

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

Example 1:

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

Example 2:

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

Constraints:

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

Solution

Python Solution

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        if not mat or not mat[0]:
            return []
            
        m, n = len(mat), len(mat[0])
        result = []
        row = col = 0
        direction = 1  # 1 for up-right, -1 for down-left
        
        while len(result) < m * n:
            result.append(mat[row][col])
            
            if direction == 1:
                if col == n - 1:
                    row += 1
                    direction = -1
                elif row == 0:
                    col += 1
                    direction = -1
                else:
                    row -= 1
                    col += 1
            else:
                if row == m - 1:
                    col += 1
                    direction = 1
                elif col == 0:
                    row += 1
                    direction = 1
                else:
                    row += 1
                    col -= 1
        
        return result

Time Complexity: O(m × n)

Where m and n are the dimensions of the matrix. We visit each element exactly once.

Space Complexity: O(1)

Not counting the space needed for output array.

Java Solution

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        if (mat == null || mat.length == 0) {
            return new int[0];
        }
        
        int m = mat.length, n = mat[0].length;
        int[] result = new int[m * n];
        int row = 0, col = 0, index = 0;
        int direction = 1;  // 1 for up-right, -1 for down-left
        
        while (index < m * n) {
            result[index++] = mat[row][col];
            
            if (direction == 1) {
                if (col == n - 1) {
                    row++;
                    direction = -1;
                } else if (row == 0) {
                    col++;
                    direction = -1;
                } else {
                    row--;
                    col++;
                }
            } else {
                if (row == m - 1) {
                    col++;
                    direction = 1;
                } else if (col == 0) {
                    row++;
                    direction = 1;
                } else {
                    row++;
                    col--;
                }
            }
        }
        
        return result;
    }
}

Time Complexity: O(m × n)

Where m and n are the dimensions of the matrix. We visit each element exactly once.

Space Complexity: O(1)

Not counting the space needed for output array.

C++ Solution

class Solution {
public:
    vector findDiagonalOrder(vector>& mat) {
        if (mat.empty() || mat[0].empty()) {
            return {};
        }
        
        int m = mat.size(), n = mat[0].size();
        vector result;
        int row = 0, col = 0;
        int direction = 1;  // 1 for up-right, -1 for down-left
        
        while (result.size() < m * n) {
            result.push_back(mat[row][col]);
            
            if (direction == 1) {
                if (col == n - 1) {
                    row++;
                    direction = -1;
                } else if (row == 0) {
                    col++;
                    direction = -1;
                } else {
                    row--;
                    col++;
                }
            } else {
                if (row == m - 1) {
                    col++;
                    direction = 1;
                } else if (col == 0) {
                    row++;
                    direction = 1;
                } else {
                    row++;
                    col--;
                }
            }
        }
        
        return result;
    }
};

Time Complexity: O(m × n)

Where m and n are the dimensions of the matrix. We visit each element exactly once.

Space Complexity: O(1)

Not counting the space needed for output array.

JavaScript Solution

/**
 * @param {number[][]} mat
 * @return {number[]}
 */
var findDiagonalOrder = function(mat) {
    if (!mat || !mat.length) {
        return [];
    }
    
    const m = mat.length, n = mat[0].length;
    const result = [];
    let row = 0, col = 0;
    let direction = 1;  // 1 for up-right, -1 for down-left
    
    while (result.length < m * n) {
        result.push(mat[row][col]);
        
        if (direction === 1) {
            if (col === n - 1) {
                row++;
                direction = -1;
            } else if (row === 0) {
                col++;
                direction = -1;
            } else {
                row--;
                col++;
            }
        } else {
            if (row === m - 1) {
                col++;
                direction = 1;
            } else if (col === 0) {
                row++;
                direction = 1;
            } else {
                row++;
                col--;
            }
        }
    }
    
    return result;
};

Time Complexity: O(m × n)

Where m and n are the dimensions of the matrix. We visit each element exactly once.

Space Complexity: O(1)

Not counting the space needed for output array.

C# Solution

public class Solution {
    public int[] FindDiagonalOrder(int[][] mat) {
        if (mat == null || mat.Length == 0) {
            return new int[0];
        }
        
        int m = mat.Length, n = mat[0].Length;
        int[] result = new int[m * n];
        int row = 0, col = 0, index = 0;
        int direction = 1;  // 1 for up-right, -1 for down-left
        
        while (index < m * n) {
            result[index++] = mat[row][col];
            
            if (direction == 1) {
                if (col == n - 1) {
                    row++;
                    direction = -1;
                } else if (row == 0) {
                    col++;
                    direction = -1;
                } else {
                    row--;
                    col++;
                }
            } else {
                if (row == m - 1) {
                    col++;
                    direction = 1;
                } else if (col == 0) {
                    row++;
                    direction = 1;
                } else {
                    row++;
                    col--;
                }
            }
        }
        
        return result;
    }
}

Time Complexity: O(m × n)

Where m and n are the dimensions of the matrix. We visit each element exactly once.

Space Complexity: O(1)

Not counting the space needed for output array.

Approach Explanation

The solution uses a simulation approach:

  1. Key Insights:
    • Direction tracking
    • Boundary handling
    • Pattern recognition
    • Coordinate manipulation
  2. Algorithm Steps:
    • Initialize direction
    • Handle boundaries
    • Update coordinates
    • Build result array

Implementation Details:

  • Direction flag
  • Coordinate tracking
  • Boundary checks
  • Result building

Optimization Insights:

  • Single pass
  • In-place tracking
  • Minimal variables
  • Early termination

Edge Cases:

  • Empty matrix
  • Single row/column
  • Square matrix
  • Rectangular matrix