Zigzag (Diagonal) traversal of Matrix

The problem states that give a N * N square matrix A, traverse all the elements in a diagonals order from top to bottom.

Example

A = [[1, 2], [3, 4]]

Here the elements will be returned in the order {1, 2, 3, 4}.

Idea

Overall, the code performs a zigzag traversal of the input matrix, printing the elements in the specified order. The zigzag pattern is created by traversing the diagonals alternately from top to bottom and bottom to top. It starts with the top-left element and proceeds down each diagonal until the last column, then moves to the next column and repeats the process. After completing the top-to-bottom traversal, it starts from the second row, moving from bottom to top along each diagonal. The resulting sequence represents a zigzag pattern through the matrix elements.

Approach

• On keen observation it can be seen that the elements of the first row and last column are the starting points of the anti diagonals.
• For every point [i,j] the next element in that respective anti diagonal will be [i+1,j-1].
• So the key is to traverse these starting points one by one and add the elements in those respective anti diagonals to the answer array

Step 1: Initialize an empty answer array.

Step 2: Traverse the elements in the first row one by one followed by the elements in the last column. These elements will act as the starting points for the anti diagonals.

Step 3: Let [i,j] be the position of the starting point. For each starting point:

• Add the element at position [i,j] to the answer array.
• Increment i by one and decrement j by one. So the next element will be [i+1,j-1].
• Repeat the above two steps until you reach the end of that respective anti diagonal.

Step 4: Print the answer array.

Complexity

• Time Complexity:  O(N^2)
• Space Complexity: O(N)

Code

#Java

import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

class ZigZagMatrix {
    public static void main(String args[]) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int matrix[][] = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }

        ArrayList<Integer> result = getDiagonalElements(n, matrix);
        for (Integer val : result)
            System.out.print(val + " ");
        System.out.println();
    }

    static ArrayList<Integer> getDiagonalElements(int size, int[][] array) {
        ArrayList<Integer> result = new ArrayList<>();
        int row = 0;
        int col = 0;

        while (col < size) {
            int currentRow = row;
            int currentCol = col;

            while (currentRow < size && currentCol >= 0) {
                result.add(array[currentRow][currentCol]);
                currentRow++;
                currentCol--;
            }

            col++;
        }

        col = size - 1;
        row = 1;

        while (row < size) {
            int currentRow = row;
            int currentCol = col;

            while (currentRow < size && currentCol >= 0) {
                result.add(array[currentRow][currentCol]);
                currentRow++;
                currentCol--;
            }

            row++;
        }

        return result;
    }
}

Output

1, 3, 2, 4