⌘K

Introduction to Matrices

EditorialUpdated Nov 9, 2026

The same cells, many times slower

Spiral Matrix, Rotate Image, Valid Sudoku: matrix problems are loops over rows and columns, and which loop goes inside looks like a matter of taste. Here are the same 9 million cells, a 3,000 × 3,000 grid, added up row by row and then column by column, in every language the judge runs:

import time

n = 3000
grid = [[(r * 7 + c) % 10 for c in range(n)] for r in range(n)]

start = time.perf_counter()
total = 0
for r in range(n):                    # row by row: each row's cells one after another
    for c in range(n):
        total += grid[r][c]
print(f"by rows:    {total} in {(time.perf_counter() - start) * 1000:.0f} ms")

start = time.perf_counter()
total = 0
for c in range(n):                    # column by column: one cell from every row in turn
    for r in range(n):
        total += grid[r][c]
print(f"by columns: {total} in {(time.perf_counter() - start) * 1000:.0f} ms")

# by rows:    40500000 in 1181 ms
# by columns: 40500000 in 1337 ms

public class Main {
    public static void main(String[] args) {
        int n = 3000;
        int[][] grid = new int[n][n];
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++)
                grid[r][c] = (r * 7 + c) % 10;

        long start = System.nanoTime();
        long total = 0;
        for (int r = 0; r < n; r++)       // row by row: each row's cells one after another
            for (int c = 0; c < n; c++)
                total += grid[r][c];
        System.out.printf("by rows:    %d in %d ms%n", total, (System.nanoTime() - start) / 1000000);

        start = System.nanoTime();
        total = 0;
        for (int c = 0; c < n; c++)       // column by column: one cell from every row in turn
            for (int r = 0; r < n; r++)
                total += grid[r][c];
        System.out.printf("by columns: %d in %d ms%n", total, (System.nanoTime() - start) / 1000000);
    }
}

// by rows:    40500000 in 13 ms
// by columns: 40500000 in 119 ms

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 3000;
    vector<vector<int>> grid(n, vector<int>(n));
    for (int r = 0; r < n; r++)
        for (int c = 0; c < n; c++)
            grid[r][c] = (r * 7 + c) % 10;
    auto ms = [](auto start) {
        return (long long) chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
    };

    auto start = chrono::steady_clock::now();
    long long total = 0;
    for (int r = 0; r < n; r++)           // row by row: each row's cells one after another
        for (int c = 0; c < n; c++)
            total += grid[r][c];
    printf("by rows:    %lld in %lld ms\n", total, ms(start));

    start = chrono::steady_clock::now();
    total = 0;
    for (int c = 0; c < n; c++)           // column by column: one cell from every row in turn
        for (int r = 0; r < n; r++)
            total += grid[r][c];
    printf("by columns: %lld in %lld ms\n", total, ms(start));
}

// by rows:    40500000 in 4 ms
// by columns: 40500000 in 69 ms

const n = 3000;
const grid = Array.from({ length: n }, (_, r) => Array.from({ length: n }, (_, c) => (r * 7 + c) % 10));

let start = performance.now();
let total = 0;
for (let r = 0; r < n; r++)           // row by row: each row's cells one after another
    for (let c = 0; c < n; c++)
        total += grid[r][c];
console.log(`by rows:    ${total} in ${Math.round(performance.now() - start)} ms`);

start = performance.now();
total = 0;
for (let c = 0; c < n; c++)           // column by column: one cell from every row in turn
    for (let r = 0; r < n; r++)
        total += grid[r][c];
console.log(`by columns: ${total} in ${Math.round(performance.now() - start)} ms`);

// by rows:    40500000 in 15 ms
// by columns: 40500000 in 129 ms

const n: number = 3000;
const grid: number[][] = Array.from({ length: n }, (_, r) => Array.from({ length: n }, (_, c) => (r * 7 + c) % 10));

let start: number = performance.now();
let total: number = 0;
for (let r = 0; r < n; r++)           // row by row: each row's cells one after another
    for (let c = 0; c < n; c++)
        total += grid[r][c];
console.log(`by rows:    ${total} in ${Math.round(performance.now() - start)} ms`);

start = performance.now();
total = 0;
for (let c = 0; c < n; c++)           // column by column: one cell from every row in turn
    for (let r = 0; r < n; r++)
        total += grid[r][c];
console.log(`by columns: ${total} in ${Math.round(performance.now() - start)} ms`);

// by rows:    40500000 in 15 ms
// by columns: 40500000 in 129 ms

using System;
using System.Diagnostics;

class Program {
    static void Main() {
        int n = 3000;
        int[][] grid = new int[n][];
        for (int r = 0; r < n; r++) {
            grid[r] = new int[n];
            for (int c = 0; c < n; c++) grid[r][c] = (r * 7 + c) % 10;
        }

        var watch = Stopwatch.StartNew();
        long total = 0;
        for (int r = 0; r < n; r++)       // row by row: each row's cells one after another
            for (int c = 0; c < n; c++)
                total += grid[r][c];
        Console.WriteLine($"by rows:    {total} in {watch.ElapsedMilliseconds} ms");

        watch.Restart();
        total = 0;
        for (int c = 0; c < n; c++)       // column by column: one cell from every row in turn
            for (int r = 0; r < n; r++)
                total += grid[r][c];
        Console.WriteLine($"by columns: {total} in {watch.ElapsedMilliseconds} ms");
    }
}

// by rows:    40500000 in 6 ms
// by columns: 40500000 in 118 ms

package main

import (
	"fmt"
	"time"
)

func main() {
	n := 3000
	grid := make([][]int, n)
	for r := range grid {
		grid[r] = make([]int, n)
		for c := range grid[r] {
			grid[r][c] = (r*7 + c) % 10
		}
	}

	start := time.Now()
	total := 0
	for r := 0; r < n; r++ { // row by row: each row's cells one after another
		for c := 0; c < n; c++ {
			total += grid[r][c]
		}
	}
	fmt.Printf("by rows:    %d in %d ms\n", total, time.Since(start).Milliseconds())

	start = time.Now()
	total = 0
	for c := 0; c < n; c++ { // column by column: one cell from every row in turn
		for r := 0; r < n; r++ {
			total += grid[r][c]
		}
	}
	fmt.Printf("by columns: %d in %d ms\n", total, time.Since(start).Milliseconds())
}

// by rows:    40500000 in 9 ms
// by columns: 40500000 in 84 ms

Both orders found 40,500,000 in all seven. Column by column took 9 to 20 times as long in Java, C++, JavaScript, TypeScript, C# and Go: 4 ms against 69 ms in C++, 13 ms against 119 ms in Java, 6 ms against 118 ms in C#. In Python it was 1.1 times, 1,181 ms against 1,337 ms: Python's own work for each cell costs far more than reaching it.

Each row sits in memory in one piece, its values side by side, and memory reaches the processor in small blocks of neighbouring values, a cache line at a time. Row by row uses every value in each block it brings in. Column by column brings in a block for one value, then leaves for the next row, somewhere else in memory. So put the loop over the columns inside the loop over the rows. This lesson is about how a matrix is laid out, how to move around it without falling off, and the walks most matrix problems are built from.

A 3 × 4 grid of cells numbered 0 to 11, and under it the same cells in memory: each row one run of cells, row 0, row 1 and row 2 apart from each other. Left, ticked, by rows: an arrow runs along each row's run, one cell after the next. Right, crossed, by columns: the walk hops from 0 to 4 to 8, a different row each time, then back to 1. Focal line: each row sits in one piece, so walk along the rows. Title: rows beat columns.

Rows, columns and one index

A matrix with m rows and n columns, m × n, names each cell by its row r and column c, both counted from 0. In code it's a list of rows, so grid[r][c] is row r first, then column c; m is the number of rows and n the length of each row. They're only equal when the matrix is square.

Numbered row after row, cell (r, c) is number r × n + c, and division takes the number back: row i / n, column i % n. The same arithmetic finds a 9 × 9 Sudoku's 3 × 3 box, numbered 0 to 8 by rows, (r / 3) * 3 + c / 3, dividing whole numbers (// in Python):

rows, cols = 3, 4
grid = [[r * cols + c for c in range(cols)] for r in range(rows)]   # each cell holds its index, r * cols + c
for row in grid:
    print(*row)
i = 7
print(f"index {i} is row {i // cols}, column {i % cols}")         # and back
for r, c in ((4, 7), (8, 0)):                                       # a 9 x 9 Sudoku's boxes, 0 to 8
    print(f"({r}, {c}) is in box {(r // 3) * 3 + c // 3}")

