Arrays

An array stores elements of the same type in one contiguous block of memory. That one fact explains almost every strength and weakness of arrays. If the first element starts at address base, and each element occupies size bytes, then element i starts at:

base + i * size

The machine does not need to walk through earlier elements to reach arr[i]; it computes the address directly. This is why indexed access is O(1). The price is that the block is physically ordered: inserting or deleting in the middle means moving elements to keep the sequence compact.

Conceptually, an array is both a storage layout and a data structure interface. The storage layout says “values live next to each other.” The interface usually supports indexed access, traversal, search, insertion, deletion, and sometimes resizing. Only indexed access is automatically fast. Searching for a value and changing the middle of the sequence still require scanning or shifting.

An abstract data type (ADT) describes the operations and rules visible to a caller, independently of storage. The caller sees the array’s logical state—its active sequence of values—while the implementation maintains physical state such as an allocation, capacity, and unused slots. A representation invariant is the condition connecting those views; every operation may assume it on entry and must restore it before returning.

When n is the number of active elements, O(f(n)) is an asymptotic upper bound on growth, while Theta(f(n)) is a matching upper and lower order. Theta(1) work does not grow with n; Theta(n) work grows proportionally with it. These symbols compare growth rates, not exact running times: two constant-time operations can still require different numbers of instructions.

Setup

In C, declaring an array fixes its element type and physical capacity:

int marks[5];                         /* declared, values uninitialized */
int scores[5] = {80, 75, 90, 60, 88}; /* declared and initialized */

For array implementations, always distinguish:

• capacity: how many slots physically exist
• size: how many slots currently contain meaningful values

Traversal should visit 0 through size - 1, not the whole capacity. Insertion is valid only when size < capacity. Deletion reduces size; it does not need to erase the old value beyond the active range.

Array Traversal

Traversing an array is a sequential scan over contiguous memory:

#include <stdio.h>

