PK

PKBytes

Explore tracks
Chapter 10: Matrices, Grids and Multidimensional Arrays
10.02Beginner / Intermediate6 topics18 min6 interactive animations

Basic operations

The basic matrix operations: traversing by rows and columns, transposing, reflecting, rotating by 90 degrees in place, addition and the standard matrix multiplication, each with its cost.

Learning goals

  • Traverse a matrix in row and column order
  • Transpose, reflect and rotate a square matrix in place
  • Add and multiply matrices and state the costs

Prerequisites

2D representation
10.02.1

Traverse rows and columns

Row-by-row traversal runs the column index in the inner loop; column-by-column swaps the loops. Both visit all R × C cells in O(R·C) time, but row order is faster on large matrices because it reads memory sequentially. Choose the order the problem needs, and prefer row order when both are possible.

Compare the two orders in the animation.

Java
1for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) visit(g[r][c]);   // row by row
2for (int c = 0; c < C; c++) for (int r = 0; r < R; r++) visit(g[r][c]);   // column by column

Matrix traversal orders

Interactive · edit the input

Your input

Try

grid · 3 × 4

0123
0
1
2
3
4
1
5
6
7
8
2
9
10
11
12
Visiting nowAlready visited

visit order

none yet
Setup

Spiral: walk the outer ring clockwise, then repeat on the shrinking inner matrix.

Step 1 / 14
Java
1// row-major: consecutive memory, cache friendly
2for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) visit(g[r][c]);
3// column-major: jumps a whole row each step
4for (int c = 0; c < C; c++) for (int r = 0; r < R; r++) visit(g[r][c]);
5// snake: odd rows run right to left
6for (int r = 0; r < R; r++) for (int k = 0; k < C; k++) visit(g[r][r % 2 == 0 ? k : C - 1 - k]);
7// spiral: peel the outer ring, then shrink the bounds
8int top = 0, bottom = R - 1, left = 0, right = C - 1;
9while (top <= bottom && left <= right) {
10    for (int c = left; c <= right; c++) visit(g[top][c]);                       // top side
11    for (int r = top + 1; r <= bottom; r++) visit(g[r][right]);                 // right side
12    if (top < bottom) for (int c = right - 1; c >= left; c--) visit(g[bottom][c]);   // bottom side
13    if (left < right) for (int r = bottom - 1; r > top; r--) visit(g[r][left]);      // left side
14    top++; bottom--; left++; right--;                                           // boundary-only stops after one ring
15}
16// cells with the same r + c form an anti-diagonal; zigzag reverses every other one
17for (int d = 0; d < R + C - 1; d++) {
18    for (int r = Math.max(0, d - C + 1); r <= Math.min(d, R - 1); r++) visit(g[r][d - r]);
19}

Live state

R

3

C

4

No condition evaluated on this step
Execution trace (dry run table)Show 14 steps
StepLineStateWhat happens
1L10R=3 C=4Spiral: walk the outer ring clockwise, then repeat on the shrinking inner matrix.
2L10step=1 r=0 c=0 g[r][c]=1Visit g[0][0] = 1 (cell 1 of 12).
3L10step=2 r=0 c=1 g[r][c]=2Visit g[0][1] = 2 (cell 2 of 12).
4L10step=3 r=0 c=2 g[r][c]=3Visit g[0][2] = 3 (cell 3 of 12).
5L10step=4 r=0 c=3 g[r][c]=4Visit g[0][3] = 4 (cell 4 of 12).
6L10step=5 r=1 c=3 g[r][c]=8Visit g[1][3] = 8 (cell 5 of 12).
7L10step=6 r=2 c=3 g[r][c]=12Visit g[2][3] = 12 (cell 6 of 12).
8L10step=7 r=2 c=2 g[r][c]=11Visit g[2][2] = 11 (cell 7 of 12).
9L10step=8 r=2 c=1 g[r][c]=10Visit g[2][1] = 10 (cell 8 of 12).
10L10step=9 r=2 c=0 g[r][c]=9Visit g[2][0] = 9 (cell 9 of 12).
11L10step=10 r=1 c=0 g[r][c]=5Visit g[1][0] = 5 (cell 10 of 12).
12L10step=11 r=1 c=1 g[r][c]=6Visit g[1][1] = 6 (cell 11 of 12).
13L10step=12 r=1 c=2 g[r][c]=7Visit g[1][2] = 7 (cell 12 of 12).
14L10return=[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]12 cells visited: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]. O(R x C) time.
10.02.2

