Arrays and Dynamic Arrays

How arrays are laid out in memory, what each operation costs, and the array techniques — prefix sums, difference arrays, Kadane's algorithm, Dutch National Flag, quickselect and coordinate compression — that recur in later modules.

What you will learn

Prerequisites: Modules 2 and 4.

Concepts

One-dimensional and multidimensional arrays.

Contiguous memory, indexing, row-major layout.

Static arrays versus dynamic arrays.

Traversal, insertion, deletion, update, search.

Resizing and amortized append.

Array rotation, reversal, partitioning, and rearrangement.

Subarrays versus subsequences versus subsets.

Prefix sums, suffix sums, difference arrays, and frequency arrays.

In-place operations and stable versus unstable rearrangement.

Element i of an array of T starting at address base lives at base + i·sizeof(T), which is why indexing is O(1). A 2-D array int g[R][C] is stored row by row (row-major): g[r][c] is at offset r·C + c. A subarray is contiguous; a subsequence keeps order but may skip elements; a subset ignores order. For n elements there are n(n+1)/2 non-empty subarrays but 2ⁿ − 1 non-empty subsequences.

Syntax

vector<int> a = {1, 2, 3, 4};
int x = a[2];            // zero-based index: 3
a[1] = 10;
a.push_back(5);

Complexity

Search unsorted data O(1) amortized Insert/delete at middle O(n log n) typical comparison sort

Example: prefix sums

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Teach the half-open interval convention and prevent off-by-one errors. With prefix[i] meaning “sum of the first i elements”, the sum of [l, r) is prefix[r] − prefix[l], the empty range needs no special case, and the array has n + 1 entries.

Output (CPython 3.13.1): Difference arrays: many range updates, then one pass

Each update is O(1); reconstructing all values is one O(n) prefix pass. Use it when all updates come before any query (offline). For interleaved updates and queries, use a Fenwick or segment tree (Modules 36–37).

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};
    vector<long long> prefix(a.size() + 1, 0);
    for (size_t i = 0; i < a.size(); ++i)
        prefix[i + 1] = prefix[i] + a[i];

    cout << "i      :";
    for (size_t i = 0; i < prefix.size(); ++i) cout << setw(3) << i;
    cout << "\nprefix :";
    for (long long p : prefix) cout << setw(3) << p;
    cout << '\n';
    size_t l = 2, r = 6;
    // Sum of half-open range [l, r)
    long long rangeSum = prefix[r] - prefix[l];
    cout << "sum of a[2..5] = a[2]+a[3]+a[4]+a[5] = 4+1+5+9 = " << rangeSum << '\n';
    cout << "empty range [3, 3) = " << prefix[3] - prefix[3] << '\n';
}

i      :  0  1  2  3  4  5  6  7  8
prefix :  0  3  4  8  9 14 23 25 31
sum of a[2..5] = a[2]+a[3]+a[4]+a[5] = 4+1+5+9 = 19
empty range [3, 3) = 0

from itertools import accumulate

a = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = [0, *accumulate(a)]          # prefix[i] = sum of the first i elements
print("prefix:", prefix)
l, r = 2, 6
print("sum of a[2:6] =", prefix[r] - prefix[l], "| check:", sum(a[l:r]))

prefix: [0, 3, 4, 8, 9, 14, 23, 25, 31]
sum of a[2:6] = 19 | check: 19

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 8;
    vector<long long> diff(n + 1, 0);
    // add v to every index in [l, r)
    auto rangeAdd = [&](int l, int r, long long v) { diff[l] += v; diff[r] -= v; };
    rangeAdd(1, 5, 10);
    rangeAdd(3, 8, 2);
    rangeAdd(0, 2, -1);
    vector<long long> value(n);
    long long run = 0;
    for (int i = 0; i < n; ++i) { run += diff[i]; value[i] = run; }
    cout << "values:";
    for (long long v : value) cout << ' ' << v;
    cout << '\n';
}

values: -1 9 10 12 12 2 2 2

Advanced topics

Kadane's algorithm, maximum product subarray, cyclic sort patterns, Dutch National Flag, quickselect, inversion count, merge-based counting, matrix traversal, sparse matrices, and cache locality.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Kadane keeps the best sum ending at the current index; a negative running sum is never worth extending. All-negative arrays return the largest single element, because cur starts at a[0].

Dutch National Flag maintains the invariant shown in the comment; mid advances only when the element is known to belong in the middle region.

Quickselect partitions like quicksort but recurses into one side only: expected O(n), worst case O(n²) (Module 51 explains why random pivots make the worst case unlikely).

