Arrays & Vectors

Arrays store same-type elements in contiguous memory, enabling constant-time indexing and cache-friendly traversal.

What to understand

Memory layout
Index-based access
Insertion and deletion shifts
std::array versus std::vector

Remember this

1Random access is O(1)
2Middle insertion is O(n)
3vector grows dynamically
4Contiguous storage improves locality

Detailed notes

An array maps index i to an address using base + i × element-size. This arithmetic explains O(1) random access and why all elements must have a fixed-size representation.

std::vector adds a size and capacity around a dynamic array. When capacity is exhausted it allocates a larger block and moves elements, making an individual growth operation O(n) but a sequence of appends O(1) amortised per append.

How it works

1Validate index boundaries before access.
2Shift the suffix right before middle insertion.
3Shift the suffix left after deletion.
4Reserve capacity when approximate final size is known.

Worked trace

Insert 25 at index 2

[10, 20, 30, 40]

1Increase logical size from 4 to 5.
2Shift 40 from index 3 to 4.
3Shift 30 from index 2 to 3.
4Write 25 at the opened index 2.

Result: [10, 20, 25, 30, 40] · three writes · O(n) worst case

Where it is used

Dense tables and matrices
Heap and adjacency-matrix storage
Buffers requiring fast traversal and indexing

Common mistakes

Reading or writing outside bounds
Keeping pointers or iterators across vector reallocation
Using repeated front insertion on a vector

Complexity analysis

Operation	Best	Average	Worst	Extra space
Index access	O(1)	O(1)	O(1)	O(1)
Search	O(n)	O(n)	O(n)	O(1)
Append to vector	O(1)	O(1) amortized	O(n)	O(1)
Middle insert/delete	O(n)	O(n)	O(n)	O(1)

C++ implementation

C++17 reference

Core vector operations

std::vector provides contiguous dynamic storage. Insertion in the middle shifts the suffix.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> values{10, 20, 30};
    values.push_back(40);                 // amortized O(1)
    values.insert(values.begin() + 1, 15); // O(n)
    values.erase(values.begin() + 2);      // O(n)

    for (int value : values) cout << value << ' ';
    cout << "\nSize: " << values.size() << '\n';
}

13 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.

End-of-topic practice

Turn arrays & vectors into working C++.

The idea is fresh—use it now. Run visible cases, inspect failures, and then submit against hidden tests.

Browse the full arena

Practice 01Foundation

Rotate in place

Rotate a vector right by k positions without allocating another vector.

Target · O(n) time, O(1) extra Attempt in C++

Practice 02Foundation

Best contiguous sum

Find the maximum sum of a non-empty contiguous subarray, including when every value is negative.

Target · O(n) time, O(1) extra Attempt in C++