Transpose

The transpose swaps rows and columns: t[c][r] = g[r][c]. For a square matrix it can be done in place by swapping each pair of mirror cells across the main diagonal, visiting only the cells above the diagonal (c > r) so no pair is swapped twice. A non-square matrix needs a new array of shape C × R.

Choose Transpose and watch the mirror pairs swap.

Java
1static void transpose(int[][] g) {              // square n x n
2    for (int r = 0; r < g.length; r++)
3        for (int c = r + 1; c < g.length; c++) {
4            int t = g[r][c]; g[r][c] = g[c][r]; g[c][r] = t;
5        }
6}

Transpose, reflect and rotate a matrix in place

Interactive · edit the input

Your input

Try

grid · 3 × 3

012
0
1
2
3
1
4
5
6
2
7
8
9
Pair being swappedJust swapped
Setup

A 90-degree clockwise rotation is a transpose followed by a left-right reflection of every row.

Step 1 / 12
Java
1static void transpose(int[][] g) {                       // square matrix
2    for (int r = 0; r < g.length; r++)
3        for (int c = r + 1; c < g.length; c++) swap(g, r, c, c, r);   // only above the diagonal
4}
5static void reflectLeftRight(int[][] g) {
6    for (int[] row : g) for (int lo = 0, hi = row.length - 1; lo < hi; lo++, hi--) { int t = row[lo]; row[lo] = row[hi]; row[hi] = t; }
7}
8static void reflectTopBottom(int[][] g) {
9    for (int lo = 0, hi = g.length - 1; lo < hi; lo++, hi--) { int[] t = g[lo]; g[lo] = g[hi]; g[hi] = t; }
10}
11static void rotateClockwise(int[][] g) { transpose(g); reflectLeftRight(g); }   // 90 degrees clockwise

Live state

R

3

C

3

No condition evaluated on this step
Execution trace (dry run table)Show 12 steps
StepLineStateWhat happens
1L11R=3 C=3A 90-degree clockwise rotation is a transpose followed by a left-right reflection of every row.
2L3r=0 c=1g[0][1] and g[1][0] are mirror cells across the main diagonal.
3L3swaps=1Swap g[0][1] with g[1][0].
4L3r=0 c=2g[0][2] and g[2][0] are mirror cells across the main diagonal.
5L3swaps=2Swap g[0][2] with g[2][0].
6L3r=1 c=2g[1][2] and g[2][1] are mirror cells across the main diagonal.
7L3swaps=3Swap g[1][2] with g[2][1].
8L11Transposed. Now reverse every row.
9L11swaps=4Row 0: swap columns 0 and 2.
10L11swaps=5Row 1: swap columns 0 and 2.
11L11swaps=6Row 2: swap columns 0 and 2.
12L11swaps=6 return=[[7, 4, 1], [8, 5, 2], [9, 6, 3]]6 swaps, O(R x C) time and O(1) extra space (a non-square transpose needs a new matrix).
10.02.3

Reflect

A left-right reflection reverses every row; a top-bottom reflection reverses the order of the rows. Both are O(R·C), in place, with no temporary matrix: swap pairs of cells (or of row references) from the outside in.

Try the non-square preset: reflections work on any rectangle, transpose in place does not.

