10.01Beginner / Intermediate5 topics14 min3 interactive animations
2D representation
A matrix is a table of values addressed by row and column. This lesson covers rows and columns, rectangular versus jagged arrays, row-major memory order and why it matters for speed, bounds checks and how Java's int[][] really works.
Learning goals
- Index a matrix by (row, column) and compute its dimensions
- Explain the difference between rectangular and jagged arrays
- Predict which traversal order is cache friendly
- Write correct bounds checks
Prerequisites
Arrays and dynamic arrays
10.01.1
Rows and columns
A matrix with R rows and C columns stores R × C values; g[r][c] is the value in row r (counted from the top) and column c (counted from the left). Indexes start at 0, so the valid rows are 0 to R - 1 and the valid columns 0 to C - 1. Problems often give a flat list of values plus the number of columns; row r then starts at position r × C.
Step through a traversal to see each (row, column) pair visited.
Java
1int[][] g = {{1, 2, 3}, {4, 5, 6}};2int R = g.length; // 2 rows3int C = g[0].length; // 3 columns4int x = g[1][2]; // row 1, column 2 -> 65int flat = 1 * C + 2; // the same cell in a flat array of R * C values (index 5)
Matrix traversal orders
Interactive · edit the inputgrid · 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 friendly2for (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 step4for (int c = 0; c < C; c++) for (int r = 0; r < R; r++) visit(g[r][c]);5// snake: odd rows run right to left6for (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 bounds8int top = 0, bottom = R - 1, left = 0, right = C - 1;9while (top <= bottom && left <= right) {10for (int c = left; c <= right; c++) visit(g[top][c]); // top side11for (int r = top + 1; r <= bottom; r++) visit(g[r][right]); // right side12if (top < bottom) for (int c = right - 1; c >= left; c--) visit(g[bottom][c]); // bottom side13if (left < right) for (int r = bottom - 1; r > top; r--) visit(g[r][left]); // left side14top++; bottom--; left++; right--; // boundary-only stops after one ring15}16// cells with the same r + c form an anti-diagonal; zigzag reverses every other one17for (int d = 0; d < R + C - 1; d++) {18for (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 stepsHide
| Step | Line | State | What happens |
|---|---|---|---|
| 1 | L10 | R=3 C=4 | Spiral: walk the outer ring clockwise, then repeat on the shrinking inner matrix. |
| 2 | L10 | step=1 r=0 c=0 g[r][c]=1 | Visit g[0][0] = 1 (cell 1 of 12). |
| 3 | L10 | step=2 r=0 c=1 g[r][c]=2 | Visit g[0][1] = 2 (cell 2 of 12). |
| 4 | L10 | step=3 r=0 c=2 g[r][c]=3 | Visit g[0][2] = 3 (cell 3 of 12). |
| 5 | L10 | step=4 r=0 c=3 g[r][c]=4 | Visit g[0][3] = 4 (cell 4 of 12). |
| 6 | L10 | step=5 r=1 c=3 g[r][c]=8 | Visit g[1][3] = 8 (cell 5 of 12). |
| 7 | L10 | step=6 r=2 c=3 g[r][c]=12 | Visit g[2][3] = 12 (cell 6 of 12). |
| 8 | L10 | step=7 r=2 c=2 g[r][c]=11 | Visit g[2][2] = 11 (cell 7 of 12). |
| 9 | L10 | step=8 r=2 c=1 g[r][c]=10 | Visit g[2][1] = 10 (cell 8 of 12). |
| 10 | L10 | step=9 r=2 c=0 g[r][c]=9 | Visit g[2][0] = 9 (cell 9 of 12). |
| 11 | L10 | step=10 r=1 c=0 g[r][c]=5 | Visit g[1][0] = 5 (cell 10 of 12). |
| 12 | L10 | step=11 r=1 c=1 g[r][c]=6 | Visit g[1][1] = 6 (cell 11 of 12). |
| 13 | L10 | step=12 r=1 c=2 g[r][c]=7 | Visit g[1][2] = 7 (cell 12 of 12). |
| 14 | L10 | return=[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.01.2
Rectangular vs jagged
In a rectangular matrix every row has the same length. Java does not force that: a 2D array is an array whose elements are arrays, so rows may have different lengths (a jagged array). Triangular data such as Pascal's triangle fits a jagged array well. Never assume g[r].length == g[0].length unless you built it yourself.
Use g[r].length for the inner loop bound whenever the shape is not guaranteed.
Java
1int[][] rect = new int[3][4]; // 3 rows of 42int[][] jag = new int[3][]; // rows allocated separately3for (int r = 0; r < 3; r++) jag[r] = new int[r + 1]; // lengths 1, 2, 34int total = 0;5for (int[] row : jag) total += row.length; // 6 cells: safe on any shape
10.01.3
Row-major intuition
Memory is one long line, so a matrix has to be laid out in order. Row-major order stores row 0 completely, then row 1, and so on; Java (like C) does this for each row array. Reading along a row therefore touches neighbouring addresses, while reading down a column jumps by a whole row each step. Cache lines make the first pattern several times faster on big matrices.
The simulator counts cache hits and misses for row order against column order.
Java
1long sum = 0;2for (int r = 0; r < R; r++)3for (int c = 0; c < C; c++) sum += g[r][c]; // inner loop over the last index: sequential access4// swapping the two loops reads the same cells in column order: much slower for large R and C
Cache lines: row-major vs column-major traversal
Interactive · edit the inputmemory (row-major, 4 ints per cache line)
0line 0
1line 0
2line 0
3line 0
4line 1
5line 1
6line 1
7line 1
8line 2
9line 2
10line 2
11line 2
12line 3
13line 3
14line 3
15line 3
16line 4
17line 4
18line 4
19line 4
20line 5
21line 5
22line 5
23line 5
24line 6
25line 6
26line 6
27line 6
28line 7
29line 7
30line 7
31line 7
cache (2 lines, LRU)
empty
Setup
A 4×8 matrix is stored row by row in one long run of memory. The CPU fetches memory in cache lines of 4 ints and keeps the 2 most recently used lines.
Step 1 / 34
Java
1int sumRowMajor(int[][] m) { // inner loop walks along a row2int sum = 0;3for (int r = 0; r < m.length; r++)4for (int c = 0; c < m[0].length; c++) sum += m[r][c];5return sum;6}7int sumColumnMajor(int[][] m) { // inner loop jumps down a column8int sum = 0;9for (int c = 0; c < m[0].length; c++)10for (int r = 0; r < m.length; r++) sum += m[r][c];11return sum;12}
Live state
0 hits0 misses
rows
4
cols
8
lineSize
4
cache lines
2
No condition evaluated on this step
Execution trace (dry run table)Show 34 stepsHide
| Step | Line | State | What happens |
|---|---|---|---|
| 1 | L3 | rows=4 cols=8 lineSize=4 cache lines=2 | A 4×8 matrix is stored row by row in one long run of memory. The CPU fetches memory in cache lines of 4 ints and keeps the 2 most recently used lines. |
| 2 | L4 | r=0 c=0 address=0 line=0 hits=0 misses=1 | m[0][0] is memory cell 0, on line 0, which is not cached: a miss. The CPU stalls while the whole line is loaded. |
| 3 | L4 | r=0 c=1 address=1 line=0 hits=1 misses=1 | m[0][1] is memory cell 1, on line 0, which is already in the cache: a hit (fast). |
| 4 | L4 | r=0 c=2 address=2 line=0 hits=2 misses=1 | m[0][2] is memory cell 2, on line 0, which is already in the cache: a hit (fast). |
| 5 | L4 | r=0 c=3 address=3 line=0 hits=3 misses=1 | m[0][3] is memory cell 3, on line 0, which is already in the cache: a hit (fast). |
| 6 | L4 | r=0 c=4 address=4 line=1 hits=3 misses=2 | m[0][4] is memory cell 4, on line 1, which is not cached: a miss. The CPU stalls while the whole line is loaded. |
| 7 | L4 | r=0 c=5 address=5 line=1 hits=4 misses=2 | m[0][5] is memory cell 5, on line 1, which is already in the cache: a hit (fast). |
| 8 | L4 | r=0 c=6 address=6 line=1 hits=5 misses=2 | m[0][6] is memory cell 6, on line 1, which is already in the cache: a hit (fast). |
| 9 | L4 | r=0 c=7 address=7 line=1 hits=6 misses=2 | m[0][7] is memory cell 7, on line 1, which is already in the cache: a hit (fast). |
| 10 | L4 | r=1 c=0 address=8 line=2 hits=6 misses=3 | m[1][0] is memory cell 8, on line 2, which is not cached: a miss. The CPU stalls while the whole line is loaded. |
| 11 | L4 | r=1 c=1 address=9 line=2 hits=7 misses=3 | m[1][1] is memory cell 9, on line 2, which is already in the cache: a hit (fast). |
| 12 | L4 | r=1 c=2 address=10 line=2 hits=8 misses=3 | m[1][2] is memory cell 10, on line 2, which is already in the cache: a hit (fast). |
| 13 | L4 | r=1 c=3 address=11 line=2 hits=9 misses=3 | m[1][3] is memory cell 11, on line 2, which is already in the cache: a hit (fast). |
| 14 | L4 | r=1 c=4 address=12 line=3 hits=9 misses=4 | m[1][4] is memory cell 12, on line 3, which is not cached: a miss. The CPU stalls while the whole line is loaded. |
| 15 | L4 | r=1 c=5 address=13 line=3 hits=10 misses=4 | m[1][5] is memory cell 13, on line 3, which is already in the cache: a hit (fast). |
| 16 | L4 | r=1 c=6 address=14 line=3 hits=11 misses=4 | m[1][6] is memory cell 14, on line 3, which is already in the cache: a hit (fast). |
| 17 | L4 | r=1 c=7 address=15 line=3 hits=12 misses=4 | m[1][7] is memory cell 15, on line 3, which is already in the cache: a hit (fast). |
| 18 | L4 | r=2 c=0 address=16 line=4 hits=12 misses=5 | m[2][0] is memory cell 16, on line 4, which is not cached: a miss. The CPU stalls while the whole line is loaded. |
| 19 | L4 | r=2 c=1 address=17 line=4 hits=13 misses=5 | m[2][1] is memory cell 17, on line 4, which is already in the cache: a hit (fast). |
| 20 | L4 | r=2 c=2 address=18 line=4 hits=14 misses=5 | m[2][2] is memory cell 18, on line 4, which is already in the cache: a hit (fast). |
| 21 | L4 | r=2 c=3 address=19 line=4 hits=15 misses=5 | m[2][3] is memory cell 19, on line 4, which is already in the cache: a hit (fast). |
| 22 | L4 | r=2 c=4 address=20 line=5 hits=15 misses=6 | m[2][4] is memory cell 20, on line 5, which is not cached: a miss. The CPU stalls while the whole line is loaded. |
| 23 | L4 | r=2 c=5 address=21 line=5 hits=16 misses=6 | m[2][5] is memory cell 21, on line 5, which is already in the cache: a hit (fast). |
| 24 | L4 | r=2 c=6 address=22 line=5 hits=17 misses=6 | m[2][6] is memory cell 22, on line 5, which is already in the cache: a hit (fast). |
| 25 | L4 | r=2 c=7 address=23 line=5 hits=18 misses=6 | m[2][7] is memory cell 23, on line 5, which is already in the cache: a hit (fast). |
| 26 | L4 | r=3 c=0 address=24 line=6 hits=18 misses=7 | m[3][0] is memory cell 24, on line 6, which is not cached: a miss. The CPU stalls while the whole line is loaded. |
| 27 | L4 | r=3 c=1 address=25 line=6 hits=19 misses=7 | m[3][1] is memory cell 25, on line 6, which is already in the cache: a hit (fast). |
| 28 | L4 | r=3 c=2 address=26 line=6 hits=20 misses=7 | m[3][2] is memory cell 26, on line 6, which is already in the cache: a hit (fast). |
| 29 | L4 | r=3 c=3 address=27 line=6 hits=21 misses=7 | m[3][3] is memory cell 27, on line 6, which is already in the cache: a hit (fast). |
| 30 | L4 | r=3 c=4 address=28 line=7 hits=21 misses=8 | m[3][4] is memory cell 28, on line 7, which is not cached: a miss. The CPU stalls while the whole line is loaded. |
| 31 | L4 | r=3 c=5 address=29 line=7 hits=22 misses=8 | m[3][5] is memory cell 29, on line 7, which is already in the cache: a hit (fast). |
| 32 | L4 | r=3 c=6 address=30 line=7 hits=23 misses=8 | m[3][6] is memory cell 30, on line 7, which is already in the cache: a hit (fast). |
| 33 | L4 | r=3 c=7 address=31 line=7 hits=24 misses=8 | m[3][7] is memory cell 31, on line 7, which is already in the cache: a hit (fast). |
| 34 | L5 | accesses=32 hits=24 misses=8 hit rate %=75 return=8 | 8 misss and 24 hits (75% hit rate). Both loops do identical arithmetic and are O(rows × cols), but walking along a row uses every int in a loaded line before moving on. Switch the order and compare. |
10.01.4
Index bounds
Reading outside the matrix throws ArrayIndexOutOfBoundsException, so every neighbour access needs a bounds check: 0 <= r < R and 0 <= c < C. Put the check in one helper and test it before indexing, never after. Remember that negative indexes are invalid in Java, unlike in some other languages.
The neighbours animation shows corner and edge cells where some directions fall outside.
Java
1static boolean inBounds(int[][] g, int r, int c) {2return r >= 0 && r < g.length && c >= 0 && c < g[r].length;3}4int v = inBounds(g, r - 1, c) ? g[r - 1][c] : 0; // the cell above, or a default at the border
Neighbours, direction vectors and bounds checks
Interactive · edit the inputgrid · 3 × 4
0123
0
1
1
0
1
1
1
1me
0
1
2
1
1
1
1
Chosen cellValid neighbourWall (blocked)
valid neighbours
none yet
Setup
Cell 5 is row 1, column 1. A direction vector (dr, dc) added to (r, c) gives each neighbour; 4 directions here.
Step 1 / 6
Java
1static final int[] DR4 = {-1, 0, 1, 0}, DC4 = {0, 1, 0, -1}; // up, right, down, left2static final int[] DR8 = {-1, -1, 0, 1, 1, 1, 0, -1}, DC8 = {0, 1, 1, 1, 0, -1, -1, -1}; // adds the diagonals3static List<int[]> neighbors(int[][] g, int r, int c, boolean eight) {4int[] dr = eight ? DR8 : DR4, dc = eight ? DC8 : DC4;5List<int[]> out = new ArrayList<>();6for (int d = 0; d < dr.length; d++) {7int nr = r + dr[d], nc = c + dc[d];8if (nr < 0 || nr >= g.length || nc < 0 || nc >= g[0].length) continue; // outside the grid9if (g[nr][nc] == 0) continue; // wall10out.add(new int[]{nr, nc});11}12return out;13}
Live state
r
1
c
1
No condition evaluated on this step
Execution trace (dry run table)Show 6 stepsHide
| Step | Line | State | What happens |
|---|---|---|---|
| 1 | L4 | r=1 c=1 | Cell 5 is row 1, column 1. A direction vector (dr, dc) added to (r, c) gives each neighbour; 4 directions here. |
| 2 | L10 | d=0 (dr, dc)=(-1, 0) (nr, nc)=(0, 1) | up: (0, 1) is open: a valid neighbour. |
| 3 | L9 | d=1 (dr, dc)=(0, 1) (nr, nc)=(1, 2) | right: (1, 2) is a wall. |
| 4 | L10 | d=2 (dr, dc)=(1, 0) (nr, nc)=(2, 1) | down: (2, 1) is open: a valid neighbour. |
| 5 | L10 | d=3 (dr, dc)=(0, -1) (nr, nc)=(1, 0) | left: (1, 0) is open: a valid neighbour. |
| 6 | L12 | return=3 | 3 valid neighbours out of 4 directions. Corners and edges have fewer neighbours, which is why the bounds check is needed. |
10.01.5
Java int[][]
int[][] is an array of references to int[] rows. new int[R][C] allocates the outer array and R separate row arrays, all zero-filled; each row has its own 16-byte header, so many tiny rows waste memory. Because rows are separate objects, g[r] can be swapped, shared or null. For performance-critical code a single flat int[R * C] indexed by r * C + c has better locality and less overhead.
Copying needs care: clone() on a 2D array is shallow, so copy each row.
Java
1int[][] g = new int[3][4];2int[][] shallow = g.clone(); // shares the row arrays3int[][] deep = new int[g.length][];4for (int r = 0; r < g.length; r++) deep[r] = g[r].clone();5int[] flat = new int[3 * 4];6flat[2 * 4 + 1] = 7; // cell (2, 1) in a flat array7System.out.println(Arrays.deepToString(g)); // prints nested arrays; Arrays.toString would print row references
Practice ladder
Now try it yourself
Easy
- Give the flat index of cell (2, 3) in a matrix with 5 columns
- What is g.length and g[0].length for new int[4][7]?
Medium
- Why can summing a large matrix by columns be several times slower than by rows?
- Write a method that safely reads g[r][c] and returns a default outside the grid
Advanced
- Convert between a flat array and an int[][] and measure the access speed of each on a 4000 × 4000 matrix
Key takeaways
- g[r][c]: r counts rows from the top, c counts columns from the left, both from 0.
- A Java 2D array is an array of row arrays; rows can differ in length.
- Row-major order makes row-wise traversal cache friendly; always check bounds before indexing.