How is a 2D array int m[R][C] laid out in memory in C, why must a function parameter know the column count C, and how does loop order affect cache misses?

A strong answer

C stores multidimensional arrays in row-major order: one single, flat, contiguous block of R * C elements where all elements of row 0 come first, immediately followed by all elements of row 1, and so on. There are no hidden row pointers. To access m[r][c], the compiler translates the 2D subscript into a 1D element offset using the formula:

address(&m[r][c]) = base_address + (r * C + c) * sizeof(int)

Look closely at that formula: the number of rows R does not appear anywhere in the address calculation, but the number of columns C (the row stride) is multiplied by r! Without knowing C, the compiler cannot know how many elements to skip to get from row 0 to row 1. That is why a function accepting a 2D array can omit the outer dimension void process(int m[][C], int rows) (or in C99, void process(int rows, int cols, int m[rows][cols])), but must know the column width C.

Because a 64-byte CPU cache line holds 16 consecutive 4-byte ints from the same row, iterating row by row (r outer loop, c inner loop) steps through memory sequentially (+4 bytes per step), achieving a 93.75% cache hit rate (15 hits per 16 elements) and triggering the hardware prefetcher. Swapping the loops to iterate column by column (c outer, r inner) jumps by C * 4 bytes on every read—missing the cache on every access when the matrix exceeds L1/L2 cache size and running 5x to 15x slower.

What the interviewer is listening for

• Writes the exact row-major index formula r * C + c and uses it to explain why C (column count) is required in function parameter types.
• Contrasts a true 2D array int m[R][C] (one contiguous block, zero pointer indirection) against a jagged array of pointers int *m[R] (an array of R pointers, each pointing to a separate allocation that may be scattered in RAM).
• Explains the 64-byte cache line impact of row-major ([r][c]) vs column-major ([c][r]) loop nesting.

Common mistakes

• Passing int m[R][C] to a function expecting int **m—a 2D array decays to a pointer to a row int (*)[C], not a pointer to a pointer int **, and casting it causes an immediate crash when the function tries to dereference data integers as 64-bit pointers!
• Allocating a dynamic matrix with R + 1 separate malloc calls instead of one contiguous malloc(R * C * sizeof(int)) buffer.