Step 1 of 6

Measure first, and fix the algorithm first

Rust is fast by default, and most code is fast enough as written. When something is slow, the time almost always goes to a few hot spots, and the biggest wins come from doing less work, not from clever tricks. The order teams follow: make it work, make it right, then measure, and only then make it fast.

Debug versus release

cargo run and cargo build make a debug build: no optimizations, plus extra checks like integer overflow. It compiles quickly and is great for development, but it's often 10 to 100 times slower than a release build:

$ cargo build --release
$ ./target/release/report big_input.txt

Never judge speed from a debug build, and never benchmark one. Release builds can be tuned in Cargo.toml:

[profile.release]
lto = true            # optimize across crates: slower to build, often a bit faster to run
codegen-units = 1     # fewer parallel compile units: better optimization, slower builds
debug = true          # keep symbols so profilers can show function names

This site runs debug builds, so its tests can't measure fine-grained speed. Instead, the exercises in this module check what matters most: the amount of work. Tests use inputs big enough that a quadratic solution runs past the 2-second time limit, while a linear one finishes in milliseconds, even unoptimized. Other exercises check for allocations and clones with rules.

Big-O beats micro-optimization

Big-O describes how the work grows with the input size n. For n = 100_000:

No compiler flag turns ten billion steps into a hundred thousand. The most common O(n²) at work hides in one innocent line: Vec::contains inside a loop.

use std::collections::HashSet;

// O(n * m): for every wanted id, scan the whole stock list.
fn missing_slow(wanted: &[u32], in_stock: &[u32]) -> Vec<u32> {
    wanted.iter().filter(|id| !in_stock.contains(id)).copied().collect()
}

// O(n + m): build a set once, then each lookup is O(1).
fn missing_fast(wanted: &[u32], in_stock: &[u32]) -> Vec<u32> {
    let stock: HashSet<u32> = in_stock.iter().copied().collect();
    wanted.iter().filter(|id| !stock.contains(id)).copied().collect()
}

fn main() {
    let wanted = [3, 8, 15, 42];
    let in_stock = [42, 8, 7];
    println!("{:?}", missing_slow(&wanted, &in_stock));
    println!("{:?}", missing_fast(&wanted, &in_stock));
}

[3, 15]
[3, 15]

Same answer. With 100,000 orders and 100,000 stock items, the slow version does ten billion comparisons; the fast one does about 200,000 hash operations. For a dozen items, though, the Vec is fine (hashing has a cost too). Big-O matters when n can grow.

Choosing a collection

Common mistakes

• Optimizing without measuring: you'll speed up code that wasn't slow and make it harder to read.
• Sorting inside a loop, or calling .contains on a Vec inside a loop: each turns a linear job into a quadratic one.
• Reaching for a HashMap for five items: a small Vec or array is simpler and often faster.

Your task

has_duplicates compares every pair of ids, which is O(n²); with 100,000 ids it blows the time limit. Make it O(n) with a HashSet: remember that insert returns false when the value was already there. (Sorting a copy and comparing neighbours, O(n log n), would also pass.)

Challenge 2

count_known counts how many words appear in a dictionary, but it calls dictionary.contains for every word: O(words × dictionary). Put the dictionary into a HashSet<&str> first (no need to copy the strings: the set can hold the borrowed &strs).

Challenge 3

A classic interview problem, done in O(n). Write has_pair_with_sum(values, target): is there a pair of values at two different positions that adds up to target? Walk the list once, keeping a HashSet of the values seen so far; for each value v, check whether target - v is already in the set. (Nested loops would time out on the 100,000-value test.)

Next: Borrow, don't clone