void print_array(const int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int linear_search(const int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

Traversal is O(n) because every active element is visited once. Accessing a known index is O(1), but finding a value without additional structure is still O(n).

Addresses

For a 1D array A, the address of A[i] is:

address(A[i]) = base(A) + i * sizeof(element)

For an array indexed from lower to upper instead of from zero:

address(A[i]) = base(A) + (i - lower) * sizeof(element)

C uses zero-based indexing and does not check bounds at runtime. arr[n] is not the last element; it is one past the last valid element. Reading or writing it is undefined behavior.

int safe_get(const int arr[], int n, int index, int *out) {
    if (index < 0 || index >= n) {
        return 0;
    }
    *out = arr[index];
    return 1;
}

Bounds checks are O(1). They do not change the asymptotic cost of indexed access, but they often decide whether the program is correct.

Updates

Appending at the end is O(1) if unused capacity remains. Inserting at the front or middle is O(n) because elements must shift right:

int array_insert(int arr[], int *n, int capacity, int at, int value) {
    if (*n == capacity || at < 0 || at > *n) {
        return 0;
    }
    for (int i = *n; i > at; i--) {
        arr[i] = arr[i - 1];
    }
    arr[at] = value;
    (*n)++;
    return 1;
}

int array_delete(int arr[], int *n, int at) {
    if (at < 0 || at >= *n) {
        return 0;
    }
    for (int i = at; i < *n - 1; i++) {
        arr[i] = arr[i + 1];
    }
    (*n)--;
    return 1;
}

The shift direction matters. During insertion, shift from the end toward the insertion index so values are not overwritten before being copied. During deletion, shift from the deleted index toward the end.

Ordered Arrays

If an array is kept sorted, searching can improve from linear search to binary search: O(log n). Insertion, however, still costs O(n) because even after finding the correct position, values must shift.

int lower_bound(const int arr[], int n, int value) {
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < value) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

int sorted_insert(int arr[], int *n, int capacity, int value) {
    if (*n == capacity) {
        return 0;
    }
    int at = lower_bound(arr, *n, value);
    return array_insert(arr, n, capacity, at, value);
}

Sorted arrays are excellent for repeated search and range queries, but expensive for frequent insertion and deletion.

Dynamic Arrays

The experiment below makes the shift rules visible. Try inserting at the front, middle, and end; then switch to deletion and compare the direction in which unread data must move.

A static array cannot grow after declaration. A dynamic array grows by allocating a larger block, copying the old elements, and freeing the old block. This is the idea behind vectors and array lists.

The compact sketch below shows the fields and the basic growth idea, but it is not safe when allocation fails: initialization does not check malloc, and ia_push overwrites the only data pointer with the result of realloc. Read it as a first look at the representation, not as code to copy into a real program. The checked ia_reserve routine in Resizing and ia_push_checked in Failure-Safe Growth show how to preserve the old array when memory cannot be obtained.

#include <stdlib.h>

typedef struct {
    int *data;
    int size;
    int capacity;
} IntArray;

void ia_init(IntArray *a) {
    a->capacity = 4;
    a->size = 0;
    a->data = malloc(a->capacity * sizeof(int));
}

void ia_push(IntArray *a, int value) {
    if (a->size == a->capacity) {
        a->capacity *= 2;
        a->data = realloc(a->data, a->capacity * sizeof(int));
    }
    a->data[a->size++] = value;
}

void ia_free(IntArray *a) {
    free(a->data);
    a->data = NULL;
    a->size = 0;
    a->capacity = 0;
}

An occasional resize costs O(n), but doubling capacity makes push amortized O(1) over a long sequence of insertions. Growing by a constant amount, such as 10 slots each time, would copy too often and produce O(n^2) total work across n appends.

Resizing

realloc may extend the same block in place, or it may allocate a new block, copy values, free the old block, and return a new pointer. Use a temporary pointer so failed allocation does not lose the old array:

int ia_reserve(IntArray *a, int new_capacity) {
    if (new_capacity <= a->capacity) {
        return 1;
    }
    int *new_data = realloc(a->data, new_capacity * sizeof(int));
    if (new_data == NULL) {
        return 0;
    }
    a->data = new_data;
    a->capacity = new_capacity;
    return 1;
}

A dynamic array owns its backing buffer. Whoever calls ia_init must eventually call ia_free. Forgetting this leaks memory; freeing twice corrupts memory.

2D Arrays

A 2D array represents a rectangular table. In C, A[ROWS][COLS] is stored in row-major order: all of row 0, then all of row 1, and so on. Element A[i][j] is stored at offset:

i * COLS + j

#define MAX_ROWS 10
#define MAX_COLS 10

void fill_matrix(int A[MAX_ROWS][MAX_COLS], int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            A[i][j] = i * cols + j;
        }
    }
}

Accessing A[i][j] is O(1), but inserting or deleting rows and columns requires shifting many cells.

void insert_row(int A[MAX_ROWS][MAX_COLS], int *rows, int cols,
                int at, const int new_row[]) {
    for (int i = *rows; i > at; i--) {
        for (int j = 0; j < cols; j++) {
            A[i][j] = A[i - 1][j];
        }
    }
    for (int j = 0; j < cols; j++) {
        A[at][j] = new_row[j];
    }
    (*rows)++;
}

void delete_row(int A[MAX_ROWS][MAX_COLS], int *rows, int cols, int at) {
    for (int i = at; i < *rows - 1; i++) {
        for (int j = 0; j < cols; j++) {
            A[i][j] = A[i + 1][j];
        }
    }
    (*rows)--;
}

void insert_col(int A[MAX_ROWS][MAX_COLS], int rows, int *cols,
                int at, const int new_col[]) {
    for (int i = 0; i < rows; i++) {
        for (int j = *cols; j > at; j--) {
            A[i][j] = A[i][j - 1];
        }
        A[i][at] = new_col[i];
    }
    (*cols)++;
}

