Zigzag Matrix Traversal

Java coding interview problem for Matrix Problems: Zigzag Matrix Traversal.

Zigzag matrix traversal is a popular matrix traversal problem where elements are visited in an alternating direction pattern.

Unlike:

Normal row traversal
Column traversal
Spiral traversal

zigzag traversal changes direction after every row or column.

This problem tests:

Matrix indexing
Direction handling
Conditional traversal
Boundary management

What is Zigzag Matrix Traversal?

Zigzag traversal means visiting matrix elements in a pattern where:

One row is traversed left to right.
The next row is traversed right to left.
This pattern continues alternatively.

Example

Input:

Normal row traversal:

Output:

[1,2,3,4,5,6,7,8,9,10,11,12]

Zigzag traversal:

Row 0:

Left → Right

Output:

1 2 3 4

Row 1:

Right → Left

Output:

8 7 6 5

Row 2:

Left → Right

Output:

9 10 11 12

Final result:

[1,2,3,4,8,7,6,5,9,10,11,12]

Understanding Zigzag Pattern

For every row:

Even Row Index

Traverse:

Left → Right

Example:

row = 0

row = 2

row = 4

Odd Row Index

Traverse:

Right → Left

Example:

row = 1

row = 3

row = 5

Matrix Visualization

Matrix:

1  2  3  4

5  6  7  8

9 10 11 12

13 14 15 16

Zigzag movement:

→ → → →

← ← ← ←

→ → → →

← ← ← ←

Traversal order:

1 2 3 4

8 7 6 5

9 10 11 12

16 15 14 13

Row-wise Zigzag vs Column-wise Zigzag

Zigzag traversal can be applied in different directions.

Row-wise Zigzag

Direction changes after every row.

Example:

→

←

→

←

Column-wise Zigzag

Direction changes after every column.

Example:

↓
↑
↓
↑

Difference Between Spiral and Zigzag Traversal

Many developers confuse these patterns.

Spiral Traversal

Movement:

Right

Down

Left

Up

Example:

1 2 3
8 9 4
7 6 5

Visits:

outer layer → inner layer

Zigzag Traversal

Movement:

Row direction changes

Example:

Visits:

row by row

Why Is Zigzag Matrix Traversal Asked in Interviews?

This problem tests:

1. Direction Control

Can you switch between:

Forward traversal

Reverse traversal

2. Index Manipulation

Can you correctly handle:

row index

column index

3. Algorithm Thinking

Can you convert:

visual movement

into

code logic

4. Edge Case Handling

Important cases:

Empty matrix
Single row
Single column
Rectangular matrix

Real-World Applications

Image Processing

Images are stored as:

Pixel Matrix

Zigzag scanning is used in:

Image compression
JPEG encoding
Signal processing

Data Compression

Zigzag ordering helps group similar frequency values.

Example:

JPEG uses zigzag scanning to:

Arrange DCT coefficients
Improve compression

Game Development

Grid-based games use zigzag movement for:

Board traversal
Path patterns
Animation sequences

Memory Optimization

Some systems process matrix data in alternating directions to improve cache behavior.

Problem Statement

Given a matrix:

m × n

return all elements in zigzag order.

Example 1

Input:

[
 [1,2,3],
 [4,5,6],
 [7,8,9]
]

Output:

[
1,2,3,6,5,4,7,8,9
]

Example 2

Input:

[
 [1,2,3,4],
 [5,6,7,8],
 [9,10,11,12]
]

Output:

[
1,2,3,4,
8,7,6,5,
9,10,11,12
]

Constraints

Example:

1 <= rows <= 1000

1 <= columns <= 1000

Direction Change Concept

The easiest way to solve zigzag traversal:

Maintain:

direction flag

Example:

boolean leftToRight = true;

If:

leftToRight == true

Traverse:

0 → columns-1

Otherwise:

Traverse:

columns-1 → 0

After every row:

Change direction:

leftToRight = !leftToRight;

Index Movement Pattern

For matrix:

rows = 3

columns = 4

Row 0:

column:

0 1 2 3

Row 1:

column:

3 2 1 0

Row 2:

column:

0 1 2 3

Dry Run Example

Input:

Initial:

direction = Left → Right

Row 0

Traverse:

1 2 3

Result:

[1,2,3]

Change direction.

Row 1

Traverse:

6 5 4

Result:

[1,2,3,6,5,4]

Change direction.

Row 2

Traverse:

7 8 9

Final:

[1,2,3,6,5,4,7,8,9]

Approach 1 — Brute Force Using Direction Flag

The simplest solution:

Traverse rows one by one.
Check row direction.
Reverse traversal when required.

Algorithm

For each row:

If row index is even:

left → right

If row index is odd:

right → left

Java Program

import java.util.*;

public class ZigzagMatrixTraversal {


    public static List<Integer> zigzag(
            int[][] matrix) {


        List<Integer> result =
                new ArrayList<>();


        int rows =
                matrix.length;


        int cols =
                matrix[0].length;


        for(int i = 0;
            i < rows;
            i++) {


            if(i % 2 == 0) {


                for(int j = 0;
                    j < cols;
                    j++) {


                    result.add(
                        matrix[i][j]);

                }

            }
            else {


                for(int j = cols - 1;
                    j >= 0;
                    j--) {


                    result.add(
                        matrix[i][j]);

                }

            }

        }


        return result;

    }


    public static void main(String[] args) {


        int[][] matrix =
                {
                    {1,2,3},
                    {4,5,6},
                    {7,8,9}
                };


        System.out.println(
                zigzag(matrix));

    }

}

Output

[1,2,3,6,5,4,7,8,9]

Step-by-Step Explanation

Input:

Row 0:

Even row:

Left → Right

Add:

1 2 3

Row 1:

Odd row:

Right → Left

Add:

6 5 4

Row 2:

Even row:

Left → Right

Add:

7 8 9

Complexity Analysis

For:

m × n

matrix:

Every element is visited once.

Time:

O(m × n)

Space:

O(1)

excluding output list.

Advantages

Simple.
Easy to understand.
Efficient.
Interview friendly.

Drawbacks

Only handles row-wise zigzag.
Does not show general direction control.

Approach 2 — Direction Flag Based Traversal

The previous approach uses:

row index % 2

to decide direction.

A more flexible approach uses a direction flag.

This allows us to easily change:

Row direction
Column direction
Traversal pattern

Core Idea

Maintain:

boolean leftToRight

Initially:

true

Meaning:

Traverse left → right

After every row:

leftToRight = !leftToRight

Algorithm

Start from first row.
Check direction.
Traverse current row.
Reverse direction.
Continue until all rows are processed.

Java Program — Direction Flag

import java.util.ArrayList;
import java.util.List;

public class ZigzagDirectionTraversal {


    public static List<Integer> zigzag(
            int[][] matrix) {


        List<Integer> result =
                new ArrayList<>();


        int rows =
                matrix.length;


        int cols =
                matrix[0].length;


        boolean leftToRight = true;


        for(int i = 0;
            i < rows;
            i++) {


            if(leftToRight) {


                for(int j = 0;
                    j < cols;
                    j++) {


                    result.add(
                        matrix[i][j]);

                }

            }
            else {


                for(int j = cols - 1;
                    j >= 0;
                    j--) {


                    result.add(
                        matrix[i][j]);

                }

            }


            leftToRight =
                    !leftToRight;

        }


        return result;

    }

}

Complexity Analysis

For:

m × n matrix

Every element is visited once.

Time:

O(m × n)

Space:

O(1)

excluding output.

Column-Wise Zigzag Traversal

Zigzag traversal can also happen column by column.

Example:

Matrix:

Column 0:

Top → Bottom

Values:

1 4 7

Column 1:

Bottom → Top

Values:

8 5 2

Column 2:

Top → Bottom

Values:

3 6 9

Output:

[1,4,7,8,5,2,3,6,9]