# 0 1 2 3
# 4 5 6 7
# 8 9 10 11
# index 7 is row 1, column 3
# (4, 7) is in box 5
# (8, 0) is in box 6

public class Main {
    public static void main(String[] args) {
        int rows = 3, cols = 4;
        int[][] grid = new int[rows][cols];
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                grid[r][c] = r * cols + c;        // each cell holds its index, r * cols + c
        for (int[] row : grid) {
            StringBuilder line = new StringBuilder();
            for (int v : row) line.append(line.length() == 0 ? "" : " ").append(v);
            System.out.println(line);
        }
        int i = 7;
        System.out.println("index " + i + " is row " + i / cols + ", column " + i % cols);   // and back
        for (int[] cell : new int[][] {{4, 7}, {8, 0}})   // a 9 x 9 Sudoku's boxes, 0 to 8
            System.out.println("(" + cell[0] + ", " + cell[1] + ") is in box " + ((cell[0] / 3) * 3 + cell[1] / 3));
    }
}

// 0 1 2 3
// 4 5 6 7
// 8 9 10 11
// index 7 is row 1, column 3
// (4, 7) is in box 5
// (8, 0) is in box 6

#include <bits/stdc++.h>
using namespace std;

int main() {
    int rows = 3, cols = 4;
    vector<vector<int>> grid(rows, vector<int>(cols));
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            grid[r][c] = r * cols + c;            // each cell holds its index, r * cols + c
    for (auto& row : grid) {
        for (int c = 0; c < cols; c++) cout << (c ? " " : "") << row[c];
        cout << "\n";
    }
    int i = 7;
    cout << "index " << i << " is row " << i / cols << ", column " << i % cols << "\n";   // and back
    for (auto [r, c] : vector<pair<int, int>>{{4, 7}, {8, 0}})   // a 9 x 9 Sudoku's boxes, 0 to 8
        cout << "(" << r << ", " << c << ") is in box " << (r / 3) * 3 + c / 3 << "\n";
}

// 0 1 2 3
// 4 5 6 7
// 8 9 10 11
// index 7 is row 1, column 3
// (4, 7) is in box 5
// (8, 0) is in box 6

const rows = 3, cols = 4;
const grid = Array.from({ length: rows }, (_, r) =>
    Array.from({ length: cols }, (_, c) => r * cols + c));    // each cell holds its index, r * cols + c
for (const row of grid) console.log(row.join(" "));
const i = 7;
console.log(`index ${i} is row ${Math.floor(i / cols)}, column ${i % cols}`);   // and back
for (const [r, c] of [[4, 7], [8, 0]])          // a 9 x 9 Sudoku's boxes, 0 to 8
    console.log(`(${r}, ${c}) is in box ${Math.floor(r / 3) * 3 + Math.floor(c / 3)}`);

// 0 1 2 3
// 4 5 6 7
// 8 9 10 11
// index 7 is row 1, column 3
// (4, 7) is in box 5
// (8, 0) is in box 6

const rows: number = 3, cols: number = 4;
const grid: number[][] = Array.from({ length: rows }, (_, r) =>
    Array.from({ length: cols }, (_, c) => r * cols + c));    // each cell holds its index, r * cols + c
for (const row of grid) console.log(row.join(" "));
const i: number = 7;
console.log(`index ${i} is row ${Math.floor(i / cols)}, column ${i % cols}`);   // and back
for (const [r, c] of [[4, 7], [8, 0]])          // a 9 x 9 Sudoku's boxes, 0 to 8
    console.log(`(${r}, ${c}) is in box ${Math.floor(r / 3) * 3 + Math.floor(c / 3)}`);

// 0 1 2 3
// 4 5 6 7
// 8 9 10 11
// index 7 is row 1, column 3
// (4, 7) is in box 5
// (8, 0) is in box 6

using System;

class Program {
    static void Main() {
        int rows = 3, cols = 4;
        int[][] grid = new int[rows][];
        for (int r = 0; r < rows; r++) {
            grid[r] = new int[cols];
            for (int c = 0; c < cols; c++) grid[r][c] = r * cols + c;   // each cell holds its index
        }
        foreach (int[] row in grid) Console.WriteLine(string.Join(" ", row));
        int i = 7;
        Console.WriteLine($"index {i} is row {i / cols}, column {i % cols}");   // and back
        foreach (var (r, c) in new[] { (4, 7), (8, 0) })   // a 9 x 9 Sudoku's boxes, 0 to 8
            Console.WriteLine($"({r}, {c}) is in box {(r / 3) * 3 + c / 3}");
    }
}

// 0 1 2 3
// 4 5 6 7
// 8 9 10 11
// index 7 is row 1, column 3
// (4, 7) is in box 5
// (8, 0) is in box 6

package main

import (
	"fmt"
	"strings"
)

func main() {
	rows, cols := 3, 4
	grid := make([][]int, rows)
	for r := range grid {
		grid[r] = make([]int, cols)
		for c := range grid[r] {
			grid[r][c] = r*cols + c // each cell holds its index, r * cols + c
		}
	}
	for _, row := range grid {
		fmt.Println(strings.Trim(fmt.Sprint(row), "[]"))
	}
	i := 7
	fmt.Printf("index %d is row %d, column %d\n", i, i/cols, i%cols) // and back
	for _, cell := range [][2]int{{4, 7}, {8, 0}} { // a 9 x 9 Sudoku's boxes, 0 to 8
		r, c := cell[0], cell[1]
		fmt.Printf("(%d, %d) is in box %d\n", r, c, (r/3)*3+c/3)
	}
}

// 0 1 2 3
// 4 5 6 7
// 8 9 10 11
// index 7 is row 1, column 3
// (4, 7) is in box 5
// (8, 0) is in box 6

A 3 × 4 grid with each cell's row and column, and under it the strip of indexes 0 to 11, one row after another. Cell (1, 2) and index 6 are joined: 1 × 4 + 2 = 6 one way, 6 ÷ 4 = 1 remainder 2 the other. Focal line: index = r × cols + c, and back with ÷ and %. Title: one index, two coordinates.

Search a 2D Matrix uses that index to binary search a whole sorted matrix as one array (Binary Search on Two Sorted Arrays and Matrices), and Valid Sudoku files every cell under its row, its column and its box.

Neighbours without falling off

Most grid problems look at the cells around one cell: up, down, left and right, or all eight with the corners. A list of row and column steps keeps that to one loop, and a bounds check keeps it inside the grid, since a cell on the edge has fewer neighbours. Counting the live neighbours of every cell, as Game of Life has to:

grid = [[0, 1, 0, 0],
        [1, 1, 0, 1],
        [0, 1, 1, 0]]
rows, cols = len(grid), len(grid[0])
DIRS = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]   # the eight around a cell


def live_neighbours(r, c):
    count = 0
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:      # inside the grid: a corner has 3 neighbours, an edge 5
            count += grid[nr][nc]
    return count


for r in range(rows):
    print(*(live_neighbours(r, c) for c in range(cols)))

# 3 2 3 1
# 3 4 5 1
# 3 3 3 2

public class Main {
    static int[][] grid = {{0, 1, 0, 0}, {1, 1, 0, 1}, {0, 1, 1, 0}};
    static int rows = grid.length, cols = grid[0].length;
    static int[][] DIRS = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};   // the eight

    static int liveNeighbours(int r, int c) {
        int count = 0;
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols)   // inside: a corner has 3 neighbours, an edge 5
                count += grid[nr][nc];
        }
        return count;
    }

    public static void main(String[] args) {
        for (int r = 0; r < rows; r++) {
            StringBuilder line = new StringBuilder();
            for (int c = 0; c < cols; c++) line.append(c == 0 ? "" : " ").append(liveNeighbours(r, c));
            System.out.println(line);
        }
    }
}

// 3 2 3 1
// 3 4 5 1
// 3 3 3 2

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> grid = {{0, 1, 0, 0}, {1, 1, 0, 1}, {0, 1, 1, 0}};
int rows = grid.size(), cols = grid[0].size();
int DIRS[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};   // the eight

int liveNeighbours(int r, int c) {
    int count = 0;
    for (auto& d : DIRS) {
        int nr = r + d[0], nc = c + d[1];
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols)   // inside: a corner has 3 neighbours, an edge 5
            count += grid[nr][nc];
    }
    return count;
}

