498. Diagonal Traverse¶

Difficulty: Medium

498. Diagonal Traverse

Medium

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¶

class Solution {
    private ArrayList<Integer> res;
    private int count;
    public int[] findDiagonalOrder(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        res = new ArrayList<>();
        count = 0;
        for (int j = 0; j < m; j++) {
            fill(0, j, mat);
            count++;
        }
        for (int i = 1; i < n; i++) {
            fill(i, m - 1, mat);
            count++;
        }
        int ans[] = new int[res.size()];
        for (int i = 0; i < res.size(); i++) 
            ans[i] = res.get(i);
        return ans; 
    }
    private void fill(int startRow, int startCol, int arr[][]) {
        int n = arr.length, m = arr[0].length;
        ArrayList<Integer> temp = new ArrayList<>();
        while (startRow < n && startCol >= 0) {
            temp.add(arr[startRow][startCol]);
            startRow++;
            startCol--;
        }
        if (count % 2 == 0) {
            Collections.reverse(temp);
        }
        for (int ele : temp) 
            res.add(ele);
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here