void delete_col(int A[MAX_ROWS][MAX_COLS], int rows, int *cols, int at) {
    for (int i = 0; i < rows; i++) {
        for (int j = at; j < *cols - 1; j++) {
            A[i][j] = A[i][j + 1];
        }
    }
    (*cols)--;
}

Column operations are often less cache-friendly than row operations because they jump across rows instead of moving through consecutive memory.

Matrix Layout

C stores 2D arrays in row-major order. Some languages use column-major order. The logical matrix may be the same, but traversal performance changes.

/* Cache-friendly in C */
for (int i = 0; i < rows; i++)
    for (int j = 0; j < cols; j++)
        sum += A[i][j];

/* Less cache-friendly in C */
for (int j = 0; j < cols; j++)
    for (int i = 0; i < rows; i++)
        sum += A[i][j];

Both loops are O(rows * cols), but the first usually runs faster because it reads consecutive memory.

Matrix Forms

C can represent a matrix as an array of row pointers:

int **matrix = malloc(rows * sizeof(int *));
for (int i = 0; i < rows; i++) {
    matrix[i] = malloc(cols * sizeof(int));
}

This is more flexible than int A[ROWS][COLS], but rows may live in different memory blocks. A flattened matrix keeps a single contiguous block:

int get_flat(const int data[], int cols, int i, int j) {
    return data[i * cols + j];
}

When most values are zero, dense matrices waste memory. A sparse matrix can store only non-zero entries:

typedef struct {
    int row;
    int col;
    int value;
} Entry;

This saves memory but makes lookup slower unless the entries are sorted or indexed.

Array Hazards

• Mixing up size and capacity
• Reading arr[n] instead of arr[n - 1]
• Shifting in the wrong direction during insertion
• Forgetting to check capacity before insertion
• Losing the old pointer when realloc fails
• Assuming int ** has the same memory layout as int A[ROWS][COLS]

Array Costs

Array Practice

1. Implement insertion and deletion in a 1D array with explicit size and capacity.
2. Trace the array [10, 20, 30, 40, 50] after inserting 99 at index 2, showing every shift.
3. Implement row insertion and column deletion for a matrix.
4. Explain why A[i][j] is O(1) but inserting a column is not.

Array Invariant

For a resizable array, the fields are meaningful only together. A valid state maintains:

0 <= size <= capacity
capacity == 0 implies data == NULL
capacity > 0 implies data points to capacity contiguous elements
indices [0, size) contain the logical sequence
indices [size, capacity) are spare storage

The half-open range [0, size) is important. A value left physically in data[size] after deletion is not part of the array. Conversely, an index may lie inside the allocation but outside the logical sequence. Bounds for access and bounds for insertion are therefore different:

access or deletion: 0 <= index < size
insertion:          0 <= index <= size

Checking this invariant after every mutation catches size changes that were forgotten, capacity changes committed before allocation succeeded, and writes into the first unavailable slot.

Failure-Safe Growth

Growth should finish allocation before publishing new state. ia_reserve already protects the old pointer with a temporary variable; a checked push can build on that guarantee:

#include <limits.h>

int ia_push_checked(IntArray *a, int value) {
    if (a->size == a->capacity) {
        int next_capacity = 4;
        if (a->capacity > 0) {
            if (a->capacity > INT_MAX / 2) {
                return 0;
            }
            next_capacity = a->capacity * 2;
        }
        if (!ia_reserve(a, next_capacity)) {
            return 0;
        }
    }

    a->data[a->size] = value;
    a->size++;
    return 1;
}

On failure, size, capacity, and every existing element remain unchanged. Production code should use size_t for sizes and verify that new_capacity * sizeof *data cannot overflow before calling an allocator.

Successful realloc may move the block. Any pointer to an old element, such as &a->data[3], may then dangle even though index 3 is still valid. Preserve indices across operations that may grow the array; recompute element addresses afterward.