int main() {
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) cout << (c ? " " : "") << liveNeighbours(r, c);
        cout << "\n";
    }
}

// 3 2 3 1
// 3 4 5 1
// 3 3 3 2

const grid = [[0, 1, 0, 0],
              [1, 1, 0, 1],
              [0, 1, 1, 0]];
const rows = grid.length, cols = grid[0].length;
const DIRS = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];   // the eight

function liveNeighbours(r, c) {
    let count = 0;
    for (const [dr, dc] of DIRS) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols)   // inside: a corner has 3 neighbours, an edge 5
            count += grid[nr][nc];
    }
    return count;
}

for (let r = 0; r < rows; r++)
    console.log(Array.from({ length: cols }, (_, c) => liveNeighbours(r, c)).join(" "));

// 3 2 3 1
// 3 4 5 1
// 3 3 3 2

const grid: number[][] = [[0, 1, 0, 0],
                          [1, 1, 0, 1],
                          [0, 1, 1, 0]];
const rows: number = grid.length, cols: number = grid[0].length;
const DIRS: [number, number][] = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]];

function liveNeighbours(r: number, c: number): number {
    let count = 0;
    for (const [dr, dc] of DIRS) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols)   // inside: a corner has 3 neighbours, an edge 5
            count += grid[nr][nc];
    }
    return count;
}

for (let r = 0; r < rows; r++)
    console.log(Array.from({ length: cols }, (_, c) => liveNeighbours(r, c)).join(" "));

// 3 2 3 1
// 3 4 5 1
// 3 3 3 2

using System;
using System.Linq;

class Program {
    static int[][] grid = { new[] {0, 1, 0, 0}, new[] {1, 1, 0, 1}, new[] {0, 1, 1, 0} };
    static int rows = grid.Length, cols = grid[0].Length;
    static (int, int)[] DIRS = { (-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1) };

    static int LiveNeighbours(int r, int c) {
        int count = 0;
        foreach (var (dr, dc) in DIRS) {
            int nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols)   // inside: a corner has 3 neighbours, an edge 5
                count += grid[nr][nc];
        }
        return count;
    }

    static void Main() {
        for (int r = 0; r < rows; r++)
            Console.WriteLine(string.Join(" ", Enumerable.Range(0, cols).Select(c => LiveNeighbours(r, c))));
    }
}

// 3 2 3 1
// 3 4 5 1
// 3 3 3 2

package main

import "fmt"

var grid = [][]int{{0, 1, 0, 0}, {1, 1, 0, 1}, {0, 1, 1, 0}}
var rows, cols = len(grid), len(grid[0])
var dirs = [][2]int{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}} // the eight

func liveNeighbours(r, c int) int {
	count := 0
	for _, d := range dirs {
		nr, nc := r+d[0], c+d[1]
		if nr >= 0 && nr < rows && nc >= 0 && nc < cols { // inside: a corner has 3 neighbours, an edge 5
			count += grid[nr][nc]
		}
	}
	return count
}

func main() {
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if c > 0 {
				fmt.Print(" ")
			}
			fmt.Print(liveNeighbours(r, c))
		}
		fmt.Println()
	}
}

// 3 2 3 1
// 3 4 5 1
// 3 3 3 2

The corner (0, 0) counts its 3 neighbours, (0, 1), (1, 0) and (1, 1), and finds 3 live ones; the middle cell (1, 2) has all 8, and 5 of them are live. Leave the bounds check out and the languages disagree, two of them silently: that's in Mistakes that cost an interview.

Walking a matrix

Row by row and column by column are two walks. The diagonals are two more: going down and to the right, r and c grow together, so r − c stays the same; going down and to the left, r grows as c shrinks, so r + c stays the same, and those are called the anti-diagonals. Grouping the cells of a 3 × 4 grid by r + c, then reading every other group backwards:

rows, cols = 3, 4
grid = [[r * cols + c for c in range(cols)] for r in range(rows)]
print("r - c = 0:", *(grid[r][r] for r in range(min(rows, cols))))     # down and to the right
order = []
for d in range(rows + cols - 1):                    # every cell with r + c == d, from the top row down
    cells = [grid[r][d - r] for r in range(rows) if 0 <= d - r < cols]
    print(f"r + c = {d}:", *cells)
    order += cells[::-1] if d % 2 == 0 else cells    # Diagonal Traverse: every other one read upwards
print("zigzag:", *order)

# r - c = 0: 0 5 10
# r + c = 0: 0
# r + c = 1: 1 4
# r + c = 2: 2 5 8
# r + c = 3: 3 6 9
# r + c = 4: 7 10
# r + c = 5: 11
# zigzag: 0 1 4 8 5 2 3 6 9 10 7 11

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int rows = 3, cols = 4;
        int[][] grid = new int[rows][cols];
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++) grid[r][c] = r * cols + c;
        StringBuilder main = new StringBuilder("r - c = 0:");   // down and to the right
        for (int r = 0; r < Math.min(rows, cols); r++) main.append(" ").append(grid[r][r]);
        System.out.println(main);
        List<Integer> order = new ArrayList<>();
        for (int d = 0; d < rows + cols - 1; d++) {   // every cell with r + c == d, from the top row down
            List<Integer> cells = new ArrayList<>();
            for (int r = 0; r < rows; r++)
                if (d - r >= 0 && d - r < cols) cells.add(grid[r][d - r]);
            StringBuilder line = new StringBuilder("r + c = " + d + ":");
            for (int v : cells) line.append(" ").append(v);
            System.out.println(line);
            if (d % 2 == 0) Collections.reverse(cells);   // Diagonal Traverse: every other one read upwards
            order.addAll(cells);
        }
        StringBuilder zigzag = new StringBuilder("zigzag:");
        for (int v : order) zigzag.append(" ").append(v);
        System.out.println(zigzag);
    }
}

// r - c = 0: 0 5 10
// r + c = 0: 0
// r + c = 1: 1 4
// r + c = 2: 2 5 8
// r + c = 3: 3 6 9
// r + c = 4: 7 10
// r + c = 5: 11
// zigzag: 0 1 4 8 5 2 3 6 9 10 7 11

#include <bits/stdc++.h>
using namespace std;

int main() {
    int rows = 3, cols = 4;
    vector<vector<int>> grid(rows, vector<int>(cols));
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++) grid[r][c] = r * cols + c;
    cout << "r - c = 0:";                         // down and to the right
    for (int r = 0; r < min(rows, cols); r++) cout << " " << grid[r][r];
    cout << "\n";
    vector<int> order;
    for (int d = 0; d < rows + cols - 1; d++) {   // every cell with r + c == d, from the top row down
        vector<int> cells;
        for (int r = 0; r < rows; r++)
            if (d - r >= 0 && d - r < cols) cells.push_back(grid[r][d - r]);
        cout << "r + c = " << d << ":";
        for (int v : cells) cout << " " << v;
        cout << "\n";
        if (d % 2 == 0) reverse(cells.begin(), cells.end());   // Diagonal Traverse: every other one upwards
        order.insert(order.end(), cells.begin(), cells.end());
    }
    cout << "zigzag:";
    for (int v : order) cout << " " << v;
    cout << "\n";
}

// r - c = 0: 0 5 10
// r + c = 0: 0
// r + c = 1: 1 4
// r + c = 2: 2 5 8
// r + c = 3: 3 6 9
// r + c = 4: 7 10
// r + c = 5: 11
// zigzag: 0 1 4 8 5 2 3 6 9 10 7 11

const rows = 3, cols = 4;
const grid = Array.from({ length: rows }, (_, r) => Array.from({ length: cols }, (_, c) => r * cols + c));
const main = [];
for (let r = 0; r < Math.min(rows, cols); r++) main.push(grid[r][r]);   // down and to the right
console.log("r - c = 0:", main.join(" "));
const order = [];
for (let d = 0; d < rows + cols - 1; d++) {     // every cell with r + c == d, from the top row down
    const cells = [];
    for (let r = 0; r < rows; r++)
        if (d - r >= 0 && d - r < cols) cells.push(grid[r][d - r]);
    console.log(`r + c = ${d}:`, cells.join(" "));
    order.push(...(d % 2 === 0 ? cells.reverse() : cells));   // Diagonal Traverse: every other one upwards
}
console.log("zigzag:", order.join(" "));

