Rust Built-In Time Complexity: The Interview Cheat Sheet

Rust gives you a small, well-designed standard library. Six collections cover every interview scenario. The trap is not that you don't know they exist. The trap is not knowing the time complexity of each operation, and then stepping on the usize landmine right as your interviewer is watching.

The Six Collections You'll Actually Use

Collection	When to reach for it
`Vec<T>`	Default sequence, stack, almost everything
`VecDeque<T>`	BFS queue, sliding window with pop_front
`HashMap<K, V>`	Frequency counts, memoization, grouping
`BTreeMap<K, V>`	Sorted keys, range queries, floor/ceiling lookups
`BinaryHeap<T>`	Top-k elements, Dijkstra, max-heap by default
`HashSet<T>` / `BTreeSet<T>`	Dedup, cycle detection, set operations

LinkedList<T> exists. Don't use it. Cache locality destroys any theoretical advantage, and arbitrary O(1) deletion requires holding a CursorMut, which is still an unstable API. Use VecDeque instead. The Rust team knows. They left LinkedList in as a cautionary tale.

Vec Is O(n) in the Middle. Plan Around That.

Vec<T> backs roughly half the solutions you'll write in Rust. Every push doubles capacity when the buffer is full, giving you O(1) amortized append. Everything else that touches the interior is linear.

The operation that bites candidates most is remove(i): it shifts every element after index i left, making it O(n). If you don't need ordering, use swap_remove(i) instead. It moves the last element into position i and pops, making removal O(1). The order of remaining elements changes. If that's fine for your problem, you just got a free upgrade.

let mut v = vec![1, 2, 3, 4, 5];
v.remove(1);      // O(n), shifts [3,4,5] left -> [1,3,4,5]
v.swap_remove(1); // O(1), swaps with last   -> [1,5,4]

Operation	Time
`push`	O(1) amortized
`pop`	O(1)
`get(i)` / `v[i]`	O(1)
`insert(i, x)`	O(n)
`remove(i)`	O(n)
`swap_remove(i)`	O(1)
`contains`	O(n)
`sort`	O(n log n) stable
`sort_unstable`	O(n log n) worst case
`binary_search`	O(log n) on sorted slice
`dedup`	O(n) on sorted vec
`retain`	O(n)

sort_unstable uses pattern-defeating quicksort and is consistently faster than sort (TimSort-based) in benchmarks while still guaranteeing O(n log n) worst case. Use it unless you're sorting tuples and stability matters. See how merge sort and quicksort actually compare if you want the full analysis.

binary_search returns Ok(index) on a hit and Err(insertion_point) on a miss. Both are useful. unwrap_or_else(|x| x) gives you the index either way.

For a deeper look at how dynamic arrays amortize resize cost, the dynamic array time complexity breakdown walks through the math.

VecDeque Is What Vec Should Be for Queues

VecDeque<T> is a ring buffer. Push and pop at both ends are O(1) amortized.

Use VecDeque whenever you need BFS. If you use Vec for BFS and call remove(0) on every dequeue, you're paying O(n) per step. A graph with V vertices and E edges goes from O(V+E) to O(V²+E). Your interviewer is watching. The timeout counter is not waiting.

use std::collections::VecDeque;
let mut queue: VecDeque<i32> = VecDeque::new();
queue.push_back(1);
queue.push_back(2);
let front = queue.pop_front(); // O(1), returns Some(1)

Operation	Time
`push_front` / `push_back`	O(1) amortized
`pop_front` / `pop_back`	O(1) amortized
`get(i)`	O(1)
`insert(i, x)`	O(n)
`len`	O(1)

Converting between Vec and VecDeque is O(n). Do it at setup time, not inside your loop.

HashMap Is Fast, Unordered, and Non-Deterministic

Rust's HashMap uses hashbrown internally, a Swiss table implementation with SIMD acceleration. The default hasher is SipHash-1-3, which resists adversarial DoS inputs at the cost of some speed. Average-case lookups, inserts, and deletes are all O(1). Iteration order is random and changes between program runs. Don't rely on it. Seriously.

The entry API is the idiomatic way to handle "insert if absent" and the pattern you will write in nearly every frequency-counting problem.

let mut freq: HashMap<char, usize> = HashMap::new();
for c in s.chars() {
    *freq.entry(c).or_insert(0) += 1;
}

or_insert returns a mutable reference. Dereference and mutate in one statement.

Operation	Time
`insert`	O(1) average
`get`	O(1) average
`remove`	O(1) average
`contains_key`	O(1) average
`entry().or_insert()`	O(1) average
Iteration	O(n), random order

For a detailed explanation of why O(1) lookup works and when it quietly doesn't, see hash map time complexity.

BTreeMap When You Need Sorted Keys or Ranges

BTreeMap stores keys in sorted order using a B-tree (Rust uses B=6 by default). Every operation costs O(log n). According to the official collections documentation, BTreeMap is competitive with HashMap up to around a thousand elements because of cache-friendly node access.

Reach for BTreeMap when you need sorted iteration, a sliding window keyed on a value, or a floor or ceiling lookup. It has range(), first_key_value(), and last_key_value(). None of those exist on HashMap. If you find yourself sorting a HashMap's keys at the start of every iteration, you want BTreeMap.

use std::collections::BTreeMap;
let mut map: BTreeMap<i32, i32> = BTreeMap::new();
map.insert(3, 10);
map.insert(1, 5);
map.insert(2, 7);
// Always sorted: (1,5), (2,7), (3,10)
for (k, v) in &map {
    println!("{}: {}", k, v);
}
// Range query: keys in [1, 3)
for (k, v) in map.range(1..3) {
    println!("{}: {}", k, v);
}

