Print Diagonally

JavaView on GFG

Time: O(n^2)

Space: O(n^2)

Intuition

Print matrix elements diagonally (anti-diagonal order). Group elements by i+j sum.

Algorithm

1Elements with same i+j are on same anti-diagonal. Iterate diagonal index 0 to m+n-2. Print elements in each diagonal.

Common Pitfalls

•Index trick: diagonal d contains elements where row+col=d. Bounds: row in [max(0,d-n+1), min(d,m-1)].

Print Diagonally.java

Java


// Approach: Iterate diagonals from top-left to bottom-right.
// Each diagonal d has elements at (row, col) where row - col = constant.
// Walk from top-right to bottom-left of each diagonal using row/col iterators.
// Time: O(n^2) Space: O(n^2)
import java.util.*;

class Solution {

    static ArrayList<Integer> diagView(int mat[][]) {
        int n = mat.length;
        int cnt = n + n - 1;
        int row = 0;
        int col = 0;
        ArrayList<Integer> result = new ArrayList<>();
        while (cnt > 0) {
            int colIterator = Math.min(col, n - 1);
            int rowIterator = Math.min(row, n - 1);

            while (colIterator >= 0 && rowIterator < n) {
                result.add(mat[rowIterator][colIterator]);
                rowIterator++;
                colIterator--;
            }
            col++;
            if (col >= n) {
                row++;
            }
            cnt--;
        }
        
        return result;
    }
}

Was this solution helpful?