// r - c = 0: 0 5 10
// r + c = 0: 0
// r + c = 1: 1 4
// r + c = 2: 2 5 8
// r + c = 3: 3 6 9
// r + c = 4: 7 10
// r + c = 5: 11
// zigzag: 0 1 4 8 5 2 3 6 9 10 7 11

const rows: number = 3, cols: number = 4;
const grid: number[][] = Array.from({ length: rows }, (_, r) => Array.from({ length: cols }, (_, c) => r * cols + c));
const main: number[] = [];
for (let r = 0; r < Math.min(rows, cols); r++) main.push(grid[r][r]);   // down and to the right
console.log("r - c = 0:", main.join(" "));
const order: number[] = [];
for (let d = 0; d < rows + cols - 1; d++) {     // every cell with r + c == d, from the top row down
    const cells: number[] = [];
    for (let r = 0; r < rows; r++)
        if (d - r >= 0 && d - r < cols) cells.push(grid[r][d - r]);
    console.log(`r + c = ${d}:`, cells.join(" "));
    order.push(...(d % 2 === 0 ? cells.reverse() : cells));   // Diagonal Traverse: every other one upwards
}
console.log("zigzag:", order.join(" "));

// r - c = 0: 0 5 10
// r + c = 0: 0
// r + c = 1: 1 4
// r + c = 2: 2 5 8
// r + c = 3: 3 6 9
// r + c = 4: 7 10
// r + c = 5: 11
// zigzag: 0 1 4 8 5 2 3 6 9 10 7 11

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int rows = 3, cols = 4;
        int[][] grid = new int[rows][];
        for (int r = 0; r < rows; r++) {
            grid[r] = new int[cols];
            for (int c = 0; c < cols; c++) grid[r][c] = r * cols + c;
        }
        var main = new List<int>();
        for (int r = 0; r < Math.Min(rows, cols); r++) main.Add(grid[r][r]);   // down and to the right
        Console.WriteLine("r - c = 0: " + string.Join(" ", main));
        var order = new List<int>();
        for (int d = 0; d < rows + cols - 1; d++) {   // every cell with r + c == d, from the top row down
            var cells = new List<int>();
            for (int r = 0; r < rows; r++)
                if (d - r >= 0 && d - r < cols) cells.Add(grid[r][d - r]);
            Console.WriteLine($"r + c = {d}: " + string.Join(" ", cells));
            if (d % 2 == 0) cells.Reverse();         // Diagonal Traverse: every other one read upwards
            order.AddRange(cells);
        }
        Console.WriteLine("zigzag: " + string.Join(" ", order));
    }
}

// r - c = 0: 0 5 10
// r + c = 0: 0
// r + c = 1: 1 4
// r + c = 2: 2 5 8
// r + c = 3: 3 6 9
// r + c = 4: 7 10
// r + c = 5: 11
// zigzag: 0 1 4 8 5 2 3 6 9 10 7 11

package main

import (
	"fmt"
	"strings"
)

func line(label string, values []int) string {
	return strings.TrimSpace(label + " " + strings.Trim(fmt.Sprint(values), "[]"))
}

func main() {
	rows, cols := 3, 4
	grid := make([][]int, rows)
	for r := range grid {
		grid[r] = make([]int, cols)
		for c := range grid[r] {
			grid[r][c] = r*cols + c
		}
	}
	var mainDiagonal []int
	for r := 0; r < min(rows, cols); r++ { // down and to the right
		mainDiagonal = append(mainDiagonal, grid[r][r])
	}
	fmt.Println(line("r - c = 0:", mainDiagonal))
	var order []int
	for d := 0; d < rows+cols-1; d++ { // every cell with r + c == d, from the top row down
		var cells []int
		for r := 0; r < rows; r++ {
			if d-r >= 0 && d-r < cols {
				cells = append(cells, grid[r][d-r])
			}
		}
		fmt.Println(line(fmt.Sprintf("r + c = %d:", d), cells))
		if d%2 == 0 { // Diagonal Traverse: every other one read upwards
			for i, j := 0, len(cells)-1; i < j; i, j = i+1, j-1 {
				cells[i], cells[j] = cells[j], cells[i]
			}
		}
		order = append(order, cells...)
	}
	fmt.Println(line("zigzag:", order))
}

// r - c = 0: 0 5 10
// r + c = 0: 0
// r + c = 1: 1 4
// r + c = 2: 2 5 8
// r + c = 3: 3 6 9
// r + c = 4: 7 10
// r + c = 5: 11
// zigzag: 0 1 4 8 5 2 3 6 9 10 7 11

The cells hold their own index, so the zigzag line, 0 1 4 8 5 2 3 6 9 10 7 11, is Diagonal Traverse's order: after 0, the next anti-diagonal goes down, 1 then 4, and the one after it up, 8, 5 then 2. A matrix with m rows and n columns has m + n − 1 of them, r + c from 0 to m + n − 2.

The spiral

Spiral Matrix reads the outer ring clockwise, then the next ring in, and so on. Keep four boundaries, the top and bottom rows and the left and right columns not yet read. Read along the top row and move top down; read down the right column and move right in; then the bottom row backwards and the left column upwards, moving those two in. The cells still unread are always exactly the rectangle between the four boundaries, so the loop ends when it's empty. Two guards matter: after the first two passes, the rectangle may be a single row or a single column, and reading it backwards would read it twice:

def spiral(grid):
    out = []
    top, bottom, left, right = 0, len(grid) - 1, 0, len(grid[0]) - 1
    while top <= bottom and left <= right:            # unread: rows top..bottom, columns left..right
        for c in range(left, right + 1):              # along the top row
            out.append(grid[top][c])
        top += 1
        for r in range(top, bottom + 1):              # down the right column
            out.append(grid[r][right])
        right -= 1
        if top <= bottom:                             # a row is left to read backwards
            for c in range(right, left - 1, -1):      # along the bottom row, backwards
                out.append(grid[bottom][c])
            bottom -= 1
        if left <= right:                             # a column is left to read upwards
            for r in range(bottom, top - 1, -1):      # up the left column
                out.append(grid[r][left])
            left += 1
    return out


for grid in ([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]], [[1, 2, 3]], [[1], [2], [3]]):
    print(*spiral(grid))

# 1 2 3 4 8 12 11 10 9 5 6 7
# 1 2 3
# 1 2 3

import java.util.*;

public class Main {
    static List<Integer> spiral(int[][] grid) {
        List<Integer> out = new ArrayList<>();
        int top = 0, bottom = grid.length - 1, left = 0, right = grid[0].length - 1;
        while (top <= bottom && left <= right) {  // unread: rows top..bottom, columns left..right
            for (int c = left; c <= right; c++) out.add(grid[top][c]);      // along the top row
            top++;
            for (int r = top; r <= bottom; r++) out.add(grid[r][right]);    // down the right column
            right--;
            if (top <= bottom) {                  // a row is left to read backwards
                for (int c = right; c >= left; c--) out.add(grid[bottom][c]);
                bottom--;
            }
            if (left <= right) {                  // a column is left to read upwards
                for (int r = bottom; r >= top; r--) out.add(grid[r][left]);
                left++;
            }
        }
        return out;
    }

    public static void main(String[] args) {
        int[][][] grids = {{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}, {{1, 2, 3}}, {{1}, {2}, {3}}};
        for (int[][] grid : grids) {
            StringBuilder line = new StringBuilder();
            for (int v : spiral(grid)) line.append(line.length() == 0 ? "" : " ").append(v);
            System.out.println(line);
        }
    }
}

// 1 2 3 4 8 12 11 10 9 5 6 7
// 1 2 3
// 1 2 3

#include <bits/stdc++.h>
using namespace std;

vector<int> spiral(const vector<vector<int>>& grid) {
    vector<int> out;
    int top = 0, bottom = grid.size() - 1, left = 0, right = grid[0].size() - 1;
    while (top <= bottom && left <= right) {      // unread: rows top..bottom, columns left..right
        for (int c = left; c <= right; c++) out.push_back(grid[top][c]);      // along the top row
        top++;
        for (int r = top; r <= bottom; r++) out.push_back(grid[r][right]);    // down the right column
        right--;
        if (top <= bottom) {                      // a row is left to read backwards
            for (int c = right; c >= left; c--) out.push_back(grid[bottom][c]);
            bottom--;
        }
        if (left <= right) {                      // a column is left to read upwards
            for (int r = bottom; r >= top; r--) out.push_back(grid[r][left]);
            left++;
        }
    }
    return out;
}