Java
1static void reflectLeftRight(int[][] g) {
2    for (int[] row : g)
3        for (int lo = 0, hi = row.length - 1; lo < hi; lo++, hi--) { int t = row[lo]; row[lo] = row[hi]; row[hi] = t; }
4}
5static void reflectTopBottom(int[][] g) {
6    for (int lo = 0, hi = g.length - 1; lo < hi; lo++, hi--) { int[] t = g[lo]; g[lo] = g[hi]; g[hi] = t; }   // swaps whole rows
7}

Transpose, reflect and rotate a matrix in place

Interactive · edit the input

Your input

Try

grid · 3 × 3

012
0
1
2
3
1
4
5
6
2
7
8
9
Pair being swappedJust swapped
Setup

A 90-degree clockwise rotation is a transpose followed by a left-right reflection of every row.

Step 1 / 12
Java
1static void transpose(int[][] g) {                       // square matrix
2    for (int r = 0; r < g.length; r++)
3        for (int c = r + 1; c < g.length; c++) swap(g, r, c, c, r);   // only above the diagonal
4}
5static void reflectLeftRight(int[][] g) {
6    for (int[] row : g) for (int lo = 0, hi = row.length - 1; lo < hi; lo++, hi--) { int t = row[lo]; row[lo] = row[hi]; row[hi] = t; }
7}
8static void reflectTopBottom(int[][] g) {
9    for (int lo = 0, hi = g.length - 1; lo < hi; lo++, hi--) { int[] t = g[lo]; g[lo] = g[hi]; g[hi] = t; }
10}
11static void rotateClockwise(int[][] g) { transpose(g); reflectLeftRight(g); }   // 90 degrees clockwise

Live state

R

3

C

3

No condition evaluated on this step
Execution trace (dry run table)Show 12 steps
StepLineStateWhat happens
1L11R=3 C=3A 90-degree clockwise rotation is a transpose followed by a left-right reflection of every row.
2L3r=0 c=1g[0][1] and g[1][0] are mirror cells across the main diagonal.
3L3swaps=1Swap g[0][1] with g[1][0].
4L3r=0 c=2g[0][2] and g[2][0] are mirror cells across the main diagonal.
5L3swaps=2Swap g[0][2] with g[2][0].
6L3r=1 c=2g[1][2] and g[2][1] are mirror cells across the main diagonal.
7L3swaps=3Swap g[1][2] with g[2][1].
8L11Transposed. Now reverse every row.
9L11swaps=4Row 0: swap columns 0 and 2.
10L11swaps=5Row 1: swap columns 0 and 2.
11L11swaps=6Row 2: swap columns 0 and 2.
12L11swaps=6 return=[[7, 4, 1], [8, 5, 2], [9, 6, 3]]6 swaps, O(R x C) time and O(1) extra space (a non-square transpose needs a new matrix).
10.02.4

Rotate 90 degrees

Rotating a square matrix 90° clockwise equals transposing it and then reflecting every row left to right: cell (r, c) moves to (c, n - 1 - r). Counter-clockwise is the transpose followed by reversing the order of the rows. The in-place method uses O(1) extra space and O(n²) time.

The default animation rotates a 3 × 3 matrix in two phases.

Java
1static void rotateClockwise(int[][] g) {
2    int n = g.length;
3    for (int r = 0; r < n; r++) for (int c = r + 1; c < n; c++) { int t = g[r][c]; g[r][c] = g[c][r]; g[c][r] = t; }   // transpose
4    for (int[] row : g) for (int lo = 0, hi = n - 1; lo < hi; lo++, hi--) { int t = row[lo]; row[lo] = row[hi]; row[hi] = t; }   // reverse rows
5}

Transpose, reflect and rotate a matrix in place

Interactive · edit the input

Your input

Try

grid · 3 × 3

012
0
1
2
3
1
4
5
6
2
7
8
9
Pair being swappedJust swapped
Setup

A 90-degree clockwise rotation is a transpose followed by a left-right reflection of every row.

