Diagonal Traverse

Medium Arrays & Hashing Matrix Traversal Original on LeetCode

Diagonal Traverse is a medium arrays & hashing problem solved with the matrix traversal pattern. The best approach, optimal (direct simulation), runs in O(m · n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (group by diagonal, reverse alternate) up.

Problem

Given an m x n matrix mat, return all of its elements in zigzag diagonal order.

Start at the top-left cell. Read the first anti-diagonal (cells with the same i + j) moving up and to the right, the next one moving down and to the left, and keep alternating until the bottom-right cell has been read.

Examples

Example 1

Input
mat = [[1,2,3,4],[5,6,7,8]]
Output
[1,2,5,6,3,4,7,8]
Why
Diagonals are read as 1 (up), 2→5 (down), 6→3 (up), 4→7 (down), 8 (up).

Example 2

Input
mat = [[7],[8],[9]]
Output
[7,8,9]
Why
A single column: every diagonal holds one cell, so the order is just top to bottom.

Example 3

Input
mat = [[1,2],[3,4]]
Output
[1,2,3,4]
Why
1, then the anti-diagonal 2→3 going down, then 4.

Constraints

  • m == mat.length, n == mat[i].length
  • 1 <= m, n <= 10^4 and 1 <= m · n <= 10^4
  • -10^5 <= mat[i][j] <= 10^5

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (group by diagonal, reverse alternate)O(m · n)O(m · n)
Optimal (direct simulation)O(m · n)O(1)

1Brute force (group by diagonal, reverse alternate)

TimeO(m · n)Each cell is placed in a bucket once and copied out once.
SpaceO(m · n)The buckets hold a second copy of every value.

Bucket every cell by d = i + j, scanning rows top to bottom so each bucket is in top-to-bottom order. Then emit the buckets in order of d, reversing the even-indexed ones so they read upward.

  1. Create m + n - 1 lists; append mat[i][j] to list i + j while scanning row by row.
  2. For d from 0 to m + n - 2: if d is even, append the list reversed, otherwise append it as is.
class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        List<List<Integer>> buckets = new ArrayList<>();
        for (int d = 0; d < m + n - 1; d++) {
            buckets.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                buckets.get(i + j).add(mat[i][j]);
            }
        }
        int[] result = new int[m * n];
        int k = 0;
        for (int d = 0; d < m + n - 1; d++) {
            List<Integer> b = buckets.get(d);
            if (d % 2 == 0) {
                for (int t = b.size() - 1; t >= 0; t--) {
                    result[k++] = b.get(t);
                }
            } else {
                for (int x : b) {
                    result[k++] = x;
                }
            }
        }
        return result;
    }
}

2Optimal (direct simulation)

TimeO(m · n)Each cell is visited exactly once with O(1) work per step.
SpaceO(1)Only the position and direction are stored (output not counted).

Walk the matrix cell by cell with a direction flag. Going up, move to (i - 1, j + 1); going down, move to (i + 1, j - 1). When the next step would leave the matrix, slide along the border instead (right or down when going up, down or right when going down) and flip the direction. Checking the far border first handles the corners.

  1. i = j = 0, up = true; repeat m · n times: write mat[i][j].
  2. If up: if j == n - 1, go down a row (i++) and flip; else if i == 0, go right (j++) and flip; else i--, j++.
  3. If down: if i == m - 1, go right (j++) and flip; else if j == 0, go down (i++) and flip; else i++, j--.
class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[] result = new int[m * n];
        int i = 0, j = 0;
        boolean up = true;
        for (int k = 0; k < m * n; k++) {
            result[k] = mat[i][j];
            if (up) {
                if (j == n - 1) { i++; up = false; }
                else if (i == 0) { j++; up = false; }
                else { i--; j++; }
            } else {
                if (i == m - 1) { j++; up = true; }
                else if (j == 0) { i++; up = true; }
                else { i++; j--; }
            }
        }
        return result;
    }
}

Edge cases to test

  • A single cell
  • A single row or a single column
  • Wide matrices (n much larger than m) and tall ones (m much larger than n)
  • Turning at a corner, where both the row and the column hit a border at once

Hints

Hint 1

All cells on one anti-diagonal share the same i + j. There are m + n - 1 such diagonals.

Hint 2

Diagonals with an even index are read going up-right (row decreasing); odd ones going down-left.

Hint 3

You can also walk the matrix directly: move up-right until you fall off, then decide whether to step right or down, flip the direction, and continue.

FAQ

What is the best time complexity for Diagonal Traverse?

Optimal (direct simulation) runs in O(m · n) time and O(1) extra space. Each cell is visited exactly once with O(1) work per step.

Which pattern does Diagonal Traverse use?

It is a arrays & hashing problem that uses the matrix traversal pattern. Other problems with the same pattern: Spiral Matrix, Best Meeting Point, Sparse Matrix Multiplication.

Is there a brute force solution for Diagonal Traverse?

Yes. Brute force (group by diagonal, reverse alternate) takes O(m · n) time and O(m · n) space. Bucket every cell by d = i + j, scanning rows top to bottom so each bucket is in top-to-bottom order.

Which edge cases should I test for Diagonal Traverse?

A single cell; A single row or a single column; Wide matrices (n much larger than m) and tall ones (m much larger than n); Turning at a corner, where both the row and the column hit a border at once.