int main() {
    vector<vector<vector<int>>> grids = {{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}, {{1, 2, 3}}, {{1}, {2}, {3}}};
    for (auto& grid : grids) {
        vector<int> out = spiral(grid);
        for (size_t i = 0; i < out.size(); i++) cout << (i ? " " : "") << out[i];
        cout << "\n";
    }
}

// 1 2 3 4 8 12 11 10 9 5 6 7
// 1 2 3
// 1 2 3

function spiral(grid) {
    const out = [];
    let top = 0, bottom = grid.length - 1, left = 0, right = grid[0].length - 1;
    while (top <= bottom && left <= right) {    // unread: rows top..bottom, columns left..right
        for (let c = left; c <= right; c++) out.push(grid[top][c]);      // along the top row
        top++;
        for (let r = top; r <= bottom; r++) out.push(grid[r][right]);    // down the right column
        right--;
        if (top <= bottom) {                    // a row is left to read backwards
            for (let c = right; c >= left; c--) out.push(grid[bottom][c]);
            bottom--;
        }
        if (left <= right) {                    // a column is left to read upwards
            for (let r = bottom; r >= top; r--) out.push(grid[r][left]);
            left++;
        }
    }
    return out;
}

for (const grid of [[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]], [[1, 2, 3]], [[1], [2], [3]]])
    console.log(spiral(grid).join(" "));

// 1 2 3 4 8 12 11 10 9 5 6 7
// 1 2 3
// 1 2 3

function spiral(grid: number[][]): number[] {
    const out: number[] = [];
    let top = 0, bottom = grid.length - 1, left = 0, right = grid[0].length - 1;
    while (top <= bottom && left <= right) {    // unread: rows top..bottom, columns left..right
        for (let c = left; c <= right; c++) out.push(grid[top][c]);      // along the top row
        top++;
        for (let r = top; r <= bottom; r++) out.push(grid[r][right]);    // down the right column
        right--;
        if (top <= bottom) {                    // a row is left to read backwards
            for (let c = right; c >= left; c--) out.push(grid[bottom][c]);
            bottom--;
        }
        if (left <= right) {                    // a column is left to read upwards
            for (let r = bottom; r >= top; r--) out.push(grid[r][left]);
            left++;
        }
    }
    return out;
}

const grids: number[][][] = [[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]], [[1, 2, 3]], [[1], [2], [3]]];
for (const grid of grids) console.log(spiral(grid).join(" "));

// 1 2 3 4 8 12 11 10 9 5 6 7
// 1 2 3
// 1 2 3

using System;
using System.Collections.Generic;

class Program {
    static List<int> Spiral(int[][] grid) {
        var result = new List<int>();
        int top = 0, bottom = grid.Length - 1, left = 0, right = grid[0].Length - 1;
        while (top <= bottom && left <= right) {  // unread: rows top..bottom, columns left..right
            for (int c = left; c <= right; c++) result.Add(grid[top][c]);      // along the top row
            top++;
            for (int r = top; r <= bottom; r++) result.Add(grid[r][right]);    // down the right column
            right--;
            if (top <= bottom) {                  // a row is left to read backwards
                for (int c = right; c >= left; c--) result.Add(grid[bottom][c]);
                bottom--;
            }
            if (left <= right) {                  // a column is left to read upwards
                for (int r = bottom; r >= top; r--) result.Add(grid[r][left]);
                left++;
            }
        }
        return result;
    }

    static void Main() {
        int[][][] grids = {
            new[] { new[] {1, 2, 3, 4}, new[] {5, 6, 7, 8}, new[] {9, 10, 11, 12} },
            new[] { new[] {1, 2, 3} },
            new[] { new[] {1}, new[] {2}, new[] {3} },
        };
        foreach (var grid in grids) Console.WriteLine(string.Join(" ", Spiral(grid)));
    }
}

// 1 2 3 4 8 12 11 10 9 5 6 7
// 1 2 3
// 1 2 3

package main

import (
	"fmt"
	"strings"
)

func spiral(grid [][]int) []int {
	var out []int
	top, bottom, left, right := 0, len(grid)-1, 0, len(grid[0])-1
	for top <= bottom && left <= right { // unread: rows top..bottom, columns left..right
		for c := left; c <= right; c++ { // along the top row
			out = append(out, grid[top][c])
		}
		top++
		for r := top; r <= bottom; r++ { // down the right column
			out = append(out, grid[r][right])
		}
		right--
		if top <= bottom { // a row is left to read backwards
			for c := right; c >= left; c-- {
				out = append(out, grid[bottom][c])
			}
			bottom--
		}
		if left <= right { // a column is left to read upwards
			for r := bottom; r >= top; r-- {
				out = append(out, grid[r][left])
			}
			left++
		}
	}
	return out
}

func main() {
	grids := [][][]int{{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}, {{1, 2, 3}}, {{1}, {2}, {3}}}
	for _, grid := range grids {
		fmt.Println(strings.Trim(fmt.Sprint(spiral(grid)), "[]"))
	}
}

// 1 2 3 4 8 12 11 10 9 5 6 7
// 1 2 3
// 1 2 3

The 3 × 4 grid 1 to 12 with the spiral's passes as numbered arrows around it: 1, along the top row 1 2 3 4; 2, down the right column 8 12; 3, along the bottom row backwards 11 10 9; 4, up the left column 5. A dashed box marks the row still unread, 6 7, and pass 5 reads it. Two verdict cards: with the guards, 1 2 3 4 8 12 11 10 9 5 6 7, each cell once; without them, 6 is read a second time, 13 values for 12 cells. Focal line: the boundaries move in, and the guards stop a second read. Title: the spiral shrinks.

1 2 3 4 8 12 11 10 9 5 6 7 for the 3 × 4 grid, and a single row or a single column comes out once, 1 2 3. Each cell is read once, so it's O(m · n) time.

Walk the Matrix. Steer a walk yourself: a spiral that turns at the boundaries, or Diagonal Traverse's zigzag. A step off the grid, or onto a cell you've already read, is refused.

Walk the Matrix: steer a spiral or a zigzag, and see which steps the grid refuses

The transpose

The transpose turns rows into columns: cell (r, c) moves to (c, r). An m × n matrix becomes n × m, so Transpose Matrix builds a new one. Only a square matrix can be transposed in place, swapping each pair across the diagonal once:

def show(grid):
    return " | ".join(" ".join(map(str, row)) for row in grid)


def transpose(grid):                              # m x n in, n x m out: cell (r, c) goes to (c, r)
    rows, cols = len(grid), len(grid[0])
    return [[grid[r][c] for r in range(rows)] for c in range(cols)]


print(show(transpose([[1, 2, 3], [4, 5, 6]])))

square = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
n = len(square)
for r in range(n):                                # in place, square only: each pair above the diagonal, once
    for c in range(r + 1, n):
        square[r][c], square[c][r] = square[c][r], square[r][c]
print(show(square))

# 1 4 | 2 5 | 3 6
# 1 4 7 | 2 5 8 | 3 6 9

public class Main {
    static String show(int[][] grid) {
        StringBuilder sb = new StringBuilder();
        for (int[] row : grid) {
            if (sb.length() > 0) sb.append(" | ");
            for (int c = 0; c < row.length; c++) sb.append(c == 0 ? "" : " ").append(row[c]);
        }
        return sb.toString();
    }

    static int[][] transpose(int[][] grid) {      // m x n in, n x m out: cell (r, c) goes to (c, r)
        int rows = grid.length, cols = grid[0].length;
        int[][] t = new int[cols][rows];
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++) t[c][r] = grid[r][c];
        return t;
    }

    public static void main(String[] args) {
        System.out.println(show(transpose(new int[][] {{1, 2, 3}, {4, 5, 6}})));
        int[][] square = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int n = square.length;
        for (int r = 0; r < n; r++)               // in place, square only: each pair above the diagonal, once
            for (int c = r + 1; c < n; c++) {
                int keep = square[r][c];
                square[r][c] = square[c][r];
                square[c][r] = keep;
            }
        System.out.println(show(square));
    }
}

// 1 4 | 2 5 | 3 6
// 1 4 7 | 2 5 8 | 3 6 9

#include <bits/stdc++.h>
using namespace std;

string show(const vector<vector<int>>& grid) {
    string s;
    for (auto& row : grid) {
        if (!s.empty()) s += " | ";
        for (size_t c = 0; c < row.size(); c++) s += (c ? " " : "") + to_string(row[c]);
    }
    return s;
}

