498. Diagonal Traverse
https://leetcode.com/problems/diagonal-traverse/
Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.
Example:
Input: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Output: [1,2,4,7,5,3,6,8,9] Explanation:
Note:
The total number of elements of the given matrix will not exceed 10,000.
---
Intuition
Diagonal traversals are determined based on (r + c) % 2
Dimensions r, c can only increase, except on diagonals
Apply bounds check on every move
Even diagonal => go up = > r = r - 1, c = c + 1
Apply bounds check to both dimensions
If c + 1 is within bounds => c = c + 1
=> next column on 0th row
else r = r + 1
=> next row on last column
Intuition
Diagonal traversals are determined based on (r + c) % 2
Dimensions r, c can only increase, except on diagonals
Apply bounds check on every move
Even diagonal => go up = > r = r - 1, c = c + 1
Apply bounds check to both dimensions
If c + 1 is within bounds => c = c + 1
=> next column on 0th row
else r = r + 1
=> next row on last column
Odd diagonal => go down => r = r + 1, c = c - 1
Apply bounds check to both dimensions
If r + 1 is within bounds => r = r + 1
=> next row on 0th col
else c = c + 1
=> next col on last row
---
Time - O(R * C)
Space - O(1)
---
Related problems
1424-diagonal-traverse-ii
---
Apply bounds check to both dimensions
If r + 1 is within bounds => r = r + 1
=> next row on 0th col
else c = c + 1
=> next col on last row
---
Time - O(R * C)
Space - O(1)
---
Related problems
1424-diagonal-traverse-ii
---