Cache locality: iterating a row-major matrix row by row touches consecutive memory; iterating column by column jumps by C elements each step and can be several times slower for large matrices, with identical O(R·C) complexity (Module 56).

#include <bits/stdc++.h>
using namespace std;

// Kadane: best[i] = max subarray sum ending at i = max(a[i], best[i-1] + a[i])
pair<long long, pair<int, int>> kadane(const vector<int>& a) {
    long long best = a[0], cur = a[0];
    int start = 0, bestL = 0, bestR = 0;
    for (int i = 1; i < (int)a.size(); ++i) {
        if (cur + a[i] < a[i]) { cur = a[i]; start = i; } else cur += a[i];
        if (cur > best) { best = cur; bestL = start; bestR = i; }
    }
    return {best, {bestL, bestR}};
}

// Dutch National Flag: one pass, three regions [0,lo) = 0, [lo,mid) = 1, (hi,n) = 2
void dutchFlag(vector<int>& a) {
    int lo = 0, mid = 0, hi = (int)a.size() - 1;
    while (mid <= hi) {
        if (a[mid] == 0) swap(a[lo++], a[mid++]);
        else if (a[mid] == 1) ++mid;
        else swap(a[mid], a[hi--]);
    }
}

// Quickselect: k-th smallest (0-based), expected O(n)
int quickselect(vector<int> a, int k, mt19937& rng) {
    int l = 0, r = (int)a.size() - 1;
    while (true) {
        if (l == r) return a[l];
        int pivot = a[l + rng() % (r - l + 1)];
        int i = l, lt = l, gt = r;                       // three-way partition around pivot
        while (i <= gt) {
         
…

max subarray sum 6 at [3, 6]
dutch flag: 0 0 0 1 1 1 2 2 2
quickselect k=0..8: 1 2 3 4 5 6 7 8 9
quickselect agrees with sorting on 2000 random arrays

Edge cases and common mistakes

Empty arrays and single elements; ranges where l == r.

Off-by-one with inclusive versus half-open ranges — choose one convention per function and document it.

Overflow of sums: 10⁵ values of 10⁹ need long long.

Erasing from a vector while iterating with an index or iterator.

Tricky interview question: product of array except self

Given a, return out[i] = product of all a[j], j ≠ i, without division, in O(n) time.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Division fails when an element is zero (the second and third inputs). Prefix and suffix products avoid it; the output array doubles as the prefix storage, so the auxiliary space is O(1) beyond the answer.

#include <bits/stdc++.h>
using namespace std;

vector<long long> productExceptSelf(const vector<long long>& a) {
    int n = (int)a.size();
    vector<long long> out(n, 1);
    long long left = 1;
    for (int i = 0; i < n; ++i) { out[i] = left; left *= a[i]; }          // product of a[0..i-1]
    long long right = 1;
    for (int i = n - 1; i >= 0; --i) { out[i] *= right; right *= a[i]; }  // times product of a[i+1..n-1]
    return out;
}

int main() {
    for (auto a : vector<vector<long long>>{{1, 2, 3, 4}, {2, 0, 5, 3}, {0, 4, 0}}) {
        auto r = productExceptSelf(a);
        for (long long x : r) cout << x << ' ';
        cout << '\n';
    }
}

24 12 8 6 
0 30 0 0 
0 0 0

Practice

Easy: rotate an array right by k in place using three reversals.

Medium: count subarrays whose sum equals k (hint: prefix sums + hash map, Module 10).

Hard: count inversions in O(n log n) (Module 18 shows the merge-sort solution).

Quiz

? With `prefix[i]` = sum of the first i elements, how do you get the sum of a[l..r] inclusive?
+ prefix[r+1] − prefix[l] :: Inclusive [l, r] is half-open [l, r+1).
- prefix[r] − prefix[l] :: That is [l, r), excluding a[r].
- prefix[r] − prefix[l−1] :: Breaks at l = 0.
- prefix[r+1] − prefix[l+1] :: Excludes a[l].

? Kadane's algorithm on an all-negative array, starting with `best = cur = a[0]`, returns…
+ the largest (least negative) element :: A single element is the best non-empty subarray.
- 0 :: Only if empty subarrays are allowed.
- the sum of all elements :: That is the smallest sum.
- an error :: It is well defined.

? Which are true of quickselect? (select all that apply)
+ Expected O(n) time with random pivots :: It recurses into one side only.
+ Worst case O(n²) :: Consistently bad pivots.
- It sorts the whole array :: It only places the k-th element.
+ Three-way partitioning handles many duplicates efficiently :: Equal elements are not revisited.