Step 1 / 12
Java
1static void transpose(int[][] g) {                       // square matrix
2    for (int r = 0; r < g.length; r++)
3        for (int c = r + 1; c < g.length; c++) swap(g, r, c, c, r);   // only above the diagonal
4}
5static void reflectLeftRight(int[][] g) {
6    for (int[] row : g) for (int lo = 0, hi = row.length - 1; lo < hi; lo++, hi--) { int t = row[lo]; row[lo] = row[hi]; row[hi] = t; }
7}
8static void reflectTopBottom(int[][] g) {
9    for (int lo = 0, hi = g.length - 1; lo < hi; lo++, hi--) { int[] t = g[lo]; g[lo] = g[hi]; g[hi] = t; }
10}
11static void rotateClockwise(int[][] g) { transpose(g); reflectLeftRight(g); }   // 90 degrees clockwise

Live state

R

3

C

3

No condition evaluated on this step
Execution trace (dry run table)Show 12 steps
StepLineStateWhat happens
1L11R=3 C=3A 90-degree clockwise rotation is a transpose followed by a left-right reflection of every row.
2L3r=0 c=1g[0][1] and g[1][0] are mirror cells across the main diagonal.
3L3swaps=1Swap g[0][1] with g[1][0].
4L3r=0 c=2g[0][2] and g[2][0] are mirror cells across the main diagonal.
5L3swaps=2Swap g[0][2] with g[2][0].
6L3r=1 c=2g[1][2] and g[2][1] are mirror cells across the main diagonal.
7L3swaps=3Swap g[1][2] with g[2][1].
8L11Transposed. Now reverse every row.
9L11swaps=4Row 0: swap columns 0 and 2.
10L11swaps=5Row 1: swap columns 0 and 2.
11L11swaps=6Row 2: swap columns 0 and 2.
12L11swaps=6 return=[[7, 4, 1], [8, 5, 2], [9, 6, 3]]6 swaps, O(R x C) time and O(1) extra space (a non-square transpose needs a new matrix).
10.02.5

Matrix addition

Two matrices of the same shape add cell by cell: c[r][c] = a[r][c] + b[r][c], O(R·C) time. Subtraction and scalar multiplication work the same way. Different shapes cannot be added.

The animation adds a matrix to its own transpose.

Java
1static int[][] add(int[][] a, int[][] b) {
2    int[][] c = new int[a.length][a[0].length];
3    for (int i = 0; i < a.length; i++)
4        for (int j = 0; j < a[0].length; j++) c[i][j] = a[i][j] + b[i][j];
5    return c;
6}

Matrix addition and multiplication

Interactive · edit the input

Your input

Try

grid · 2 × 2

01
0
·
·
1
·
·
Cell being computedComputed
Setup

Each cell C[i][j] is the dot product of row i of A and column j of A: n multiplications and additions per cell.

Step 1 / 6
Java
1static int[][] add(int[][] a, int[][] b) {                // same dimensions: O(n^2)
2    int[][] c = new int[a.length][a[0].length];
3    for (int i = 0; i < a.length; i++) for (int j = 0; j < a[0].length; j++) c[i][j] = a[i][j] + b[i][j];
4    return c;
5}
6static int[][] multiply(int[][] a, int[][] b) {           // (n x m) times (m x p): O(n * m * p)
7    int[][] c = new int[a.length][b[0].length];
8    for (int i = 0; i < a.length; i++)
9        for (int j = 0; j < b[0].length; j++)
10            for (int k = 0; k < b.length; k++) c[i][j] += a[i][k] * b[k][j];   // row i of a dot column j of b
11    return c;
12}

Live state

n

2

