Zig Zag Traversal From Bottom

Print elements of a matrix in zig zag order starting from the bottom right corner

Understand the Problem

Problem Statement

Given a matrix of size M x N, print the elements of the matrix in zig zag order starting from the bottom right corner.

The traversal moves diagonally in alternating directions (up-right and down-left) until all elements are visited.

Constraints

1 ≤ M, N ≤ 100
Matrix elements can be any integers
Output should be space-separated on a single line

Examples

Example 1

Input

Output

9 6 8 7 5 3 2 4 1

Explanation

Starting from bottom right (9), we move up-right to 6, then down-left to 8, up-right to 7, down-left to 5, up-right to 3, down-left to 2, up-right to 4, and finally to 1. The pattern alternates between diagonal directions.

Example 2

Input

3 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15

Output

15 10 14 13 9 5 4 8 12 11 7 3 2 6 1

Explanation

Starting from bottom right (15), the traversal follows the zig zag pattern: 15→10→14→13→9→5→4→8→12→11→7→3→2→6→1, alternating between up-right and down-left diagonal movements.

Solution

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int r, c;
    scanf("%d%d", &r, &c);
    
    int arr[r][c];
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    
    int counter = 1; // 1 for up-right, 0 for down-left
    int i = r - 1, j = c - 1;
    
    while(i >= 0 && j >= 0) {
        printf("%d ", arr[i][j]);
        
        if(counter) {
            // Moving up-right
            if(j == c - 1 || i == 0) {
                // Hit boundary, switch direction
                if(i == 0) {
                    j--;
                } else {
                    i--;
                }
                counter = 0;
            } else {
                i--;
                j++;
            }
        } else {
            // Moving down-left
            if(j == 0 || i == r - 1) {
                // Hit boundary, switch direction
                if(j == 0) {
                    i--;
                } else {
                    j--;
                }
                counter = 1;
            } else {
                i++;
                j--;
            }
        }
    }
    
    return 0;
}

Time:O(M × N)

Space:O(1)

Approach:

Algorithm Explanation:

Input Reading: Read matrix dimensions and populate the 2D array
Direction Control: Use 'counter' variable to track current movement direction (1 = up-right, 0 = down-left)
Main Loop: Continue until we go out of matrix bounds
Boundary Handling: When hitting edges, determine next position and switch direction
Diagonal Movement: Move diagonally until hitting another boundary

Key Logic: The algorithm alternates between two diagonal patterns, switching direction when it encounters matrix boundaries (top row, bottom row, leftmost column, or rightmost column).

Visual Explanation

Loading diagram...

All Problems