vector<vector<int>> transpose(const vector<vector<int>>& grid) {   // m x n in, n x m out: (r, c) goes to (c, r)
    int rows = grid.size(), cols = grid[0].size();
    vector<vector<int>> t(cols, vector<int>(rows));
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++) t[c][r] = grid[r][c];
    return t;
}

int main() {
    cout << show(transpose({{1, 2, 3}, {4, 5, 6}})) << "\n";
    vector<vector<int>> square = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    int n = square.size();
    for (int r = 0; r < n; r++)                   // in place, square only: each pair above the diagonal, once
        for (int c = r + 1; c < n; c++) swap(square[r][c], square[c][r]);
    cout << show(square) << "\n";
}

// 1 4 | 2 5 | 3 6
// 1 4 7 | 2 5 8 | 3 6 9

const show = grid => grid.map(row => row.join(" ")).join(" | ");

function transpose(grid) {                      // m x n in, n x m out: cell (r, c) goes to (c, r)
    const rows = grid.length, cols = grid[0].length;
    return Array.from({ length: cols }, (_, c) => Array.from({ length: rows }, (_, r) => grid[r][c]));
}

console.log(show(transpose([[1, 2, 3], [4, 5, 6]])));
const square = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
const n = square.length;
for (let r = 0; r < n; r++)                     // in place, square only: each pair above the diagonal, once
    for (let c = r + 1; c < n; c++) [square[r][c], square[c][r]] = [square[c][r], square[r][c]];
console.log(show(square));

// 1 4 | 2 5 | 3 6
// 1 4 7 | 2 5 8 | 3 6 9

const show = (grid: number[][]): string => grid.map(row => row.join(" ")).join(" | ");

function transpose(grid: number[][]): number[][] {   // m x n in, n x m out: cell (r, c) goes to (c, r)
    const rows = grid.length, cols = grid[0].length;
    return Array.from({ length: cols }, (_, c) => Array.from({ length: rows }, (_, r) => grid[r][c]));
}

console.log(show(transpose([[1, 2, 3], [4, 5, 6]])));
const square: number[][] = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
const n: number = square.length;
for (let r = 0; r < n; r++)                     // in place, square only: each pair above the diagonal, once
    for (let c = r + 1; c < n; c++) [square[r][c], square[c][r]] = [square[c][r], square[r][c]];
console.log(show(square));

// 1 4 | 2 5 | 3 6
// 1 4 7 | 2 5 8 | 3 6 9

using System;
using System.Linq;

class Program {
    static string Show(int[][] grid) => string.Join(" | ", grid.Select(row => string.Join(" ", row)));

    static int[][] Transpose(int[][] grid) {      // m x n in, n x m out: cell (r, c) goes to (c, r)
        int rows = grid.Length, cols = grid[0].Length;
        int[][] t = new int[cols][];
        for (int c = 0; c < cols; c++) {
            t[c] = new int[rows];
            for (int r = 0; r < rows; r++) t[c][r] = grid[r][c];
        }
        return t;
    }

    static void Main() {
        Console.WriteLine(Show(Transpose(new[] { new[] {1, 2, 3}, new[] {4, 5, 6} })));
        int[][] square = { new[] {1, 2, 3}, new[] {4, 5, 6}, new[] {7, 8, 9} };
        int n = square.Length;
        for (int r = 0; r < n; r++)               // in place, square only: each pair above the diagonal, once
            for (int c = r + 1; c < n; c++) (square[r][c], square[c][r]) = (square[c][r], square[r][c]);
        Console.WriteLine(Show(square));
    }
}

// 1 4 | 2 5 | 3 6
// 1 4 7 | 2 5 8 | 3 6 9

package main

import (
	"fmt"
	"strings"
)

func show(grid [][]int) string {
	rows := make([]string, len(grid))
	for i, row := range grid {
		rows[i] = strings.Trim(fmt.Sprint(row), "[]")
	}
	return strings.Join(rows, " | ")
}

func transpose(grid [][]int) [][]int { // m x n in, n x m out: cell (r, c) goes to (c, r)
	rows, cols := len(grid), len(grid[0])
	t := make([][]int, cols)
	for c := range t {
		t[c] = make([]int, rows)
		for r := 0; r < rows; r++ {
			t[c][r] = grid[r][c]
		}
	}
	return t
}

func main() {
	fmt.Println(show(transpose([][]int{{1, 2, 3}, {4, 5, 6}})))
	square := [][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
	n := len(square)
	for r := 0; r < n; r++ { // in place, square only: each pair above the diagonal, once
		for c := r + 1; c < n; c++ {
			square[r][c], square[c][r] = square[c][r], square[r][c]
		}
	}
	fmt.Println(show(square))
}

// 1 4 | 2 5 | 3 6
// 1 4 7 | 2 5 8 | 3 6 9

The 2 × 3 matrix came out 3 × 2, 1 4 | 2 5 | 3 6, and the 3 × 3 one, 1 4 7 | 2 5 8 | 3 6 9. The inner loop starts at r + 1, so each pair above the diagonal is swapped once; the cells on it stay where they are. Rotating a square matrix is a transpose and one more step: that's the next lesson, Changing a Matrix in Place.

Spotting it

The clues: a "matrix", "grid", "board" or "image" given as rows of values, an m × n input, cells and their neighbours, or a reading order: spiral, diagonal, row by row, column by column. Near misses:

The shortest way through a grid, or how many islands it holds: a graph search on the cells (Graphs).
Sums over many rectangles of one grid: Difference Arrays and 2D Prefix Sums.
Finding a value in a matrix sorted along its rows and columns: Binary Search on Two Sorted Arrays and Matrices.
Filling a grid by trying choices and undoing them, like a Sudoku solver: Backtracking on Grids and Constraints.

Mistakes that cost an interview

One row, three times. A grid of zeros made in one line can hold the same row three times, so writing one cell changes a whole column:

grid = [[0] * 3] * 3                  # one row, and the same row twice more
grid[0][0] = 1
for row in grid:
    print(*row)

# 1 0 0
# 1 0 0
# 1 0 0

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[][] grid = new int[3][];
        Arrays.fill(grid, new int[3]);    // one row, in all three places
        grid[0][0] = 1;
        for (int[] row : grid) System.out.println(row[0] + " " + row[1] + " " + row[2]);
    }
}

// 1 0 0
// 1 0 0
// 1 0 0

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<vector<int>> grid(3, vector<int>(3));   // three copies of one row
    grid[0][0] = 1;
    for (auto& row : grid) cout << row[0] << " " << row[1] << " " << row[2] << "\n";
}

// 1 0 0
// 0 0 0
// 0 0 0

const grid = Array(3).fill(Array(3).fill(0));   // one row, in all three places
grid[0][0] = 1;
for (const row of grid) console.log(row.join(" "));

// 1 0 0
// 1 0 0
// 1 0 0

const grid: number[][] = Array(3).fill(Array(3).fill(0));   // one row, in all three places
grid[0][0] = 1;
for (const row of grid) console.log(row.join(" "));

// 1 0 0
// 1 0 0
// 1 0 0

using System;

class Program {
    static void Main() {
        int[][] grid = new int[3][];
        Array.Fill(grid, new int[3]);     // one row, in all three places
        grid[0][0] = 1;
        foreach (int[] row in grid) Console.WriteLine(string.Join(" ", row));
    }
}

// 1 0 0
// 1 0 0
// 1 0 0

package main

import (
	"fmt"
	"strings"
)

func main() {
	row := make([]int, 3)
	grid := [][]int{row, row, row} // one row, in all three places
	grid[0][0] = 1
	for _, row := range grid {
		fmt.Println(strings.Trim(fmt.Sprint(row), "[]"))
	}
}

// 1 0 0
// 1 0 0
// 1 0 0

Python, Java, JavaScript, TypeScript, C# and Go put one row in all three places, so setting grid[0][0] set the first cell of every row. C++'s vector copies its fill value, so its three rows are three. Build each row on its own:

grid = [[0] * 3 for _ in range(3)]    # a new row each time
grid[0][0] = 1
for row in grid:
    print(*row)

# 1 0 0
# 0 0 0
# 0 0 0

public class Main {
    public static void main(String[] args) {
        int[][] grid = new int[3][3];     // three rows of their own
        grid[0][0] = 1;
        for (int[] row : grid) System.out.println(row[0] + " " + row[1] + " " + row[2]);
    }
}