Vector Reference

The earlier fragments isolate individual ideas. This complete C17 vector combines checked access, geometric growth, insertion, deletion, optional shrinking, cleanup, and invariant checks behind one reusable interface. An operation that cannot allocate leaves every existing element and all published metadata unchanged.

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} IntVector;

static bool vector_valid(const IntVector *vector) {
    if (vector == NULL || vector->size > vector->capacity) {
        return false;
    }
    if (vector->capacity == 0) {
        return vector->data == NULL;
    }
    return vector->data != NULL;
}

static void vector_init(IntVector *vector) {
    vector->data = NULL;
    vector->size = 0;
    vector->capacity = 0;
}

static void vector_destroy(IntVector *vector) {
    free(vector->data);
    vector_init(vector);
}

static bool vector_reserve(IntVector *vector, size_t requested) {
    assert(vector_valid(vector));
    if (requested <= vector->capacity) {
        return true;
    }
    if (requested > SIZE_MAX / sizeof *vector->data) {
        return false;
    }

    int *new_data = realloc(vector->data,
                            requested * sizeof *vector->data);
    if (new_data == NULL) {
        return false;
    }

    vector->data = new_data;
    vector->capacity = requested;
    assert(vector_valid(vector));
    return true;
}

static bool vector_ensure_room(IntVector *vector) {
    if (vector->size < vector->capacity) {
        return true;
    }

    size_t next = vector->capacity == 0 ? 4 : vector->capacity * 2;
    if (next < vector->capacity) {
        return false;
    }
    return vector_reserve(vector, next);
}

static bool vector_insert(IntVector *vector, size_t index, int value) {
    assert(vector_valid(vector));
    if (index > vector->size || !vector_ensure_room(vector)) {
        return false;
    }

    for (size_t i = vector->size; i > index; i--) {
        vector->data[i] = vector->data[i - 1];
    }
    vector->data[index] = value;
    vector->size++;
    assert(vector_valid(vector));
    return true;
}

static bool vector_push(IntVector *vector, int value) {
    return vector_insert(vector, vector->size, value);
}

static bool vector_get(const IntVector *vector, size_t index, int *out) {
    assert(vector_valid(vector));
    if (index >= vector->size || out == NULL) {
        return false;
    }
    *out = vector->data[index];
    return true;
}

static bool vector_set(IntVector *vector, size_t index, int value) {
    assert(vector_valid(vector));
    if (index >= vector->size) {
        return false;
    }
    vector->data[index] = value;
    return true;
}

static bool vector_erase(IntVector *vector, size_t index, int *removed) {
    assert(vector_valid(vector));
    if (index >= vector->size) {
        return false;
    }
    if (removed != NULL) {
        *removed = vector->data[index];
    }

    for (size_t i = index + 1; i < vector->size; i++) {
        vector->data[i - 1] = vector->data[i];
    }
    vector->size--;

    if (vector->capacity > 4 &&
        vector->size <= vector->capacity / 4) {
        size_t smaller = vector->capacity / 2;
        int *new_data = realloc(vector->data,
                                smaller * sizeof *vector->data);
        if (new_data != NULL) {
            vector->data = new_data;
            vector->capacity = smaller;
        }
    }

    assert(vector_valid(vector));
    return true;
}

static void vector_print(const IntVector *vector) {
    putchar('[');
    for (size_t i = 0; i < vector->size; i++) {
        printf("%s%d", i == 0 ? "" : ", ", vector->data[i]);
    }
    printf("] size=%zu capacity=%zu\n",
           vector->size, vector->capacity);
}