Java Program — Column Zigzag

import java.util.ArrayList;
import java.util.List;

public class ColumnZigzagTraversal {


    public static List<Integer> traverse(
            int[][] matrix) {


        List<Integer> result =
                new ArrayList<>();


        int rows =
                matrix.length;


        int cols =
                matrix[0].length;


        boolean topToBottom = true;


        for(int col = 0;
            col < cols;
            col++) {


            if(topToBottom) {


                for(int row = 0;
                    row < rows;
                    row++) {


                    result.add(
                        matrix[row][col]);

                }

            }
            else {


                for(int row = rows - 1;
                    row >= 0;
                    row--) {


                    result.add(
                        matrix[row][col]);

                }

            }


            topToBottom =
                    !topToBottom;

        }


        return result;

    }

}

Diagonal Zigzag Traversal

Another common interview variation:

Traverse the matrix diagonally while changing direction.

Example:

Input:

Diagonal groups:

First diagonal:

Second:

2 4

Third:

7 5 3

Fourth:

6 8

Fifth:

Zigzag order:

LeetCode Zigzag Matrix Variations

Common problems:

1. Zigzag Level Order Traversal

Used in:

Binary Trees
Graph traversal

2. Diagonal Traverse

Pattern:

↗

↙

3. Image Compression Zigzag Scan

Used in:

JPEG encoding
DCT coefficient ordering

Recursive Approach

Zigzag traversal can be implemented recursively.

Concept:

Function:

traverse(row)

Process:

Traverse current row.
Reverse direction.
Call next row.

Example:

row = 0

process

row = 1

process reverse

row = 2

process forward

Recursive Java Example

import java.util.*;

public class ZigzagRecursive {


    static List<Integer> result =
            new ArrayList<>();


    public static void traverse(
            int[][] matrix,
            int row,
            boolean leftToRight) {


        if(row == matrix.length) {

            return;

        }


        if(leftToRight) {


            for(int col = 0;
                col < matrix[0].length;
                col++) {


                result.add(
                    matrix[row][col]);

            }

        }
        else {


            for(int col = matrix[0].length - 1;
                col >= 0;
                col--) {


                result.add(
                    matrix[row][col]);

            }

        }


        traverse(
            matrix,
            row + 1,
            !leftToRight);

    }

}

Java Streams Approach

Streams can implement zigzag traversal, but they are not preferred.

Reason:

Zigzag traversal requires:

Direction changes.
Index control.
Conditional ordering.

Traditional loops are clearer.

Example Stream Concept

IntStream.range(0, rows)
.flatMap(row ->
    row % 2 == 0
    ?
    IntStream.range(0, cols)
    :
    IntStream.iterate(
        cols-1,
        i -> i >= 0,
        i -> i-1
    )
)

Why Loops Are Preferred?

For matrix algorithms:

Loops provide:

Better performance.
Lower object creation.
Easier debugging.
Clear index handling.

Comparison of All Approaches

Approach	Time Complexity	Space Complexity	Best Use
Row Index Condition	O(m×n)	O(1)	Simple solution
Direction Flag	O(m×n)	O(1)	Recommended
Column Zigzag	O(m×n)	O(1)	Column problems
Diagonal Zigzag	O(m×n)	O(m×n)	Advanced traversal
Recursive	O(m×n)	O(m)	Learning
Streams	O(m×n)	Extra objects	Not preferred

Matrix Index Mapping

Row Zigzag

Even row:

(row,0 → cols-1)

Odd row:

(row,cols-1 → 0)

Column Zigzag

Even column:

(0,col → rows-1,col)

Odd column:

(rows-1,col → 0,col)

Primitive vs Object Arrays

Primitive Matrix

int[][]

Advantages:

Faster.
Less memory.
Better cache usage.

Object Matrix

Integer[][]

Advantages:

Supports null values.
Works with collections.

Disadvantages:

Higher memory usage.

Common Interview Mistakes

Mistake 1

Forgetting to reverse direction.

Example:

Wrong:

Normal traversal only.

Mistake 2

Wrong column boundaries.

Incorrect:

j <= cols

Correct:

j < cols

Mistake 3

Not handling empty matrix.

Always check:

matrix.length == 0

Mistake 4

Confusing:

Zigzag traversal

with:

Spiral traversal

Edge Cases

Input	Result
Empty matrix	[]
1×1 matrix	Single value
Single row	Normal order
Single column	Alternating not visible
Rectangular matrix	Works
Large matrix	Works efficiently

Interview Follow-up Questions

Q1. Print matrix in zigzag order.

Q2. Print column-wise zigzag.

Q3. Print diagonal zigzag traversal.

Q4. Rotate matrix and traverse zigzag.

Q5. Find kth element in zigzag order.

Q6. Convert image matrix into zigzag sequence.

Key Takeaways

Zigzag traversal is based on:

Same rows

Different directions

The core pattern:

Even row:

Left → Right


Odd row:

Right → Left

Best interview solution:

Direction Flag Approach

Complexity:

Time: O(m × n)

Space: O(1)

Frequently Asked Interview Questions

Q1. What is zigzag traversal?

Traversal where direction alternates after every row or column.

Q2. How do you change direction?

Use:

direction = !direction;

Q3. What is the complexity?

Every element is visited once:

O(m × n)

Q4. Difference between zigzag and spiral?

Zigzag:

row/column direction changes

Spiral:

boundary direction changes

Interview Tip

When asked:

"Traverse matrix in zigzag order."

Explain:

Identify traversal direction.
Maintain a direction flag.
Reverse traversal after every row.
Handle empty and rectangular matrices.

For senior interviews, discuss variations:

Row zigzag.
Column zigzag.
Diagonal zigzag.
Compression algorithms.

This demonstrates strong understanding of matrix traversal patterns and direction-based algorithms.

Zigzag Matrix Traversal

What is Zigzag Matrix Traversal?

Example

Understanding Zigzag Pattern

Even Row Index

Odd Row Index

Matrix Visualization

Row-wise Zigzag vs Column-wise Zigzag

Row-wise Zigzag

Column-wise Zigzag

Difference Between Spiral and Zigzag Traversal

Spiral Traversal

Zigzag Traversal

Why Is Zigzag Matrix Traversal Asked in Interviews?

1. Direction Control

2. Index Manipulation

3. Algorithm Thinking

4. Edge Case Handling

Real-World Applications

Image Processing

Data Compression

Game Development

Memory Optimization

Problem Statement

Example 1

Example 2

Constraints

Direction Change Concept

Index Movement Pattern

Dry Run Example

Row 0

Row 1

Row 2

Approach 1 — Brute Force Using Direction Flag

Algorithm

Java Program

Output

Step-by-Step Explanation

Complexity Analysis

Advantages

Drawbacks

Approach 2 — Direction Flag Based Traversal

Core Idea

Algorithm

Java Program — Direction Flag

Complexity Analysis

Column-Wise Zigzag Traversal

Java Program — Column Zigzag

Diagonal Zigzag Traversal

LeetCode Zigzag Matrix Variations

1. Zigzag Level Order Traversal

2. Diagonal Traverse

3. Image Compression Zigzag Scan

Recursive Approach

Recursive Java Example

Java Streams Approach

Example Stream Concept

Why Loops Are Preferred?

Comparison of All Approaches

Matrix Index Mapping

Row Zigzag

Column Zigzag

Primitive vs Object Arrays

Primitive Matrix

Object Matrix

Common Interview Mistakes

Mistake 1

Mistake 2

Mistake 3

Mistake 4

Edge Cases

Interview Follow-up Questions

Q1. Print matrix in zigzag order.

Q2. Print column-wise zigzag.

Q3. Print diagonal zigzag traversal.

Q4. Rotate matrix and traverse zigzag.

Q5. Find kth element in zigzag order.

Q6. Convert image matrix into zigzag sequence.

Related Problems

Key Takeaways