// 1 0 0
// 0 0 0
// 0 0 0

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<vector<int>> grid(3, vector<int>(3));   // three copies of one row
    grid[0][0] = 1;
    for (auto& row : grid) cout << row[0] << " " << row[1] << " " << row[2] << "\n";
}

// 1 0 0
// 0 0 0
// 0 0 0

const grid = Array.from({ length: 3 }, () => Array(3).fill(0));   // a new row each time
grid[0][0] = 1;
for (const row of grid) console.log(row.join(" "));

// 1 0 0
// 0 0 0
// 0 0 0

const grid: number[][] = Array.from({ length: 3 }, () => Array(3).fill(0));   // a new row each time
grid[0][0] = 1;
for (const row of grid) console.log(row.join(" "));

// 1 0 0
// 0 0 0
// 0 0 0

using System;

class Program {
    static void Main() {
        int[][] grid = new int[3][];
        for (int r = 0; r < 3; r++) grid[r] = new int[3];   // a new row each time
        grid[0][0] = 1;
        foreach (int[] row in grid) Console.WriteLine(string.Join(" ", row));
    }
}

// 1 0 0
// 0 0 0
// 0 0 0

package main

import (
	"fmt"
	"strings"
)

func main() {
	grid := make([][]int, 3)
	for r := range grid {
		grid[r] = make([]int, 3) // a new row each time
	}
	grid[0][0] = 1
	for _, row := range grid {
		fmt.Println(strings.Trim(fmt.Sprint(row), "[]"))
	}
}

// 1 0 0
// 0 0 0
// 0 0 0

No bounds check. Counting the eight neighbours of the corner (0, 0) without one reads row −1 and column −1. The right count is 0:

grid = [[1, 0, 0],
        [0, 0, 1],
        [1, 1, 1]]
count = 0
for dr in (-1, 0, 1):                 # the eight neighbours of (0, 0), with no bounds check
    for dc in (-1, 0, 1):
        if dr or dc:
            count += grid[0 + dr][0 + dc]
print(count)

# 4

public class Main {
    public static void main(String[] args) {
        int[][] grid = {{1, 0, 0}, {0, 0, 1}, {1, 1, 1}};
        int count = 0;
        for (int dr = -1; dr <= 1; dr++)  // the eight neighbours of (0, 0), with no bounds check
            for (int dc = -1; dc <= 1; dc++)
                if (dr != 0 || dc != 0) count += grid[0 + dr][0 + dc];
        System.out.println(count);
    }
}

// (stopped: ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 3)

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<vector<int>> grid = {{1, 0, 0}, {0, 0, 1}, {1, 1, 1}};
    int count = 0;
    for (int dr = -1; dr <= 1; dr++)      // the eight neighbours of (0, 0), with no bounds check
        for (int dc = -1; dc <= 1; dc++)
            if (dr != 0 || dc != 0) count += grid[0 + dr][0 + dc];
    cout << count << "\n";
}

// 3

const grid = [[1, 0, 0], [0, 0, 1], [1, 1, 1]];
let count = 0;
for (let dr = -1; dr <= 1; dr++)      // the eight neighbours of (0, 0), with no bounds check
    for (let dc = -1; dc <= 1; dc++)
        if (dr !== 0 || dc !== 0) count += grid[0 + dr][0 + dc];
console.log(count);

// (stopped: TypeError: Cannot read properties of undefined (reading '-1'))

const grid: number[][] = [[1, 0, 0], [0, 0, 1], [1, 1, 1]];
let count: number = 0;
for (let dr = -1; dr <= 1; dr++)      // the eight neighbours of (0, 0), with no bounds check
    for (let dc = -1; dc <= 1; dc++)
        if (dr !== 0 || dc !== 0) count += grid[0 + dr][0 + dc];
console.log(count);

// (stopped: TypeError: Cannot read properties of undefined (reading '-1'))

using System;

class Program {
    static void Main() {
        int[][] grid = { new[] {1, 0, 0}, new[] {0, 0, 1}, new[] {1, 1, 1} };
        int count = 0;
        for (int dr = -1; dr <= 1; dr++)  // the eight neighbours of (0, 0), with no bounds check
            for (int dc = -1; dc <= 1; dc++)
                if (dr != 0 || dc != 0) count += grid[0 + dr][0 + dc];
        Console.WriteLine(count);
    }
}

// (stopped: IndexOutOfRangeException: Index was outside the bounds of the array.)

package main

import "fmt"

func main() {
	grid := [][]int{{1, 0, 0}, {0, 0, 1}, {1, 1, 1}}
	count := 0
	for dr := -1; dr <= 1; dr++ { // the eight neighbours of (0, 0), with no bounds check
		for dc := -1; dc <= 1; dc++ {
			if dr != 0 || dc != 0 {
				count += grid[0+dr][0+dc]
			}
		}
	}
	fmt.Println(count)
}

// (stopped: panic: index out of range [-1])

Python printed 4: a negative index counts from the end, so row −1 is the last row and the mistake gives a number, not an error. C++ printed 3, reading whatever memory sat next to the rows, which is undefined behaviour. Java, C# and Go stopped with an index out of range, JavaScript and TypeScript with a TypeError, reading a cell of the row that isn't there. Check 0 <= nr < rows and 0 <= nc < cols before every read.

The spiral without its guards. Leave out if top <= bottom and if left <= right and the last row or column inside is read a second time, backwards:

def spiral(grid):
    out = []
    top, bottom, left, right = 0, len(grid) - 1, 0, len(grid[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1):              # along the top row
            out.append(grid[top][c])
        top += 1
        for r in range(top, bottom + 1):              # down the right column
            out.append(grid[r][right])
        right -= 1
        for c in range(right, left - 1, -1):          # along the bottom row, backwards: no guard
            out.append(grid[bottom][c])
        bottom -= 1
        for r in range(bottom, top - 1, -1):          # up the left column: no guard
            out.append(grid[r][left])
        left += 1
    return out


for grid in ([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]], [[1, 2, 3]], [[1], [2], [3]]):
    print(*spiral(grid))

# 1 2 3 4 8 12 11 10 9 5 6 7 6
# 1 2 3 2 1
# 1 2 3 2

import java.util.*;

public class Main {
    static List<Integer> spiral(int[][] grid) {
        List<Integer> out = new ArrayList<>();
        int top = 0, bottom = grid.length - 1, left = 0, right = grid[0].length - 1;
        while (top <= bottom && left <= right) {
            for (int c = left; c <= right; c++) out.add(grid[top][c]);      // along the top row
            top++;
            for (int r = top; r <= bottom; r++) out.add(grid[r][right]);    // down the right column
            right--;
            for (int c = right; c >= left; c--) out.add(grid[bottom][c]);   // backwards: no guard
            bottom--;
            for (int r = bottom; r >= top; r--) out.add(grid[r][left]);     // upwards: no guard
            left++;
        }
        return out;
    }

    public static void main(String[] args) {
        int[][][] grids = {{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}, {{1, 2, 3}}, {{1}, {2}, {3}}};
        for (int[][] grid : grids) {
            StringBuilder line = new StringBuilder();
            for (int v : spiral(grid)) line.append(line.length() == 0 ? "" : " ").append(v);
            System.out.println(line);
        }
    }
}

// 1 2 3 4 8 12 11 10 9 5 6 7 6
// 1 2 3 2 1
// 1 2 3 2

#include <bits/stdc++.h>
using namespace std;

vector<int> spiral(const vector<vector<int>>& grid) {
    vector<int> out;
    int top = 0, bottom = grid.size() - 1, left = 0, right = grid[0].size() - 1;
    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; c++) out.push_back(grid[top][c]);      // along the top row
        top++;
        for (int r = top; r <= bottom; r++) out.push_back(grid[r][right]);    // down the right column
        right--;
        for (int c = right; c >= left; c--) out.push_back(grid[bottom][c]);   // backwards: no guard
        bottom--;
        for (int r = bottom; r >= top; r--) out.push_back(grid[r][left]);     // upwards: no guard
        left++;
    }
    return out;
}

int main() {
    vector<vector<vector<int>>> grids = {{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}, {{1, 2, 3}}, {{1}, {2}, {3}}};
    for (auto& grid : grids) {
        vector<int> out = spiral(grid);
        for (size_t i = 0; i < out.size(); i++) cout << (i ? " " : "") << out[i];
        cout << "\n";
    }
}

// 1 2 3 4 8 12 11 10 9 5 6 7 6
// 1 2 3 2 1
// 1 2 3 2