int main(void) {
    IntVector values;
    vector_init(&values);
    int seed[] = {14, 27, 9, 31};

    for (size_t i = 0; i < sizeof seed / sizeof seed[0]; i++) {
        if (!vector_push(&values, seed[i])) {
            vector_destroy(&values);
            return EXIT_FAILURE;
        }
    }
    if (!vector_insert(&values, 2, 99) ||
        !vector_set(&values, 0, 15)) {
        vector_destroy(&values);
        return EXIT_FAILURE;
    }
    vector_print(&values);

    int removed;
    int first;
    if (!vector_erase(&values, 1, &removed) ||
        !vector_get(&values, 0, &first)) {
        vector_destroy(&values);
        return EXIT_FAILURE;
    }
    printf("first %d, removed %d\n", first, removed);
    vector_print(&values);

    vector_destroy(&values);
    return EXIT_SUCCESS;
}

The validator is deliberately constant time: it checks the relationships visible in the vector metadata, although C provides no portable way to ask the allocator whether the block really contains capacity elements. Assertions make these checks useful during development; production builds may disable them after tests establish confidence. The resize code never assigns realloc directly to the owned pointer, and failed shrinking is harmless because excess capacity is still a valid state.

Shrink Policy

Deleting an element does not require shrinking capacity. Keeping spare storage is often useful when the array will grow again.

Shrinking on every deletion creates oscillation:

append -> grow -> delete -> shrink -> append -> grow -> ...

A common policy grows when size == capacity and shrinks only when size <= capacity / 4, reducing capacity by half. The gap between the growth and shrink thresholds is hysteresis: alternating near one boundary does not trigger repeated allocations.

Shrinking is still optional. A latency-sensitive program—one in which each operation must finish within a predictable time—may expose an explicit trim operation so ordinary deletion remains predictable.

Jagged Arrays

An array of row pointers does not require equal row lengths. Each row can have its own logical size:

rows[0] -> [4, 8, 2]
rows[1] -> [7]
rows[2] -> [1, 6, 9, 5]

This jagged array is appropriate for irregular data, but it requires separate row allocation, cleanup, and length metadata. It also gives up the single row-major address formula because there is no fixed column count shared by every row.

Use a contiguous flattened matrix when rows are rectangular and row-wise locality matters. Use jagged rows when their different lengths save meaningful space or represent the domain more directly.

Sparse Formats

The Entry structure shown earlier is coordinate format: each non-zero value stores (row, column, value). It is simple to build and serialize. If entries are sorted by row and column, lookup can use binary search, but inserting into the ordered entry array may shift later entries.

Compressed sparse row (CSR) separates the fields into three arrays:

• values: stored non-zero values in row order;
• columns: the column of each stored value;
• row_start: the starting offset of every row, plus one final end offset.

For

[ 0 0 8 0 ]
[ 5 0 0 7 ]
[ 0 0 0 0 ]

the CSR representation is:

values    = [8, 5, 7]
columns   = [2, 0, 3]
row_start = [0, 1, 3, 3]

Row r occupies indices row_start[r] through row_start[r + 1] - 1. CSR makes row traversal compact and fast, but arbitrary insertion may move many later entries. Coordinate format is usually easier during construction; CSR is often better after the sparse structure becomes stable.

Array Layouts

The operation pattern matters more than one isolated complexity value. Contiguous storage combines low per-element overhead with strong cache locality, while flexible representations add metadata to avoid storing unused positions.

Growth Accounting

“A push is amortized constant time” does not mean that every push is cheap. It means that an expensive resize happens rarely enough that the average cost over a whole sequence stays bounded.

Suppose an empty vector starts with capacity 4 and doubles whenever it is full. Appending ten values produces this trace:

There are ten ordinary writes and twelve copies caused by growth. More generally, the resize copies form a geometric sum:

4 + 8 + 16 + ... + largest completed capacity

That sum is less than twice its largest term. After n pushes, the total number of copied elements is therefore O(n), so the total work is O(n) and the amortized work per push is O(1).

Contrast this with growing by four slots each time. The copies would be:

4 + 8 + 12 + ... + about n

This arithmetic series totals Theta(n^2). The growth factor is not a small implementation detail; it changes the cost of a long workload.

