Allocating Multi-dimensional Arrays in C

allocating-multidimensional-arrays.md

Allocating Multi-dimensional Arrays in C

This gist was inspired by the Geeks for Geeks' writeup How to dynamically allocate a 2D array in C? by Abhay Rathi. It has been formatted to remove interstitial ads, provide a fixed URL for links, and to modify the problem statement to match that which is commonly used in Hackerrank/Grind75/LeetCode/ACM problems where the input must be read from standard input.

Problem

We want to read input from standard input, where the nature of the input is as follows:

• On line 1, $R$: the number of rows, and $C$: the number of columns in a 2D array, space-separated and newline-terminated.
• On lines 2 through $R+1$, the row's columns, space-separated and newline-terminated.
• Each cell (at [row][col]) is guaranteed to be an integer in the input.

One such example input:

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

Note that the size of the 2D array cannot be determined statically, ruling out the use of VLAs.

Solutions

Method 1: Using a single pointer and a 1D array with pointer arithmetic

#include <stdio.h>
#include <stdlib.h>
 
int main(void)
{
    // Get row and column size
    int r,c;
    scanf("%d %d\n",&r,&c);
 
    // Allocate storage for 1D array
    int* ptr = malloc((r * c) * sizeof(int));
 
    // Read in the contents of the array
    for (int i = 0; i < r * c; i++)
        scanf("%d ",&ptr[i]);
 
    // Accessing the array values as if it was a 2D array
    // using pointer arithmetic
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++)
            printf("%d ", ptr[i * c + j]);
        printf("\n");
    }
 
    // Free the storage
    free(ptr);
 
    return 0;
}

Method 2: Using an array of pointers

#include <stdio.h>
#include <stdlib.h>
 
int main(void)
{
    // Get row and column size
    int r,c;
    scanf("%d %d\n",&r,&c);
    
    // Allocate storage
    int* arr[r];
    for (int i = 0; i < r; i++)
        arr[i] = (int*)malloc(c * sizeof(int));
    
    // Read in the contents of the array
    // Note that arr[i][j] is same as *(*(arr+i)+j)
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
        scanf("%d ",&arr[i][j]);
    
    // Accessing the array values
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
        printf("%d ", arr[i][j]);
    
    // Free the storage
    for (int i = 0; i < r; i++)
        free(arr[i]);
    
    return 0;
}

Method 3: Using pointer to a pointer

#include <stdio.h>
#include <stdlib.h>
 
int main(void)
{
    // Get row and column size
    int r,c;
    scanf("%d %d\n",&r,&c);
    
    // Allocate storage
    int** arr = (int**)malloc(r * sizeof(int*));
    for (int i = 0; i < r; i++)
        arr[i] = (int*)malloc(c * sizeof(int));
    
    // Read in the contents of the array
    // Note that arr[i][j] is same as *(*(arr+i)+j)
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
        scanf("%d ",&arr[i][j]); // OR *(*(arr+i)+j)
    
    // Accessing the array
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
        printf("%d ", arr[i][j]);
    
    // Free the storage
    for (int i = 0; i < r; i++)
        free(arr[i]);
    free(arr);
    
    return 0;    
}

Method 4: Using double pointer and one malloc call

#include <stdio.h>
#include <stdlib.h>
 
int main(void)
{
    // Get row and column size
    int r,c;
    scanf("%d %d\n",&r,&c);
    
    // Allocate the storage of double pointers
    int len = sizeof(int *) * r + sizeof(int) * c * r;
    int **arr = (int **)malloc(len);
    
    // Set ptr to pointing to the first element in of 2D array
    int *ptr = (int *)(arr + r);
    
    // for loop to point rows' pointers to appropriate location in 2D array
    for(int i = 0; i < r; i++)
        arr[i] = (ptr + c * i);
    
    // Read in the contents of the array
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            scanf("%d ",&arr[i][j]);
        
    // for loop to print out the contents of the array
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
        printf("%d ", arr[i][j]);
        
    // Free the storage
    free(arr);
    
    return 0;
}

Complexity Analysis

Ignoring internal complexities of the scanf and printf functions:

Method	Time	Space
Using a single pointer and a 1D array with pointer arithmetic	$O(RC)$	$O(RC)$
Using an array of pointers	$O(RC)$	$O(RC)$
Using pointer to a pointer	$O(RC)$	$O(RC)$
Using double pointer and one malloc call	$O(RC)$	$O(RC)$