Sum of Elements in Zigzag Sequence of a Matrix

The zigzag sequence of a matrix scans each anti-diagonal in an alternating direction: even-indexed diagonals from the smallest row index to the largest, odd-indexed diagonals in reverse, visiting every element exactly once.

Because every element is visited once, the sum equals the total matrix sum. The value of this algorithm is in its traversal order, not in any special selection of elements. Placement tests that ask for the zigzag sum are checking whether you can implement the traversal correctly.

For comparison, finding the equilibrium index also scans an array in a single pass while maintaining a running sum. The diagonal scan here is the 2D generalisation of that pattern.

What Is the Zigzag Sequence of a Matrix?

Every element in a matrix sits on exactly one anti-diagonal, identified by the sum of its row and column indices. For a 3×3 matrix with elements 1 through 9:

Anti-diagonal d	Elements (row, col)	Values
0	(0,0)	1
1	(0,1), (1,0)	2, 4
2	(0,2), (1,1), (2,0)	3, 5, 7
3	(1,2), (2,1)	6, 8
4	(2,2)	9

For the zigzag pattern, even diagonals (d = 0, 2, 4, …) are read top-to-bottom (increasing row); odd diagonals (d = 1, 3, 5, …) are read bottom-to-top (decreasing row, i.e. the list is reversed).

Applying that rule to the 3×3 example gives:

• d = 0 (even, top-to-bottom): 1
• d = 1 (odd, bottom-to-top): 4, 2
• d = 2 (even): 3, 5, 7
• d = 3 (odd): 8, 6
• d = 4 (even): 9

Zigzag sequence: 1, 4, 2, 3, 5, 7, 8, 6, 9. Sum = 45, which equals 1+2+3+4+5+6+7+8+9.

An N×N matrix has 2N-1 anti-diagonals. For 3×3 that is 5; for 4×4 that is 7. For any M×N matrix the count is M+N-1.

How the Algorithm Works

The algorithm iterates over each diagonal d from 0 to M+N-2. For each diagonal it collects the elements in row order, then either keeps them as-is (even d) or reverses the list (odd d) before accumulating the sum.

The critical step is computing the valid row range for each diagonal. For diagonal d in an M×N matrix:

• r_start = max(0, d - N + 1) — the first row containing an element on diagonal d
• r_end = min(d, M - 1) — the last such row
• For any row r in that range, the column is c = d - r

Worked Example: 3×3 Matrix

Matrix:

1 2 3
4 5 6
7 8 9

• Step 1 — d = 0 (even): r_start = max(0, 0-3+1) = 0, r_end = min(0, 2) = 0. Row 0, col 0: element 1. Contribution: 1.
• Step 2 — d = 1 (odd): r_start = max(0, 1-3+1) = 0, r_end = min(1, 2) = 1. Rows 0–1 collect: (0,1)=2, (1,0)=4. Reversed: 4, 2. Contribution: 6.
• Step 3 — d = 2 (even): r_start = max(0, 2-3+1) = 0, r_end = min(2, 2) = 2. Rows 0–2 collect: (0,2)=3, (1,1)=5, (2,0)=7. As-is: 3, 5, 7. Contribution: 15.
• Step 4 — d = 3 (odd): r_start = max(0, 3-3+1) = 1, r_end = min(3, 2) = 2. Rows 1–2 collect: (1,2)=6, (2,1)=8. Reversed: 8, 6. Contribution: 14.
• Step 5 — d = 4 (even): r_start = max(0, 4-3+1) = 2, r_end = min(4, 2) = 2. Row 2, col 0: element 9. Contribution: 9.

Total: 1 + 6 + 15 + 14 + 9 = 45. Matches the direct matrix sum.

For a reference implementation using this same indexing formula, the GeeksforGeeks diagonal traversal walkthrough covers the C++ version in detail.

The most common mistake is forgetting the clamping. Without max(0, ...) the start row goes negative; without min(d, M-1) the end row exceeds the matrix boundary. Both cause index-out-of-range errors that are easy to miss in code that passes small test cases but crashes on rectangular inputs.

Code in Python, C++, and Java

Each implementation below returns the traversal sequence and its sum. The Python version is the clearest to read; the C++ and Java versions follow the same structure.