The factor also changes memory behavior. Doubling performs fewer reallocations but may leave almost half of the allocation unused immediately after growth. A factor such as 1.5 wastes less spare space but grows more often. Libraries choose different factors because allocation overhead, memory limits, and latency requirements differ. Whichever factor is chosen, integer overflow must be checked before computing the next capacity or the byte count.

Amortized analysis is a promise about a sequence, not a worst-case latency promise for one call. A real-time loop that cannot tolerate one O(n) pause should reserve enough space before the loop or use a representation whose individual insertion cost is bounded differently.

Bulk Insertion

Inserting one value creates one gap. Inserting count values should create the entire gap once, not call single-element insertion repeatedly. For a vector with

[10, 20, 30, 40], size = 4

inserting [7, 8, 9] at index 2 proceeds as follows:

reserve space for 7 elements
move [30, 40] three positions right
copy [7, 8, 9] into the gap
publish size = 7

[10, 20, 7, 8, 9, 30, 40]

Moving the suffix once costs Theta(size - index). Repeated single insertion would shift some of that suffix again for every new value.

The difficult case is aliasing: the source values may already be inside the same vector. For example, a caller may ask to insert the first three elements back into the middle. Growth could invalidate the source pointer, while shifting could overwrite source values that have not yet been copied. The interface must either forbid overlap explicitly or define snapshot semantics: the inserted values are those visible when the call began.

This straightforward version implements snapshot semantics. It allocates the snapshot before changing the vector, so any allocation failure leaves the vector untouched. memmove is used for the overlapping shift; memcpy is safe for the final copy because the snapshot is a separate allocation.

#include <string.h>

static bool vector_insert_all(IntVector *vector, size_t index,
                              const int source[], size_t count) {
    assert(vector_valid(vector));
    if (index > vector->size ||
        (source == NULL && count != 0) ||
        count > SIZE_MAX - vector->size ||
        count > SIZE_MAX / sizeof *source) {
        return false;
    }
    if (count == 0) {
        return true;
    }

    int *snapshot = malloc(count * sizeof *snapshot);
    if (snapshot == NULL) {
        return false;
    }
    memcpy(snapshot, source, count * sizeof *snapshot);

    size_t needed = vector->size + count;
    size_t capacity = vector->capacity == 0 ? 4 : vector->capacity;
    while (capacity < needed) {
        if (capacity > SIZE_MAX / 2) {
            capacity = needed;
            break;
        }
        capacity *= 2;
    }
    if (!vector_reserve(vector, capacity)) {
        free(snapshot);
        return false;
    }

    memmove(&vector->data[index + count],
            &vector->data[index],
            (vector->size - index) * sizeof *vector->data);
    memcpy(&vector->data[index], snapshot,
           count * sizeof *vector->data);
    vector->size = needed;
    free(snapshot);
    assert(vector_valid(vector));
    return true;
}

An optimized implementation can avoid the snapshot when it can prove that source and destination do not overlap, but the proof and the failure contract become more complicated. Begin with a clear, testable contract; optimize only after measuring a workload that benefits.

Address Stability

An index names a logical position. A pointer names one physical address. These remain equivalent only while the backing allocation stays in place and earlier elements are not shifted.

This distinction prevents a common bug:

int *chosen = &vector.data[2];
vector_push(&vector, 99); /* may reallocate */
printf("%d\n", *chosen); /* chosen may now dangle */

If the client wants “the element currently at position 2,” store the index and check it again after mutations. If the client wants the identity of one logical record even while positions change, an array index alone is not a stable identity. Store stable IDs in the elements, maintain an ID-to-index map, or choose a representation with an explicit handle contract.

Even an index can become semantically stale after insertion or deletion. After inserting at index 0, the old value at index 2 moves to index 3. The integer 2 is still within bounds, but it names a different value. Valid memory and correct meaning are separate concerns.

Capacity Planning