Operation	Time
`insert`	O(log n)
`get`	O(log n)
`remove`	O(log n)
`contains_key`	O(log n)
`range`	O(log n + k)
Iteration	O(n), sorted

BinaryHeap Is a Max-Heap. Reverse Everything for Min.

BinaryHeap<T> is a max-heap. peek() and pop() return the largest element. For Dijkstra, you want the smallest. These are opposite things, and Rust will not warn you when you mix them up.

For a min-heap, wrap every element in std::cmp::Reverse.

use std::collections::BinaryHeap;
use std::cmp::Reverse;

let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
min_heap.push(Reverse(5));
min_heap.push(Reverse(1));
min_heap.push(Reverse(3));
let min_val = min_heap.pop().unwrap().0; // 1

Reverse implements Ord by inverting comparisons. It composes cleanly with tuples: Reverse((cost, node)) gives you a min-priority queue keyed on cost.

Operation	Time
`push`	O(log n)
`pop`	O(log n)
`peek`	O(1)
`len`	O(1)
Build from Vec	O(n)
`into_sorted_vec`	O(n log n)

There is no decrease_key in BinaryHeap. For Dijkstra, use lazy deletion: push (cost, node) tuples and skip entries when you pop a node that has already been finalized. The heap data structure deep dive covers the sift-up and sift-down mechanics if you need the theory.

For top-k elements, push onto a max-heap of size k and compare the root against each new element. O(n log k) total.

HashSet and BTreeSet Follow the Same Rules

HashSet<T> gives O(1) average for insert, contains, and remove. BTreeSet<T> gives O(log n) with sorted iteration.

let a: HashSet<i32> = [1, 2, 3].into_iter().collect();
let b: HashSet<i32> = [2, 3, 4].into_iter().collect();
let inter: HashSet<_> = a.intersection(&b).collect(); // {2, 3}

union, intersection, difference, and symmetric_difference return iterators. Collect into a new set if you need to own the result.

Five Traps That Cost You Points

1. usize underflow

usize is unsigned. Subtracting past zero panics in debug mode and silently wraps in release. This is the kind of thing that looks fine during your walkthrough and explodes the moment you hit a test case with n=0. The interviewer quietly notes it down.

let n: usize = 0;
let _ = n - 1; // panics in debug: attempt to subtract with overflow

Cast to i64 or isize before any arithmetic that might produce a negative intermediate:

let n = v.len() as i64;
let prev = (i as i64) - 1;
if prev >= 0 { ... }

2. f64 has no Ord

f64 implements PartialOrd but not Ord because NaN is not comparable to anything, including itself. You cannot call sort(), use BTreeMap<f64, _>, or push f64 into a BinaryHeap. The compiler will tell you this in a way that feels more accusatory than helpful.

let mut v = vec![3.0_f64, 1.0, 2.0];
v.sort();                                // ERROR: Ord not implemented for f64
v.sort_by(|a, b| a.total_cmp(b));       // OK, stable since Rust 1.62

For problems where the values are guaranteed finite (almost all interview problems), total_cmp is the cleanest fix.

3. String indexing does not compile

Rust strings are UTF-8. One character can be 1 to 4 bytes, so byte offset n is not character n. s[i] is a compile error. Python never warned you. Rust doesn't let it through.

let s = String::from("hello");
let _ = s[0];            // ERROR: cannot index into String
let b = s.as_bytes()[0]; // OK: returns u8, O(1)
let c = s.chars().nth(0); // OK: returns Option<char>, O(n)

If inputs are guaranteed ASCII (which interview problems usually are), as_bytes() is the fast path. If you need repeated char-level random access, collect once into Vec<char> at O(n), then index in O(1).

4. BinaryHeap is max-heap by default

This comes up most painfully on k-th smallest element problems. Every push and pop returns the maximum. Wrap with Reverse<T> for min-heap behavior. Forget this and your Dijkstra will explore the farthest node first, return the wrong answer, and you'll spend ten minutes convinced your algorithm is correct before checking the heap direction.

5. Mutable borrow during graph traversal

The borrow checker blocks the common pattern of reading a neighbor list and mutating visited state when both are behind the same struct reference. You know what you mean. The compiler disagrees and has documentation to back it up. The fix is to clone the neighbor list before recursing.

let neighbors: Vec<usize> = self.graph[node].clone();
for next in neighbors {
    if !self.visited[next] {
        self.dfs(next);
    }
}

Cloning breaks the conflicting borrows. For interview-scale inputs (typically up to 10^5 nodes), the clone cost is negligible.

Rust Built-In Time Complexity: Quick Reference

Collection	Insert	Lookup	Delete	Notes
`Vec`	O(1) amort (end)	O(1)	O(n) / O(1) swap_remove	Use swap_remove when order doesn't matter
`VecDeque`	O(1) amort (both ends)	O(1)	O(1) both ends	BFS queue, sliding window
`HashMap`	O(1) avg	O(1) avg	O(1) avg	Random order, entry API for upserts
`BTreeMap`	O(log n)	O(log n)	O(log n)	Sorted, range queries, floor/ceiling
`HashSet`	O(1) avg	O(1) avg	O(1) avg	Dedup, cycle detection
`BTreeSet`	O(log n)	O(log n)	O(log n)	Sorted set, set intersection
`BinaryHeap`	O(log n)	O(1) peek	O(log n)	Max-heap. Use Reverse for min.
`String`	O(1) push_char	O(n) nth char	N/A	Byte access is O(1) via as_bytes()

Knowing the table is half the work. The other half is producing correct, narrated solutions under pressure. SpaceComplexity runs voice-based mock interviews with Rust-specific follow-ups, then scores your reasoning and edge-case handling in real time.

For a broader look at Rust idioms and collection patterns, the Rust for coding interviews guide covers the entry API, sort variants, and graph traversal in detail.