Contiguous 2D Array Allocation and Pointer Arithmetic

The Two Strategies for Dynamic 2D Arrays

When you need a 2D array whose dimensions are determined at runtime, you have two main options:

1. Allocate one large, continuous block of memory for all rows * cols elements.
2. Allocate an array of pointers, where each pointer then points to a separately allocated row.

Today, we're tackling the first method. The next lesson will cover the second, allowing us to compare them directly.

Method 1: The Single Contiguous Block

The core idea of this method is beautifully simple: if you need a rows x cols grid, you just ask malloc for a single chunk of memory large enough to hold rows * cols elements.

This is the most memory-efficient and often the highest-performance approach. Let's dig into how it works.

As you've just read, the allocation itself is straightforward:

#define ROWS 3
#define COLS 4

// The pointer is a simple 'int*', not 'int**'
int* matrix = malloc(ROWS * COLS * sizeof(int));

if (matrix == NULL) {
    perror("Failed to allocate memory for matrix");
    // Handle error
}

After this call, matrix points to the beginning of a contiguous block of memory large enough for 12 integers. The memory layout is identical to a static 2D array (int static_matrix[ROWS][COLS];), arranged in row-major order.

Accessing Elements: Manual Pointer Arithmetic

Here's the crucial part that interviewers will test you on. Because matrix is of type int*, the compiler has no information about the array's "shape" (its number of columns). Therefore, you cannot use the convenient matrix[i][j] syntax. Doing so will result in a compile-time error.

Instead, you must manually calculate the position of an element (i, j) within the 1D block.

The formula to access the element at matrix[row][col] is:

matrix[row * COLS + col]

Let's break this down:

• row * COLS: This calculates the offset to the beginning of the desired row. For each full row you skip, you advance by COLS elements.
• + col: This adds the final offset to get to the correct column within that row.

For example, to access matrix[1][2] in our 3x4 array:

1. We need to skip the first row (row 0). The offset is 1 * 4 = 4 elements.
2. Then, we move to the 3rd element in the current row (column 2). The offset is + 2.
3. The total offset from the beginning is 4 + 2 = 6. The access is matrix[6].

This mimics exactly what the compiler does behind the scenes for a statically allocated 2D array. With this dynamic method, we are simply doing the compiler's job explicitly.

Putting It All Together: A Full Example

Here is a complete program demonstrating allocation, initialization, access, and deallocation.

#include <stdio.h>
#include <stdlib.h>




#define ROWS 3
#define COLS 4

// Note the function signature: it takes a single pointer.
void print_matrix(int* matrix, int rows, int cols) {
    printf("Matrix contents:\n");
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            // Manual index calculation
            printf("%3d ", matrix[i * cols + j]);
        }
        printf("\n");
    }
}

int main(void) {
    // 1. Allocation
    int* matrix = malloc(ROWS * COLS * sizeof(int));
    if (matrix == NULL) {
        perror("malloc failed");
        return 1;
    }

    // 2. Initialization
    for (int i = 0; i < ROWS; ++i) {
        for (int j = 0; j < COLS; ++j) {
            matrix[i * COLS + j] = i * 10 + j;
        }
    }

    // 3. Usage (passing to a function)
    print_matrix(matrix, ROWS, COLS);

    // 4. Deallocation - simple and clean
    free(matrix);
    matrix = NULL; // Good practice to avoid dangling pointers

    return 0;
}

Notice how clean the allocation and deallocation are: one malloc, one free. This is a significant advantage.

Performance and Trade-offs

This method is a favorite in high-performance and embedded contexts. Let's summarize the pros and cons, which are excellent points to bring up in an interview.

Advantages:

• Cache Efficiency: All the data is packed together. When you access matrix[0][0], the CPU likely prefetches the rest of row 0 and possibly subsequent rows into the cache. This "spatial locality" dramatically speeds up sequential access (like iterating through the matrix).
• Memory Efficiency: There is no overhead for storing an extra array of row pointers. You only allocate memory for the data itself.
• Simple Allocation/Deallocation: A single call to malloc and a single call to free simplify memory management and reduce the risk of leaks from forgetting to free one of many blocks.

Disadvantage:

• Inconvenient Syntax: The matrix[i * COLS + j] syntax is more verbose and slightly more error-prone than the natural matrix[i][j]. A common mistake is to swap ROWS and COLS in the calculation.

One way to mitigate the syntactic inconvenience is with a macro, as suggested in this Stack Overflow answer.

Using a macro can make the code more readable:

#define ELEMENT_AT(m, r, c, cols) (m[(r) * (cols) + (c)])

// Now access becomes cleaner:
ELEMENT_AT(matrix, i, j, COLS) = i * 10 + j;

Conclusion

You've now learned the most performance-oriented method for dynamically allocating a 2D array in C. This technique demonstrates a deep understanding of memory layout and its performance implications—a hallmark of a strong systems programmer.

Key Takeaways:

• Allocation: A 2D array of R rows and C columns can be allocated as a single contiguous block using malloc(R * C * sizeof(type)).
• Pointer Type: The resulting pointer is a single pointer (type*), not a pointer-to-pointer (type**).
• Access: Elements must be accessed using manual pointer arithmetic: array[row * num_cols + col].
• Benefits: This method offers superior cache performance, lower memory overhead, and simpler memory management (one malloc, one free).

In the next lesson, we will explore the second major strategy: using an array of pointers. This will set up a direct comparison, allowing you to articulate the trade-offs between each approach—a classic interview discussion topic.