Repeated growth is unnecessary when the final size is approximately known. Reserving once before reading 100,000 records avoids intermediate copies and makes allocation failure occur before partial ingestion:

if (!vector_reserve(&records, expected_count)) {
    /* records is unchanged */
}

Capacity can also be part of a service limit. If input claims to contain billions of elements, blindly reserving that amount turns malformed data into excessive memory use. Validate the requested logical size against both arithmetic limits and a domain-specific maximum.

When elements are records, layout affects traversal. An array of structures keeps every record together:

typedef struct {
    int id;
    double score;
    unsigned char active;
} Student;

Student students[1000];

A structure of arrays keeps fields separately:

ids[]     = ...
scores[]  = ...
active[]  = ...

The first layout is convenient when operations use all fields of one student. The second can be more compact in the cache when a hot loop reads only scores. Both are arrays; the useful choice follows the access pattern. Performance-sensitive programs often gain more from contiguous storage and reserving once than from replacing a simple representation with a complicated one.

Reference Testing

Boundary examples test individual rules. A reference model tests long interactions among rules. For an integer vector, a deliberately simple fixed-capacity array can act as the oracle for randomly generated operations:

1. Start both representations empty.
2. Randomly choose push, insert, erase, get, or set.
3. Apply the operation to both, including invalid indices.
4. Compare success status, logical size, and every active value.
5. Check vector_valid after every step.

Bias generation toward sizes around 0, 1, capacity - 1, capacity, and the shrink threshold. Those are the state boundaries where most mistakes live. Keep the random seed when a failure occurs so the exact operation sequence can be replayed.

Allocation failure needs a controlled allocator rather than hope. Configure the test allocator to fail on allocation number k, rerun the same operation for every meaningful k, and verify the promised failure state. This distinguishes a merely checked return value from a genuinely transactional mutation.

For C code, run the same tests with address and undefined-behavior sanitizers. A value comparison can pass even after an out-of-bounds write happens to land in unused capacity; a sanitizer detects the invalid access itself.

Array Validation

Test the representation, not only printed values. Start with an empty vector, then exercise a singleton, insertion at indices 0 and size, deletion at both boundaries, repeated growth, deletion across a shrink threshold, and invalid indices. Force allocation failure in a test allocator and confirm that size, capacity, pointer, and existing values remain unchanged. If client code keeps an element address across a possible resize, a sanitizer-backed test should expose that invalid assumption.

When designing an array-backed interface, decide which indices are valid for reading and insertion, whether order is maintained, who owns the allocation, which calls invalidate element pointers, how capacity grows or shrinks, and what state remains after failure. These choices are part of the interface even when they do not appear in asymptotic tables.

Array Challenges

Array Invariants

1. Explain why size <= capacity is necessary and why every index from size through capacity - 1 is outside the logical sequence.

Capacity Trace

2. Trace alternating push and delete operations near separate grow and shrink thresholds. Record size, capacity, and every allocation.

Array Operations

3. Write a debug function that verifies every part of the dynamic-array invariant.
4. Add ia_insert and ia_delete with status returns and failure-safe size updates.
5. Allocate and release a jagged array whose row lengths are supplied at runtime.

Growth Policy

6. Compare automatic shrinking with an explicit trim operation for a queue of latency-sensitive requests.

CSR Conversion

7. Convert sorted coordinate entries into CSR and reconstruct every matrix row from the result. Reject duplicate or out-of-range coordinates without corrupting the destination.

Vector Variants

8. Implement vector_insert_all with well-defined behavior when the source overlaps the vector’s current allocation.
9. Build a generic vector that stores elements of a caller-supplied size. Decide whether it copies values or stores pointers, then document ownership and destruction.
10. Implement a circular dynamic array with amortized constant-time insertion at both ends.
11. Add small-buffer optimization: keep the first eight integers inside the vector object, then migrate safely to dynamic storage when the ninth arrives.