Practice/Meta/Leetcode 498. Diagonal Traverse

Leetcode 498. Diagonal Traverse

CodingMust

Problem

Given an m × n matrix, return all elements in a diagonal zigzag order. You should traverse the matrix along its diagonals, alternating the direction between upward-right and downward-left with each diagonal line.

Starting from the top-left corner, collect elements along diagonals where the first diagonal goes up-right, the second goes down-left, the third goes up-right, and so on.

Requirements

1. Return all matrix elements as a single flat array
2. Traverse along diagonal lines (where row + column sum is constant)
3. Alternate the direction of traversal for each successive diagonal
4. Handle rectangular matrices of any valid dimensions

Constraints

• m == mat.length (number of rows)
• n == mat[i].length (number of columns)
• 1 ≤ m, n ≤ 10^4
• 1 ≤ m * n ≤ 10^4
• -10^5 ≤ mat[i][j] ≤ 10^5

Examples

Example 1:

Input: mat = [[1,2,3],[4,5,6]] Output: [1,2,4,5,3,6] Explanation: Diagonal 0: [1] (going up) Diagonal 1: [2,4] (going down) Diagonal 2: [5,3] (going up) Diagonal 3: [6] (going down)

Example 2:

Input: mat = [[1,2],[3,4]] Output: [1,2,3,4] Explanation: Diagonal 0: [1] Diagonal 1: [2,3] reversed becomes [3,2] but we want [2,3] Wait, direction alternates: Diagonal 0: [1] (up-right) Diagonal 1: [2,3] (down-left, so order is 2,3) Diagonal 2: [4] (up-right) Result: [1,2,3,4]

Example 3:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,4,7,5,3,6,8,9] Explanation: Follow the zigzag diagonal pattern through all 5 diagonals