No condition evaluated on this step
Execution trace (dry run table)Show 6 steps
StepLineStateWhat happens
1L10n=2Each cell C[i][j] is the dot product of row i of A and column j of A: n multiplications and additions per cell.
2L10i=0 j=0 C[0][0]=7C[0][0] = 1x1 + 2x3 = 7.
3L10i=0 j=1 C[0][1]=10C[0][1] = 1x2 + 2x4 = 10.
4L10i=1 j=0 C[1][0]=15C[1][0] = 3x1 + 4x3 = 15.
5L10i=1 j=1 C[1][1]=22C[1][1] = 3x2 + 4x4 = 22.
6L11return=[[7, 10], [15, 22]]4 cells x 2 multiplications = 8 multiplications: O(n³) for the standard algorithm.
10.02.6

Matrix multiplication basics

An (n × m) matrix times an (m × p) matrix gives an (n × p) matrix where c[i][j] is the dot product of row i of A and column j of B. The standard algorithm uses three loops and costs O(n·m·p), O(n³) for square matrices. Matrix multiplication is not commutative, but it is associative, and Strassen's algorithm reduces the exponent to about 2.81.

Choose C = A × A and read the terms of each dot product.

Java
1static int[][] multiply(int[][] a, int[][] b) {          // (n x m) * (m x p)
2    int n = a.length, m = b.length, p = b[0].length;
3    int[][] c = new int[n][p];
4    for (int i = 0; i < n; i++)
5        for (int k = 0; k < m; k++) {                      // k before j: sequential access to b[k][*]
6            int aik = a[i][k];
7            for (int j = 0; j < p; j++) c[i][j] += aik * b[k][j];
8        }
9    return c;
10}

Matrix addition and multiplication

Interactive · edit the input

Your input

Try

grid · 2 × 2

01
0
·
·
1
·
·
Cell being computedComputed
Setup

Each cell C[i][j] is the dot product of row i of A and column j of A: n multiplications and additions per cell.

Step 1 / 6
Java
1static int[][] add(int[][] a, int[][] b) {                // same dimensions: O(n^2)
2    int[][] c = new int[a.length][a[0].length];
3    for (int i = 0; i < a.length; i++) for (int j = 0; j < a[0].length; j++) c[i][j] = a[i][j] + b[i][j];
4    return c;
5}
6static int[][] multiply(int[][] a, int[][] b) {           // (n x m) times (m x p): O(n * m * p)
7    int[][] c = new int[a.length][b[0].length];
8    for (int i = 0; i < a.length; i++)
9        for (int j = 0; j < b[0].length; j++)
10            for (int k = 0; k < b.length; k++) c[i][j] += a[i][k] * b[k][j];   // row i of a dot column j of b
11    return c;
12}

Live state

n

2

No condition evaluated on this step
Execution trace (dry run table)Show 6 steps
StepLineStateWhat happens
1L10n=2Each cell C[i][j] is the dot product of row i of A and column j of A: n multiplications and additions per cell.
2L10i=0 j=0 C[0][0]=7C[0][0] = 1x1 + 2x3 = 7.
3L10i=0 j=1 C[0][1]=10C[0][1] = 1x2 + 2x4 = 10.
4L10i=1 j=0 C[1][0]=15C[1][0] = 3x1 + 4x3 = 15.
5L10i=1 j=1 C[1][1]=22C[1][1] = 3x2 + 4x4 = 22.
6L11return=[[7, 10], [15, 22]]4 cells x 2 multiplications = 8 multiplications: O(n³) for the standard algorithm.

Practice ladder

Now try it yourself

Easy

  • Transpose [[1, 2], [3, 4]] by hand
  • How many swaps does an in-place transpose of an n × n matrix make?

Medium

  • Rotate [[1, 2, 3], [4, 5, 6], [7, 8, 9]] clockwise using transpose + reflect
  • Multiply [[1, 2], [3, 4]] by itself

Advanced

  • Rotate a matrix in place by moving four cells at a time (layer by layer)

Key takeaways

  • Traversals are O(R·C); prefer row order for speed.
  • Rotate 90° clockwise = transpose, then reverse each row.
  • Matrix multiplication is O(n·m·p) with a dot product per cell.