Diagonal Traverse

Diagonal Traverse looks strange the first time. You read the grid along slanted lines, not straight rows. And the direction keeps flipping, up then down then up. The interviewer wants to see if you can spot the pattern that controls those flips. Once you see it, the code is short and clean.

🎯 The Problem

You get a matrix, which is a grid of numbers with rows and columns. You read it in diagonal order.

The rules:

• A diagonal is a slanted line of cells where the row index plus the column index stays the same.
• Read the first diagonal, then the next, and so on.
• The direction flips every time. One diagonal goes up and to the right. The next goes down and to the left.
• Visit every cell exactly once.

Look at this grid. The first diagonal is just 1. The next holds 2 and 4, read upward as 2, 4. The next holds 3, 5, 7, read downward as 7, 5, 3. And so on.

Input:
1 2 3
4 5 6
7 8 9

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

Explanation: read each diagonal, flipping direction every time.

Here is the zigzag path. Notice how the arrows flip direction between diagonals.

🐢 Approach 1: Group Cells by Row Plus Column (Brute Force)

The idea:

• Every cell on one diagonal shares the same value of row + col.
• So bucket cells by that sum. Make a list of lists.
• Walk the whole grid. Put each cell into the bucket for its row + col.

How it works:

• Each bucket now holds one diagonal.
• The buckets are already in order, since the sum grows from 0 upward.
• For an even sum reverse the bucket. For an odd sum leave it. That gives the flip.
• Join all buckets into one list.

Why it is weak:

• It stores every cell in those buckets first.
• So the extra space is O(m × n).
• A tighter walk needs no buckets.

Here is the grouping code for that idea:

from collections import defaultdict


def find_diagonal_order(mat):
    groups = defaultdict(list)
    for r in range(len(mat)):
        for c in range(len(mat[0])):
            groups[r + c].append(mat[r][c])

    answer = []
    for key in range(len(mat) + len(mat[0]) - 1):
        values = groups[key]
        if key % 2 == 0:
            values.reverse()
        answer.extend(values)
    return answer

⚡ Approach 2: Walk With a Direction Toggle (Best)

The idea in one line: walk the cells directly in output order, flipping direction every time you step off an edge.

What we track:

• A row index, a column index, and a direction.
• The direction is either “going up-right” or “going down-left.”

How one step works:

• Read the current cell first, then move.
• Going up-right means row - 1 and col + 1.
• Going down-left means row + 1 and col - 1.
• When the move steps off the grid, fix the position and flip the direction.

How the turn works:

• Going up and off the top: move right if there is room, else move down.
• Going down and off the left: move down if there is room, else move right.
• That nudge lands you on the start of the next diagonal.

Why it is fast:

• It reads each cell exactly once.
• It stores nothing but the answer.
• So the extra space is O(1) beyond the output.

Steps to Solve

1. Start at row = 0, col = 0, with direction “up-right”.
2. Read the current cell into the result.
3. If going up-right, try row - 1, col + 1. If that steps off the grid, fix the position and flip the direction.
4. If going down-left, try row + 1, col - 1. If that steps off, fix the position and flip the direction.
5. To fix after going off the top or right, move right if you can, else move down. After going off the left or bottom, move down if you can, else move right.
6. Repeat until you have read every cell.

Here is the toggle flow for the first few cells.

#include <stdio.h>

#define R 3
#define C 3

void diagonal(int matrix[R][C]) {
    int total = R * C;
    int row = 0, col = 0, up = 1;
    printf("[");
    for (int k = 0; k < total; k++) {
        if (k) printf(", ");
        printf("%d", matrix[row][col]);
        if (up) {                          // going up-right
            if (col == C - 1) { row++; up = 0; }
            else if (row == 0) { col++; up = 0; }
            else { row--; col++; }
        } else {                           // going down-left
            if (row == R - 1) { col++; up = 1; }
            else if (col == 0) { row++; up = 1; }
            else { row++; col--; }
        }
    }
    printf("]\n");
}

int main(void) {
    int matrix[R][C] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    diagonal(matrix);
    return 0;
}

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

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