function spiral(grid) {
    const out = [];
    let top = 0, bottom = grid.length - 1, left = 0, right = grid[0].length - 1;
    while (top <= bottom && left <= right) {
        for (let c = left; c <= right; c++) out.push(grid[top][c]);      // along the top row
        top++;
        for (let r = top; r <= bottom; r++) out.push(grid[r][right]);    // down the right column
        right--;
        for (let c = right; c >= left; c--) out.push(grid[bottom][c]);   // backwards: no guard
        bottom--;
        for (let r = bottom; r >= top; r--) out.push(grid[r][left]);     // upwards: no guard
        left++;
    }
    return out;
}

for (const grid of [[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]], [[1, 2, 3]], [[1], [2], [3]]])
    console.log(spiral(grid).join(" "));

// 1 2 3 4 8 12 11 10 9 5 6 7 6
// 1 2 3 2 1
// 1 2 3 2

function spiral(grid: number[][]): number[] {
    const out: number[] = [];
    let top = 0, bottom = grid.length - 1, left = 0, right = grid[0].length - 1;
    while (top <= bottom && left <= right) {
        for (let c = left; c <= right; c++) out.push(grid[top][c]);      // along the top row
        top++;
        for (let r = top; r <= bottom; r++) out.push(grid[r][right]);    // down the right column
        right--;
        for (let c = right; c >= left; c--) out.push(grid[bottom][c]);   // backwards: no guard
        bottom--;
        for (let r = bottom; r >= top; r--) out.push(grid[r][left]);     // upwards: no guard
        left++;
    }
    return out;
}

const grids: number[][][] = [[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]], [[1, 2, 3]], [[1], [2], [3]]];
for (const grid of grids) console.log(spiral(grid).join(" "));

// 1 2 3 4 8 12 11 10 9 5 6 7 6
// 1 2 3 2 1
// 1 2 3 2

using System;
using System.Collections.Generic;

class Program {
    static List<int> Spiral(int[][] grid) {
        var result = new List<int>();
        int top = 0, bottom = grid.Length - 1, left = 0, right = grid[0].Length - 1;
        while (top <= bottom && left <= right) {
            for (int c = left; c <= right; c++) result.Add(grid[top][c]);      // along the top row
            top++;
            for (int r = top; r <= bottom; r++) result.Add(grid[r][right]);    // down the right column
            right--;
            for (int c = right; c >= left; c--) result.Add(grid[bottom][c]);   // backwards: no guard
            bottom--;
            for (int r = bottom; r >= top; r--) result.Add(grid[r][left]);     // upwards: no guard
            left++;
        }
        return result;
    }

    static void Main() {
        int[][][] grids = {
            new[] { new[] {1, 2, 3, 4}, new[] {5, 6, 7, 8}, new[] {9, 10, 11, 12} },
            new[] { new[] {1, 2, 3} },
            new[] { new[] {1}, new[] {2}, new[] {3} },
        };
        foreach (var grid in grids) Console.WriteLine(string.Join(" ", Spiral(grid)));
    }
}

// 1 2 3 4 8 12 11 10 9 5 6 7 6
// 1 2 3 2 1
// 1 2 3 2

package main

import (
	"fmt"
	"strings"
)

func spiral(grid [][]int) []int {
	var out []int
	top, bottom, left, right := 0, len(grid)-1, 0, len(grid[0])-1
	for top <= bottom && left <= right {
		for c := left; c <= right; c++ { // along the top row
			out = append(out, grid[top][c])
		}
		top++
		for r := top; r <= bottom; r++ { // down the right column
			out = append(out, grid[r][right])
		}
		right--
		for c := right; c >= left; c-- { // along the bottom row, backwards: no guard
			out = append(out, grid[bottom][c])
		}
		bottom--
		for r := bottom; r >= top; r-- { // up the left column: no guard
			out = append(out, grid[r][left])
		}
		left++
	}
	return out
}

func main() {
	grids := [][][]int{{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}, {{1, 2, 3}}, {{1}, {2}, {3}}}
	for _, grid := range grids {
		fmt.Println(strings.Trim(fmt.Sprint(spiral(grid)), "[]"))
	}
}

// 1 2 3 4 8 12 11 10 9 5 6 7 6
// 1 2 3 2 1
// 1 2 3 2

The 3 × 4 grid gave 1 2 3 4 8 12 11 10 9 5 6 7 6: 6 twice, 13 values for 12 cells. One row gave 1 2 3 2 1, one column 1 2 3 2. A square grid hides the bug, so test a single row and a single column.

An in-place transpose over every pair. With the inner loop starting at 0 instead of r + 1, each pair is swapped twice, which swaps it back:

square = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
n = len(square)
for r in range(n):
    for c in range(n):                            # every pair, from c = 0: each one is swapped twice
        square[r][c], square[c][r] = square[c][r], square[r][c]
print(" | ".join(" ".join(map(str, row)) for row in square))

# 1 2 3 | 4 5 6 | 7 8 9

public class Main {
    public static void main(String[] args) {
        int[][] square = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int n = square.length;
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++) {         // every pair, from c = 0: each one is swapped twice
                int keep = square[r][c];
                square[r][c] = square[c][r];
                square[c][r] = keep;
            }
        StringBuilder sb = new StringBuilder();
        for (int[] row : square) {
            if (sb.length() > 0) sb.append(" | ");
            sb.append(row[0]).append(" ").append(row[1]).append(" ").append(row[2]);
        }
        System.out.println(sb);
    }
}

// 1 2 3 | 4 5 6 | 7 8 9

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<vector<int>> square = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    int n = square.size();
    for (int r = 0; r < n; r++)
        for (int c = 0; c < n; c++) swap(square[r][c], square[c][r]);   // every pair: each one twice
    for (int r = 0; r < n; r++)
        cout << (r ? " | " : "") << square[r][0] << " " << square[r][1] << " " << square[r][2];
    cout << "\n";
}

// 1 2 3 | 4 5 6 | 7 8 9

const square = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
const n = square.length;
for (let r = 0; r < n; r++)
    for (let c = 0; c < n; c++)                 // every pair, from c = 0: each one is swapped twice
        [square[r][c], square[c][r]] = [square[c][r], square[r][c]];
console.log(square.map(row => row.join(" ")).join(" | "));

// 1 2 3 | 4 5 6 | 7 8 9

const square: number[][] = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
const n: number = square.length;
for (let r = 0; r < n; r++)
    for (let c = 0; c < n; c++)                 // every pair, from c = 0: each one is swapped twice
        [square[r][c], square[c][r]] = [square[c][r], square[r][c]];
console.log(square.map(row => row.join(" ")).join(" | "));

// 1 2 3 | 4 5 6 | 7 8 9

using System;
using System.Linq;

class Program {
    static void Main() {
        int[][] square = { new[] {1, 2, 3}, new[] {4, 5, 6}, new[] {7, 8, 9} };
        int n = square.Length;
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++)           // every pair, from c = 0: each one is swapped twice
                (square[r][c], square[c][r]) = (square[c][r], square[r][c]);
        Console.WriteLine(string.Join(" | ", square.Select(row => string.Join(" ", row))));
    }
}

// 1 2 3 | 4 5 6 | 7 8 9

package main

import (
	"fmt"
	"strings"
)

func main() {
	square := [][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
	n := len(square)
	for r := 0; r < n; r++ {
		for c := 0; c < n; c++ { // every pair, from c = 0: each one is swapped twice
			square[r][c], square[c][r] = square[c][r], square[r][c]
		}
	}
	rows := make([]string, n)
	for r, row := range square {
		rows[r] = strings.Trim(fmt.Sprint(row), "[]")
	}
	fmt.Println(strings.Join(rows, " | "))
}

// 1 2 3 | 4 5 6 | 7 8 9

The square came out as it went in, 1 2 3 | 4 5 6 | 7 8 9. Swap only the pairs above the diagonal, c from r + 1.

Check yourself

Quiz

1 / 6

Multiple choice

Adding up every cell of a 3,000 × 3,000 int matrix in C++: which loop order ran faster on our judge?

Practice

In this section, easy to hard:

Transpose Matrix: a new n × m matrix, cell (r, c) to (c, r).
Spiral Matrix: four boundaries and the two guards.
Diagonal Traverse: the anti-diagonals r + c, every other one read upwards.
Valid Sudoku: every cell checked against its row, its column and its box, (r / 3) * 3 + c / 3.

Next: Changing a Matrix in Place, where the answer has to be written into the matrix you were given.