Dynamic Arrays (Vectors/Lists)

Fixed-size arrays are fine when you know the size at compile time. But most problems don't tell you the size ahead of time — they give you N as the first line of input. That's where dynamic arrays come in.

Fixed vs Dynamic

A fixed array (int arr[100]) reserves space at compile time. A dynamic array (vector<int> or Vec<i32>) grows as you add elements. In competitive programming you'll use dynamic arrays 95% of the time.

C++ — vector

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

int main() {
    int n; cin >> n;

    // Read N numbers into a dynamic array
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    // Add one more
    arr.push_back(100);

    cout << "Size: " << arr.size() << "\n";
    cout << "First: " << arr.front() << "\n";
    cout << "Last: " << arr.back() << "\n";
    return 0;
}

Rust — Vec

use std::io::{self, Read};

fn main() {
    let mut input = String::new();
    io::stdin().lock().read_to_string(&mut input).unwrap();
    let nums: Vec<i32> = input
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();

    let n = nums[0] as usize;
    let mut arr: Vec<i32> = nums[1..=n].to_vec();

    arr.push(100);

    println!("Size: {}", arr.len());
    println!("First: {}", arr[0]);
    println!("Last: {}", arr[arr.len() - 1]);
}

💡 Amortized O(1) push_back

Most pushes are O(1) — there's already space. Occasional pushes trigger a reallocation that copies all elements, which is O(N). Averaged over many pushes, each one is O(1). That's "amortized constant time."

Building a Dynamic Array Element by Element

Not all problems give you N first. Sometimes you build the array conditionally. Start empty and push as you go.

C++

vector<int> evens;
for (int x : original) {
    if (x % 2 == 0) evens.push_back(x);
}

Rust

let mut evens: Vec<i32> = Vec::new();
for &x in &original {
    if x % 2 == 0 { evens.push(x); }
}

Common Patterns

Range-based for loop (read-only)

// C++
for (int x : arr) cout << x << " ";

// Rust
for &x in &arr { print!("{} ", x); }

Indexed loop (when you need the index)

// C++
for (int i = 0; i < arr.size(); i++) { ... }

// Rust
for i in 0..arr.len() { ... }

Reserve space upfront

If you know N, call arr.reserve(N) (C++) or Vec::with_capacity(N) (Rust) to avoid reallocations.

Key Takeaways

→ vector<T> (C++) and Vec<T> (Rust) are your default array type.
→ push_back() / push() adds an element; amortized O(1).
→ .size() / .len() gives the current element count.
→ .reserve() / with_capacity() avoids reallocation overhead.
→ Index with [i] — bounds are checked in Rust (panic), unchecked in C++.