Python

def zigzag_sum(matrix):
    if not matrix or not matrix[0]:
        return [], 0
    M, N = len(matrix), len(matrix[0])
    sequence = []

    for d in range(M + N - 1):
        r_start = max(0, d - N + 1)
        r_end   = min(d, M - 1)
        diagonal = [matrix[r][d - r] for r in range(r_start, r_end + 1)]
        if d % 2 != 0:
            diagonal.reverse()
        sequence.extend(diagonal)

    return sequence, sum(sequence)

# Example
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
seq, total = zigzag_sum(matrix)
print("Sequence:", seq)   # [1, 4, 2, 3, 5, 7, 8, 6, 9]
print("Sum:", total)      # 45

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int zigzagSum(vector<vector<int>>& matrix) {
    int M = matrix.size(), N = matrix[0].size();
    int total = 0;

    for (int d = 0; d < M + N - 1; d++) {
        int rStart = max(0, d - N + 1);
        int rEnd   = min(d, M - 1);

        vector<int> diagonal;
        for (int r = rStart; r <= rEnd; r++)
            diagonal.push_back(matrix[r][d - r]);

        if (d % 2 != 0)
            reverse(diagonal.begin(), diagonal.end());

        for (int x : diagonal) total += x;
    }
    return total;
}

int main() {
    vector<vector<int>> matrix = {{1,2,3},{4,5,6},{7,8,9}};
    cout << "Sum: " << zigzagSum(matrix) << endl;  // 45
    return 0;
}

Java

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

public class ZigzagSum {
    public static int zigzagSum(int[][] matrix) {
        int M = matrix.length, N = matrix[0].length;
        int total = 0;

        for (int d = 0; d < M + N - 1; d++) {
            int rStart = Math.max(0, d - N + 1);
            int rEnd   = Math.min(d, M - 1);

            List<Integer> diagonal = new ArrayList<>();
            for (int r = rStart; r <= rEnd; r++)
                diagonal.add(matrix[r][d - r]);

            if (d % 2 != 0)
                Collections.reverse(diagonal);

            for (int x : diagonal) total += x;
        }
        return total;
    }

    public static void main(String[] args) {
        int[][] m = {{1,2,3},{4,5,6},{7,8,9}};
        System.out.println("Sum: " + zigzagSum(m));  // 45
    }
}

Complexity and Placement Context

Time complexity: O(M×N). The outer loop runs M+N-1 times (once per diagonal). Summed across all iterations, the inner loop processes each of the M×N elements exactly once.

Space complexity: O(min(M,N)) auxiliary. Each diagonal is buffered as a temporary list before the sum is accumulated. The longest diagonal in any M×N matrix contains at most min(M,N) elements. For the sum-only use case the buffer can be discarded and the accumulation done in a single pass with O(1) auxiliary space. See space complexity of algorithms with examples for how that O(1) optimisation is derived from the same first-principles argument.

Zigzag diagonal traversal appears in placement coding rounds at service-tier and mid-tier companies as a matrix variant of the standard scan-and-sum pattern. Interviewers look for the correct row-range clamping formula. Incorrect bounds (missing max or min) produce off-by-one errors that pass small square test cases and fail on rectangular ones.

If you have solved problems like finding symmetric pairs in an array and are moving to 2D patterns, this diagonal traversal is a natural step. The anti-diagonal index d = row + col is the 2D analogue of a single array index, and the direction-flip rule is the 2D analogue of alternating left-right scans.

The same anti-diagonal scan appears in the JPEG standard as the zigzag reordering of the 64 DCT coefficients in each 8×8 image block. Low-frequency coefficients cluster at the start of the zigzag sequence, high-frequency ones at the end, making the subsequent run-length encoding step more compact. The formula d = r + c that drives this code is exactly what JPEG encoders apply to 8×8 sub-matrices at every pixel block.

That same diagonal indexing formula appears when working with attention matrices and convolution kernels in neural network code. TinkerLLM’s hands-on matrix labs at ₹299 start from this exact r + c == d identity and build up to the 2D array operations that image-processing layers use internally, making it a practical next step after verifying this algorithm on paper.