Dynamic Memory Allocation in C

In the world of C programming, managing memory is like being the architect of your own skyscraper. You can either build on a tiny, pre-allocated plot (the Stack) or claim as much land as you need from the city (the Heap).

Dynamic memory allocation is how you tell the operating system, "I don't know how big this array needs to be yet, but I'll let you know once the input starts rolling in."

You often face constraints like \(N \le 1,000,000\). If you declare int arr[1000000]; inside a function, you’re placing it on the Stack. A million integers take up ~4MB, which is fine: until you realize your recursion depth or other variables push you over the edge, causing a Stack Overflow.

Dynamic allocation moves that data to the Heap, which is usually limited only by the computer's total virtual address space and available RAM. On modern 64-bit systems, this can be hundreds of gigabytes or even terabytes.

The Core Toolkit

malloc (Memory Allocation)

malloc grabs a contiguous block of raw bytes. It doesn't care what you put in them; it just gives you the address.

int *ptr = (int*) malloc(n * sizeof(int));

Note: It contains "garbage" values. Never assume it's zeroed out.

calloc (Contiguous Allocation)

Think of this as malloc’s cleaner sibling. It allocates memory and initializes every bit to zero.

int *ptr = (int*) calloc(n, sizeof(int));

Use this if you need an adjacency list or a frequency array where everything must start at zero.

realloc (Re-allocation)

If your array is full and you need more space, realloc attempts to resize the existing block. If it can't, it finds a new, larger spot, copies your data over, and deletes the old one.

ptr = realloc(ptr, new_size * sizeof(int));

free (De-allocation)

This tells the OS you're done. In a 2-hour contest, you might think, "The OS will clean it up when the program ends anyway." While true, failing to free memory inside a loop (like for multiple test cases) will lead to a Memory Limit Exceeded (MLE).

The "Danger Zone"

There are issues you can encounter with dynamic memory allocation if you are not careful.

Memory Leaks

A leak occurs when you lose the pointer to allocated memory without freeing it first.

while(t--) {
    int *arr = malloc(1000 * sizeof(int));
    // ... do work ...
    // If you don't free(arr) here, you lose 4KB every test case!
}

Dangling Pointers

A dangling pointer is a "ghost" of memory past. It happens when you free a pointer but then try to use it again.

free(ptr);
printf("%d", ptr[0]); // UNDEFINED BEHAVIOR - CRASH OR GARBAGE

The Fix: Immediately set the pointer to NULL after freeing it: free(ptr); ptr = NULL;

The NULL Check

Whenever you ask the system for memory, there is a theoretical chance it says "no" (though rare in CP unless you're actually out of RAM). Dereferencing a NULL pointer is an instant Runtime Error.

int *ptr = malloc(n * sizeof(int));
if (ptr == NULL) {
    // Handle error or exit
    return 1;
}

A Note on nullptr: In C, we use the macro NULL. The keyword nullptr was introduced in C++11 to solve type-safety issues. If you are writing pure C, stick to NULL. If you are using a C++ compiler for CP (which most people do), you can use nullptr.