vector<int> diagonal(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    vector<int> result;
    int row = 0, col = 0;
    bool up = true;
    for (int k = 0; k < rows * cols; k++) {
        result.push_back(matrix[row][col]);
        if (up) {
            if (col == cols - 1) { row++; up = false; }
            else if (row == 0) { col++; up = false; }
            else { row--; col++; }
        } else {
            if (row == rows - 1) { col++; up = true; }
            else if (col == 0) { row++; up = true; }
            else { row++; col--; }
        }
    }
    return result;
}

int main() {
    vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    vector<int> result = diagonal(matrix);
    cout << "[";
    for (size_t i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i + 1 < result.size()) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}

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

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

public class Diagonal {
    public static List<Integer> diagonal(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        List<Integer> result = new ArrayList<>();
        int row = 0, col = 0;
        boolean up = true;
        for (int k = 0; k < rows * cols; k++) {
            result.add(matrix[row][col]);
            if (up) {
                if (col == cols - 1) { row++; up = false; }
                else if (row == 0) { col++; up = false; }
                else { row--; col++; }
            } else {
                if (row == rows - 1) { col++; up = true; }
                else if (col == 0) { row++; up = true; }
                else { row++; col--; }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        System.out.println(diagonal(matrix));
    }
}

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

def diagonal(matrix):
    rows = len(matrix)
    cols = len(matrix[0])
    result = []
    row, col, up = 0, 0, True
    for _ in range(rows * cols):
        result.append(matrix[row][col])     # read current cell
        if up:                              # moving up and to the right
            if col == cols - 1:
                row += 1
                up = False
            elif row == 0:
                col += 1
                up = False
            else:
                row -= 1
                col += 1
        else:                               # moving down and to the left
            if row == rows - 1:
                col += 1
                up = True
            elif col == 0:
                row += 1
                up = True
            else:
                row += 1
                col -= 1
    return result


matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(diagonal(matrix))

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

function diagonal(matrix) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const result = [];
  let row = 0;
  let col = 0;
  let up = true;
  for (let k = 0; k < rows * cols; k++) {
    result.push(matrix[row][col]);
    if (up) {
      if (col === cols - 1) { row++; up = false; }
      else if (row === 0) { col++; up = false; }
      else { row--; col++; }
    } else {
      if (row === rows - 1) { col++; up = true; }
      else if (col === 0) { row++; up = true; }
      else { row++; col--; }
    }
  }
  return result;
}

const matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
console.log(diagonal(matrix));

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

Let us read the Python version line by line, because the edge handling is the tricky part.

row, col, up = 0, 0, True starts us at the top left, moving up and to the right. We use up as the direction. True means up-right. False means down-left.

The loop runs rows * cols times, once per cell. result.append(matrix[row][col]) reads the current cell before we move. Reading first is important. We always record the cell we are standing on, then decide where to step.

Now the if up block, which handles the up-right direction. The order of its checks matters. We check col == cols - 1 first. That means we are at the right wall. From here we cannot go further right, so we drop down one row and flip to down-left. We check row == 0 second. That means we hit the top edge with room still to the right, so we step right and flip. Only if neither edge is hit do we make the normal up-right step: row -= 1 and col += 1.

The corner case is why col == cols - 1 comes first. At the very top-right cell both row == 0 and col == cols - 1 are true. Checking the column first sends us down, which is correct. Checking the row first would send us right, off the grid.

The else block mirrors all of this for the down-left direction. We check row == rows - 1 first, the bottom wall, then col == 0, the left wall, then the normal down-left step.

So the walk never stores a bucket. It just steps, reads, and toggles. That is the O(1) extra space win.

⏱️ Time and Space Complexity

Both approaches read each cell once, so the time is O(m × n). The bucket approach stores every cell in its diagonal lists first, so its extra space is O(m × n). The direction-toggle walk stores nothing but the answer, so its extra space is O(1) beyond the output.

🧩 Key Takeaways

• ✅ Cells on one diagonal share the same value of row plus column.
• ✅ The direction flips every diagonal: up-right, then down-left, and back.
• ✅ The optimal walk keeps a row, a column, and a direction flag, and reads cell by cell.
• ✅ At each edge, nudge back inside the grid, then flip the direction.
• ✅ Check the wall that limits movement first, so a corner does not send you off the grid.

🚀 What’s Next?

• Spiral Matrix
• Game of Life