Vectors, strings, and hash maps

This chapter begins Part 2. Part 2 is about data structures and the algorithms that use them. In this chapter you work with the three collections you will use most in Rust: Vec, String, and HashMap.

Before any problem, I spend a few sections on groundwork. First, a way to compare two solutions by how much work they do. Then a look at how each collection stores its data. With that in place, each problem in the rest of the chapter is short, and you can see why each solution is fast.

The problems are grouped by technique, not by topic. A technique is a pattern you can reuse. Two examples are “keep a stack of things not yet matched” and “move two indexes toward each other”. Table 3.1 lists them.

3.1 Counting the work an algorithm does

Two programs can give the same answer and take very different amounts of time. You saw this in chapter 1: the recursive Fibonacci took milliseconds where the loop took nanoseconds. To choose between solutions, you need a way to describe how their running time grows as the input grows.

The usual way is to count the basic steps a program takes for an input of size n. Here n is the length of the array or string. A basic step is something that takes a fixed amount of time, such as comparing two numbers or reading one element.

Consider three ways to answer questions about an array of n numbers:

• Reading the first element takes one step, whatever n is.
• Adding up all the elements takes n steps, one per element.
• Comparing every element with every other element takes about n × n steps.

Big-O notation is a short way to write how the count grows. You keep only the part that grows fastest and drop constant factors. So the three examples above are written O(1), O(n), and O(n²). You read O(n) as “order n”: the time grows in proportion to n.

Table 3.2 shows how different these are once n is large.

A modern processor does roughly a billion simple steps per second. At a million elements, an O(n) solution finishes in about a millisecond. An O(n²) solution takes about a quarter of an hour.

The same notation describes memory. A solution that uses O(n) extra memory stores something for each input element. A solution that uses O(1) extra memory uses a fixed amount, however large the input.

3.2 How a Vec stores its elements

A Vec<T> is a growable array. Its elements sit next to each other in one block of heap memory. The Vec value itself is small. It holds three numbers. The first is a pointer to the block. The second is the number of elements in use, its length. The third is how many elements the block has room for, its capacity. Figure 3.1 shows a vector of four i32 values with room for six.

Because the elements are next to each other, reading v[i] takes one step. The address of element i is the block’s address plus i times the size of one element. The length of the vector does not matter. So indexing a Vec is O(1).

When you push an element and the block is full, the vector needs a bigger block. Figure 3.2 shows what happens.

That copy costs O(n), but it happens rarely, because each growth doubles the capacity. Spread over all the pushes, each push costs a constant amount on average. This is called amortized O(1).

If you know how many elements you will push, Vec::with_capacity(n) allocates the whole block at once, and no copy happens at all. You will see this in several listings below.

3.3 How a String stores text

A String is a Vec<u8> with one extra rule. Its bytes must always be valid UTF-8. UTF-8 is the standard way of turning characters into bytes. An English letter takes one byte. Other characters take two, three, or four bytes. Figure 3.3 shows the four characters of "café".

This has three consequences you will meet in this chapter:

• s.len() counts bytes, not characters. "café".len() is 5.
• s.chars() walks the characters one at a time, decoding the bytes as it goes.
• You cannot index a String with s[3]. A byte index might fall in the middle of a character, as index 4 does in figure 3.3, so Rust does not allow it.

3.4 How a HashMap finds a key

A HashMap<K, V> stores pairs of a key and a value, and finds the value for a key quickly. It works in three steps (figure 3.4):

1. It runs the key through a hash function, which turns any key into a large number. The same key always gives the same number.
2. It uses some of the bits of that number to pick a bucket, one slot in an array of buckets.
3. It stores the pair in that bucket, or looks for it there.

Two keys can land in the same bucket, as 7 and 11 do in the figure. Then a lookup compares the keys in that bucket one by one. The map keeps the number of keys per bucket small by growing its bucket array as it fills. So on average, insert and get are O(1), however many keys the map holds.

Rust’s HashMap uses a hash function with a random starting value, chosen when the program starts. This stops an attacker from sending keys that all land in one bucket. It also means the order in which you iterate over a map changes from one run to the next.

Now you have the tools for the problems. Each one starts with the simplest correct idea, then shows how a collection makes it faster.

3.5 Finding two numbers that add up to a target

The problem. Given an array of numbers and a target, find two positions whose numbers add up to the target. For [2, 7, 11, 15] and target 9, the answer is positions 0 and 1, because 2 + 7 = 9.

The simple idea. Try every pair. For each position i, check every later position j. That is about n × n / 2 pairs, so O(n²).

A faster idea. Walk the array once. For each number, you know which partner it needs: target - num. If you have already seen that partner, you are done. To answer “have I seen it?” in one step, keep a HashMap from each number seen so far to its position.

Trace it on [2, 7, 11, 15] with target 9:

Listing 3.1 Two Sum with one pass and a hash map. src/problems/two_sum.rs

//! Two Sum: find the pair of indices whose values add up to a target.
//!
//! Use a `HashMap` for one pass: O(n) time, O(n) space.

use std::collections::HashMap;

pub fn two_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    let mut seen = HashMap::with_capacity(nums.len());
    for (idx, &num) in nums.iter().enumerate() {
        match seen.get(&(target - num)) {
            Some(&prev) => return Some((prev, idx)),
            None => {
                seen.insert(num, idx);
            }
        }
    }
    None
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn finds_pair() {
        let nums = [2, 7, 11, 15];
        assert_eq!(two_sum(&nums, 9), Some((0, 1)));
    }

    #[test]
    fn returns_none_when_missing() {
        assert_eq!(two_sum(&[1, 2, 3], 100), None);
    }
}

Walk through the function:

• The parameter nums: &[i32] is a slice, a borrowed view of a sequence of i32 values. You can pass a Vec, an array, or part of either.
• HashMap::with_capacity(nums.len()) sizes the map for the worst case, so it never grows during the loop.
• nums.iter().enumerate() gives pairs of (position, reference to number). The pattern (idx, &num) copies the number out of the reference.
• seen.get(&(target - num)) looks up the partner. get takes a reference to the key, hence the &.
• If the partner is found, the function returns both positions. Otherwise it records this number.

The lookup comes before the insert. Think of target 4 with a single 2 in the array. If the insert came first, the 2 would find itself and pair with itself.

The function returns Option<(usize, usize)>: Some with the two positions, or None if no pair exists. It runs in O(n) time and uses O(n) extra memory for the map.

3.6 A vector used as a stack

A stack is a collection where you add and remove items at the same end, called the top. The last item you added is the first one you remove. A Vec works as a stack. push adds to the end, and pop removes the last item and returns it. last looks at the end without removing it. All three are O(1).

3.6.1 Checking brackets

The problem. A string of brackets is valid if every opening bracket is closed by the matching kind, in the right order. "{[()]}" is valid. "([)]" is not, because ] arrives while ( is still open.

The idea. Read the string from left to right. Push each opening bracket onto a stack. When a closing bracket arrives, the top of the stack must be its matching opener; pop it and continue. At the end, the stack must be empty. Figure 3.5 traces "{[()]}".

Listing 3.2 Valid Parentheses. src/problems/valid_parentheses.rs

//! Valid Parentheses: classic stack problem with idiomatic pattern matching.
//!
pub fn is_valid(s: &str) -> bool {
    use std::collections::HashMap;

    let mut stack = Vec::with_capacity(s.len());

    // Maps each closing delimiter to the opening delimiter it must match.
    let expected = HashMap::from([(')', '('), ('}', '{'), (']', '[')]);

    for ch in s.chars() {
        match ch {
            '(' | '[' | '{' => stack.push(ch),
            // Every other character, including one outside the six delimiters,
            // must close the top of the stack.
            _ => {
                if stack.pop().as_ref() != expected.get(&ch) {
                    return false;
                }
            }
        }
    }

    stack.is_empty()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn valid_cases() {
        assert!(is_valid("()"));
        assert!(is_valid("()[]{}"));
        assert!(is_valid("{[()]}"));
    }

    #[test]
    fn invalid_cases() {
        assert!(!is_valid("(]"));
        assert!(!is_valid("([)]"));
        assert!(!is_valid("("));
        assert!(!is_valid(")"));
        assert!(!is_valid("(("));
    }
}

The map expected records, for each closing bracket, the opener it needs. HashMap::from([...]) builds a map from an array of pairs.

The match has two arms. The first pushes any of the three openers. The second handles every other character and compares two Option values:

• stack.pop() removes the top and returns Some(opener), or None if the stack is empty. .as_ref() turns Option<char> into Option<&char>, so it can be compared with the next value.
• expected.get(&ch) returns Some(&opener) for a closing bracket.

If they differ, the string is invalid. An empty stack gives None, which differs from Some, so an extra closer is caught. After the loop, stack.is_empty() catches openers that were never closed.

The tests list valid and invalid examples, including "([)]", a lone ")", and "((".

3.6.2 A stack that knows its minimum

The problem. Build a stack that supports push, pop, top, and get_min, the smallest value currently in it, all in O(1).

The idea. Scanning the stack for the minimum takes O(n). Instead, keep a second stack beside the first. Each time you push a value, also push the minimum so far. Then the minimum of the whole stack is always on top of the second stack. When you pop, pop both.

Trace pushes of -2, 0, and -3:

Listing 3.3 Min Stack with a parallel stack of minimums. src/problems/min_stack.rs

//! Min Stack: O(1) push, pop, top, and get_min.
//!
//! We keep a parallel `mins` stack. Each push stores the current minimum at that
//! point in history, so pop is symmetric.

#[derive(Debug, Default)]
pub struct MinStack {
    values: Vec<i32>,
    mins: Vec<i32>,
}

impl MinStack {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn push(&mut self, val: i32) {
        match self.mins.last() {
            Some(&min) if min <= val => self.mins.push(min),
            _ => self.mins.push(val),
        }
        self.values.push(val);
    }

    pub fn pop(&mut self) -> Option<i32> {
        self.mins.pop();
        self.values.pop()
    }

    pub fn top(&self) -> Option<i32> {
        self.values.last().copied()
    }

    pub fn get_min(&self) -> Option<i32> {
        self.mins.last().copied()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn stack_tracks_minimum() {
        let mut stack = MinStack::new();
        stack.push(-2);
        stack.push(0);
        stack.push(-3);
        assert_eq!(stack.get_min(), Some(-3));
        assert_eq!(stack.pop(), Some(-3));
        assert_eq!(stack.top(), Some(0));
        assert_eq!(stack.get_min(), Some(-2));
    }

    #[test]
    fn handles_duplicates() {
        let mut stack = MinStack::new();
        stack.push(1);
        stack.push(1);
        stack.pop();
        assert_eq!(stack.get_min(), Some(1));
    }
}

#[derive(Default)] gives MinStack a default() function that creates two empty vectors, and new calls it.

In push, self.mins.last() returns the current minimum, if any. The arm Some(&min) if min <= val has a guard, the if after the pattern. It pushes the old minimum again when the new value is not smaller. The _ arm covers both an empty stack and a new smaller value, and pushes val.

The guard uses <=, not <. When you push a value equal to the current minimum, the minimum is recorded again. So popping one copy leaves the other, and the minimum stays correct. The test handles_duplicates checks this case.

top and get_min use .copied() to turn Option<&i32> into Option<i32>, so the caller gets a plain number.

3.7 Two indexes moving toward each other

Some problems need you to look at both ends of an array at once. Keep one index at the start and one at the end, and move them toward each other. Each step moves at least one index, so the whole walk is O(n).

3.7.1 Reversing a string in place

The idea. Swap the first and last bytes, then the second and second-to-last, and stop when the indexes meet (figure 3.6).

There is a complication. As section 3.3 explained, a String must stay valid UTF-8, and swapping the bytes of a two-byte character would break it. So Rust does not let you change a String’s bytes directly in safe code. String::as_mut_vec gives you the bytes, but it is marked unsafe. unsafe marks code where the compiler cannot check a rule, so the programmer must. Here the rule is “the bytes are valid UTF-8 when you are done”.

Listing 3.4 The reversing function (lines 1 to 14). src/bin/reverse_string.rs

fn reverse_str(s: &mut String) {
    // SAFETY: s._as_mut_vec() is unsafe because it exposes the inner mutability to it's character buffer, and we must ensure
    // to leave valid UTF-8. We enforce ASCII only characters.
    assert!(s.is_ascii());
    let bytes = unsafe { s.as_mut_vec() };

    let (mut start, mut end) = (0, bytes.len() - 1);

    while start < end {
        bytes.swap(start, end);
        start += 1;
        end -= 1;
    }
}

The function keeps the rule by checking first: assert!(s.is_ascii()) stops the program unless every byte is a plain ASCII character. Reversing ASCII bytes gives ASCII, which is valid UTF-8. The unsafe block is then as small as possible, one call.

bytes.swap(start, end) exchanges two elements of the vector. The loop runs while start < end, so the middle element of an odd-length string stays where it is.

Listing 3.5 The complete program, with its tests. src/bin/reverse_string.rs

fn reverse_str(s: &mut String) {
    // SAFETY: s._as_mut_vec() is unsafe because it exposes the inner mutability to it's character buffer, and we must ensure
    // to leave valid UTF-8. We enforce ASCII only characters.
    assert!(s.is_ascii());
    let bytes = unsafe { s.as_mut_vec() };

    let (mut start, mut end) = (0, bytes.len() - 1);

    while start < end {
        bytes.swap(start, end);
        start += 1;
        end -= 1;
    }
}

fn main() {
    for value in ["abcd", "abc", "a", "rust"] {
        let mut s = String::from(value);
        reverse_str(&mut s);
        println!("{value:>6} -> {s}");
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn an_even_length_string_is_reversed() {
        let mut s = String::from("abcd");
        reverse_str(&mut s);
        assert_eq!(s, "dcba");
    }

    #[test]
    fn an_odd_length_string_keeps_its_middle_byte() {
        let mut s = String::from("abc");
        reverse_str(&mut s);
        assert_eq!(s, "cba");
    }

    #[test]
    fn a_single_byte_is_unchanged() {
        let mut s = String::from("a");
        reverse_str(&mut s);
        assert_eq!(s, "a");
    }

    #[test]
    fn the_buffer_is_reused() {
        let mut s = String::from("abcd");
        let capacity = s.capacity();
        let address = s.as_ptr();
        reverse_str(&mut s);
        assert_eq!(s.capacity(), capacity);
        assert_eq!(s.as_ptr(), address);
    }

    #[test]
    fn reversing_twice_restores_the_string() {
        let mut s = String::from("interview");
        reverse_str(&mut s);
        reverse_str(&mut s);
        assert_eq!(s, "interview");
    }

    #[test]
    #[should_panic]
    fn non_ascii_input_panics() {
        let mut s = String::from("café");
        reverse_str(&mut s);
    }
}

The test the_buffer_is_reused records the string’s capacity and the address of its bytes before the call, then checks both afterward. They are unchanged, so the reversal used no new memory. non_ascii_input_panics is marked #[should_panic]: it passes only if the call panics, which the assert! does for "café".

$ cargo run --bin reverse_string
  abcd -> dcba
   abc -> cba
     a -> a
  rust -> tsur

3.7.2 Three numbers that add up to a target

The problem. Find every set of three numbers in an array that adds up to a target, without listing the same set twice.

The idea. Sort the array first. Then fix the first number, and look for the other two in the rest of the array. Use two indexes: left starts right after the fixed number, and right starts at the end. Because the array is sorted, you know which index to move:

• If the sum is too small, move left right. That can only increase the sum.
• If the sum is too large, move right left. That can only decrease it.
• If the sum is right, record the three numbers, then move both.

Each fixed number costs one O(n) walk, and there are n fixed numbers, so the whole search is O(n²). Sorting costs O(n log n), which is smaller.

The function first sorts, then fixes each number in turn:

// Import the variants directly into scope
use std::cmp::Ordering::{Equal, Greater, Less};

pub fn three_sum(numbers: &mut [i32], target: i32) -> Vec<(i32, i32, i32)> {
    numbers.sort_unstable();

    let mut results = Vec::new();
    let target = i64::from(target);

    for i in 0..numbers.len() {
        // Skip a first value that was already used, so triplets stay unique.
        if i > 0 && numbers[i] == numbers[i - 1] {
            continue;
        }

        let (mut left, mut right) = (i + 1, numbers.len().saturating_sub(1));
        // ...
    }
}

• use std::cmp::Ordering::{Equal, Greater, Less}; lets the code write Less instead of Ordering::Less. The next excerpt matches on these three.
• The continue skips a fixed value equal to the previous one, so the same set is not found twice.
• numbers.len().saturating_sub(1) gives 0 instead of underflowing when the slice is empty.

For each fixed number, left and right close in from the two ends of the rest:

pub fn three_sum(numbers: &mut [i32], target: i32) -> Vec<(i32, i32, i32)> {
    // ...
    for i in 0..numbers.len() {
        // ...
        while left < right {
            // Widen to i64 so the sum of three i32 values cannot overflow.
            let current_sum = numbers[i] as i64 + numbers[left] as i64 + numbers[right] as i64;

            match current_sum.cmp(&target) {
                Less => left += 1,
                Greater => right -= 1,
                Equal => {
                    results.push((numbers[i], numbers[left], numbers[right]));

                    while left < right && numbers[left] == numbers[left + 1] {
                        left += 1;
                    }
                    while left < right && numbers[right] == numbers[right - 1] {
                        right -= 1;
                    }

                    left += 1;
                    right -= 1;
                }
            }
        }
    }
    // ...
}

• The sum is computed in i64. Three i32 values can add up to more than i32 can hold. The test does_not_overflow_on_extreme_values uses i32::MAX twice to check this.
• current_sum.cmp(&target) returns Less, Greater, or Equal, and the match turns each into the move from the list above.
• After a match, the two inner while loops step left and right past values equal to the ones in the match.

Listing 3.6 Three Sum, with its tests. src/problems/three_sum.rs

//! Three Sum: every unique triplet of values that adds up to a target.
//!
//! Sort, fix the first value, then close in on the other two with two pointers.
//! Sorts the caller's slice in place: O(n^2) time, no extra space beyond the result.

// Import the variants directly into scope
use std::cmp::Ordering::{Equal, Greater, Less};

pub fn three_sum(numbers: &mut [i32], target: i32) -> Vec<(i32, i32, i32)> {
    numbers.sort_unstable();

    let mut results = Vec::new();
    let target = i64::from(target);

    for i in 0..numbers.len() {
        // Skip a first value that was already used, so triplets stay unique.
        if i > 0 && numbers[i] == numbers[i - 1] {
            continue;
        }

        let (mut left, mut right) = (i + 1, numbers.len().saturating_sub(1));
        while left < right {
            // Widen to i64 so the sum of three i32 values cannot overflow.
            let current_sum = numbers[i] as i64 + numbers[left] as i64 + numbers[right] as i64;

            match current_sum.cmp(&target) {
                Less => left += 1,
                Greater => right -= 1,
                Equal => {
                    results.push((numbers[i], numbers[left], numbers[right]));

                    while left < right && numbers[left] == numbers[left + 1] {
                        left += 1;
                    }
                    while left < right && numbers[right] == numbers[right - 1] {
                        right -= 1;
                    }

                    left += 1;
                    right -= 1;
                }
            }
        }
    }

    results
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn finds_all_unique_triplets() {
        let result = three_sum(&mut [-1, 0, 1, 2, -1, -4], 0);
        assert_eq!(result, vec![(-1, -1, 2), (-1, 0, 1)]);
    }

    #[test]
    fn skips_duplicates_on_every_position() {
        assert_eq!(three_sum(&mut [0, 0, 0, 0], 0), vec![(0, 0, 0)]);
        assert_eq!(three_sum(&mut [-2, 0, 0, 2, 2], 0), vec![(-2, 0, 2)]);
    }

    #[test]
    fn supports_a_non_zero_target() {
        assert_eq!(
            three_sum(&mut [1, 2, 3, 4, 5], 9),
            vec![(1, 3, 5), (2, 3, 4)]
        );
    }

    #[test]
    fn returns_nothing_when_no_triplet_exists() {
        assert!(three_sum(&mut [1, 2, 3], 100).is_empty());
        assert!(three_sum(&mut [1, 2], 3).is_empty());
        assert!(three_sum(&mut [], 0).is_empty());
    }

    #[test]
    fn does_not_overflow_on_extreme_values() {
        assert_eq!(
            three_sum(&mut [i32::MAX, i32::MAX, i32::MIN], i32::MAX - 1),
            vec![(i32::MIN, i32::MAX, i32::MAX)]
        );
    }
}

3.8 A window that slides along a string

The problem. Find the length of the longest piece of a string in which no character repeats. In "pwwkew", the answer is 3, for "wke" or "kew".

The idea. Keep a window, a range start..=end of the string with no repeated character. Move end forward one character at a time. When the new character already appears inside the window, move start to the position right after its earlier one. The window never contains a repeat, and the answer is the largest window seen.

To know where a character last appeared, keep a HashMap from each character to its last position. Figure 3.7 shows the moment in "pwwkew" when the second w arrives.

Listing 3.7 Longest substring without a repeated character. src/problems/sliding_window.rs

//! Longest substring without repeating characters.
//!
//! Sliding window with `HashMap<char, usize>`; the window start is monotonic.

use std::collections::HashMap;

pub fn length_of_longest_substring(s: &str) -> usize {
    let mut last_seen = HashMap::with_capacity(s.len());

    let (mut start, mut longest) = (0, 0);

    for (end, ch) in s.chars().enumerate() {
        if let Some(&previous) = last_seen.get(&ch) {
            start = start.max(previous + 1);
        }
        longest = longest.max(end - start + 1);
        last_seen.insert(ch, end);
    }

    longest
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn examples() {
        assert_eq!(length_of_longest_substring("abcabcbb"), 3);
        assert_eq!(length_of_longest_substring("bbbbb"), 1);
        assert_eq!(length_of_longest_substring("pwwkew"), 3);
        assert_eq!(length_of_longest_substring(""), 0);
    }
}

if let Some(&previous) = last_seen.get(&ch) runs its block only when the character has been seen before. Then start = start.max(previous + 1) moves start past the earlier position. The max stops start from moving backward when the earlier position is already outside the window. For example, in "abba", the last a was seen at 0, but start is already at 2.

end - start + 1 is the current window’s length. Both start and end only move forward, so the loop does O(n) work.

The positions come from chars().enumerate(), so they count characters, not bytes. That is what the problem asks for.

3.9 Sort, then walk once: merging ranges

The problem. Given ranges such as [1,3] [2,6] [8,10] [15,18], merge every group that overlaps. The answer here is [1,6] [8,10] [15,18].

The idea. Sort the ranges by their start. Then walk them once. Each range either overlaps the last merged range, and extends it, or starts a new merged range (figure 3.8).

The file solves the problem three times: with a named struct, with plain tuples, and in place. First the struct and the first version:

Listing 3.8 Merging ranges held in a struct (lines 6 to 28). src/problems/merge_intervals.rs

#[derive(Debug, PartialEq, Clone, Copy)]
pub struct Interval {
    start: i32,
    end: i32,
}
pub fn merge_intervals(mut intervals: Vec<Interval>) -> Vec<Interval> {
    if intervals.is_empty() {
        return intervals;
    }

    intervals.sort_unstable_by_key(|interval| interval.start);

    let mut merged: Vec<Interval> = Vec::with_capacity(intervals.len());
    for Interval { start, end } in intervals {
        match merged.last_mut() {
            Some(previous) if start <= previous.end => {
                previous.end = previous.end.max(end);
            }
            _ => merged.push(Interval { start, end }),
        }
    }
    merged
}

sort_unstable_by_key(|interval| interval.start) sorts by start. “Unstable” means equal starts may change order, which does not affect the result and is slightly faster.

The loop header for Interval { start, end } in intervals takes each range apart into two variables.

merged.last_mut() returns a mutable reference to the last merged range, or None if there is none yet. The guard if start <= previous.end checks for overlap. When it holds, the code extends the range in place through the reference: previous.end = previous.end.max(end). The max handles a range that lies entirely inside the previous one. In every other case, the _ arm starts a new merged range.

The second version does the same with (i32, i32) tuples, so the end is written previous.1:

Listing 3.9 The same merge over tuples (lines 30 to 48).

pub fn merge_intervals2(mut intervals: Vec<(i32, i32)>) -> Vec<(i32, i32)> {
    if intervals.is_empty() {
        return intervals;
    }

    intervals.sort_unstable_by_key(|(start, _)| *start);

    let mut merged: Vec<(i32, i32)> = Vec::with_capacity(intervals.len());

    for &(start, end) in &intervals {
        match merged.last_mut() {
            Some(previous) if start <= previous.1 => {
                previous.1 = previous.1.max(end);
            }
            _ => merged.push((start, end)),
        }
    }
    merged
}

It works the same way. The struct version is easier to read, because previous.end says what previous.1 leaves to you to remember.

The third version needs no second vector. It writes the merged ranges into the front of the input vector:

Listing 3.10 Merging in place (lines 50 to 72).

/// In place: `last` is the last merged interval at the front of the vector.
/// O(1) extra space.
pub fn merge_intervals_in_place(intervals: &mut Vec<Interval>) {
    if intervals.is_empty() {
        return;
    }

    intervals.sort_unstable_by_key(|interval| interval.start);

    let mut last = 0;
    for i in 1..intervals.len() {
        match (intervals[last], intervals[i]) {
            (previous, current) if current.start <= previous.end => {
                intervals[last].end = previous.end.max(current.end);
            }
            (_, current) => {
                last += 1;
                intervals[last] = current;
            }
        }
    }
    intervals.truncate(last + 1);
}

last is the position of the last merged range. For each later range, the code either extends intervals[last], or moves last forward one place and copies the range there. At the end, truncate(last + 1) drops the leftovers. This version uses O(1) extra memory.

match (intervals[last], intervals[i]) copies both ranges out of the vector into a pair. That works because Interval derives Copy. Because the arms work on copies, they are free to write to intervals[last] without a borrowing conflict.

Listing 3.11 The tests (lines 74 to 106).

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn merges_overlapping_and_adjacent() {
        let input = [(1, 3), (2, 6), (8, 10), (15, 18)].map(|(start, end)| Interval { start, end });
        let expected = [(1, 6), (8, 10), (15, 18)].map(|(start, end)| Interval { start, end });
        assert_eq!(merge_intervals(input.into()), expected);
    }

    #[test]
    fn handles_empty_and_disjoint() {
        assert_eq!(merge_intervals(vec![]), vec![]);
        let input = [(1, 2), (3, 4)].map(|(start, end)| Interval { start, end });
        let expected = [(1, 2), (3, 4)].map(|(start, end)| Interval { start, end });
        assert_eq!(merge_intervals(input.into()), expected);
    }

    #[test]
    fn merges_in_place() {
        let mut intervals: Vec<Interval> = [(8, 10), (1, 3), (15, 18), (2, 6)]
            .map(|(start, end)| Interval { start, end })
            .into();
        merge_intervals_in_place(&mut intervals);
        let expected = [(1, 6), (8, 10), (15, 18)].map(|(start, end)| Interval { start, end });
        assert_eq!(intervals, expected);

        let mut empty = vec![];
        merge_intervals_in_place(&mut empty);
        assert!(empty.is_empty());
    }
}

The tests build ranges from tuples with .map(|(start, end)| Interval { start, end }) on arrays. They cover overlapping ranges, an empty input, ranges that do not touch, and unsorted input for the in-place version.

All three versions merge ranges that only touch, such as [1,3] and [3,5], because the check is <=.

3.10 Halving the search: binary search

In a sorted array, you can find a value without looking at every element. Compare the value with the middle element. If the value is smaller, it can only be in the left half; if larger, only in the right half. Discard the other half and repeat. Figure 3.9 finds 23 in eight values in three steps.

The code in this section uses a half-open range low..high. low is the first position still in the range, and high is one past the last. The range is empty when low == high.

3.10.1 Searching a rotated array

The file solves a harder version. A sorted array has been rotated: some elements from the front were moved to the back, as in [4, 5, 6, 7, 0, 1, 2]. You still want O(log n).

The idea rests on one observation. If you split a rotated array at any middle position, at least one of the two halves is still sorted. You can tell which by comparing its end values. Then:

• If the left half is sorted and the target lies between its first and middle values, search the left half.
• If the right half is sorted and the target lies between its middle and last values, search the right half.
• Otherwise, search the other half.

Listing 3.12 Search in a rotated sorted array. src/problems/binary_search.rs

//! Binary search on a rotated sorted array.
//!
//! O(log n). The code uses explicit range bounds and
//! sorted-half checks; no recursion or nested `if` chains are required.

pub fn search_rotated(nums: &[i32], target: i32) -> Option<usize> {
    let mut low = 0usize;
    let mut high = nums.len();

    while low < high {
        let mid = low + (high - low) / 2;
        if nums[mid] == target {
            return Some(mid);
        }

        let left_is_sorted = nums[low] <= nums[mid];
        if left_is_sorted {
            if nums[low] <= target && target < nums[mid] {
                high = mid;
            } else {
                low = mid + 1;
            }
        } else if nums[mid] < target && target <= nums[high - 1] {
            low = mid + 1;
        } else {
            high = mid;
        }
    }

    None
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn finds_target_in_rotated_array() {
        let nums = [4, 5, 6, 7, 0, 1, 2];
        assert_eq!(search_rotated(&nums, 0), Some(4));
        assert_eq!(search_rotated(&nums, 3), None);
        assert_eq!(search_rotated(&nums, 5), Some(1));
    }

    #[test]
    fn handles_unrotated_and_single() {
        assert_eq!(search_rotated(&[1, 2, 3, 4], 3), Some(2));
        assert_eq!(search_rotated(&[1], 1), Some(0));
        assert_eq!(search_rotated(&[1], 2), None);
    }
}

mid = low + (high - low) / 2 finds the middle. The shorter (low + high) / 2 can overflow when both are very large; this form cannot.

nums[low] <= nums[mid] means the left half is sorted. The test that the target is in it is nums[low] <= target && target < nums[mid]. The right-half test uses nums[high - 1], the last element, because high itself is one past the end.

3.11 Rotating a square grid in place

The problem. Rotate an n × n grid a quarter turn clockwise, without a second grid.

The idea. Do it in two simple steps (figure 3.11). First transpose the grid. That means swapping the element at row i, column j with the one at row j, column i. It flips the grid across its diagonal. Then reverse each row.

Listing 3.13 The complete program. src/bin/rotate_matrix.rs

fn rotate(m: &mut [Vec<i32>]) {
    let n = m.len();

    for i in 0..n {
        for j in i + 1..n {
            let tmp = m[i][j];
            m[i][j] = m[j][i];
            m[j][i] = tmp;
        }
    }

    for row in m.iter_mut() {
        row.reverse();
    }
}

fn main() {
    let mut m = vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]];

    rotate(&mut m);

    for row in &m {
        println!("{:?}", row);
    }
}

The grid is a Vec<Vec<i32>>, a vector of rows. rotate takes it as &mut [Vec<i32>], a mutable slice of rows, because it changes cells but never adds or removes a row. The transpose loop starts j at i + 1, so it visits only the cells above the diagonal and swaps each pair once. Visiting every cell would swap each pair twice and undo the work.

The swap uses a temporary variable tmp. std::mem::swap needs two mutable references, and m[i][j] and m[j][i] are in different rows of the same outer vector. The borrow checker cannot see that they do not overlap, so it would reject taking both at once.

for row in m.iter_mut() gives a mutable reference to each row, and row.reverse() reverses it.

$ cargo run --bin rotate_matrix
[7, 4, 1]
[8, 5, 2]
[9, 6, 3]

3.12 Finding text inside text

The problem. Find the first position where a short string, the needle, appears in a longer one, the haystack.

The simple idea. Try each position of the haystack, and compare the needle character by character. On a mismatch, move one position right and start over. In the worst case this compares every needle character at every position. For a haystack of length n and a needle of length m, that is O(n × m).

The better idea. Suppose a mismatch comes after several matching characters. You already know what those characters were, because they are the start of the needle. Often a later part of them is also the start of the needle, so you can continue from there instead of starting over. The Knuth-Morris-Pratt algorithm (KMP) uses this. It never moves backward in the haystack, so it runs in O(n + m).

Figure 3.12 shows one such jump.

To know how far to jump, KMP first builds a table from the needle alone. For each position i, look at the piece needle[0..=i]. lps[i] is the length of the longest part of that piece that is both its start and its end. The whole piece does not count. The name “lps” stands for longest proper prefix that is also a suffix. For the needle in the figure:

For example, lps[4] = 2, because "aabaa" starts with "aa" and ends with "aa".

Listing 3.14 The search and the table (lines 1 to 58). src/bin/kmp_pattern_matching.rs

struct Solution {}
impl Solution {
    /// @param haystack the string to search in
    /// @param needle   the pattern to find
    /// @return         first index of needle in haystack, or -1
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let (haystack, needle) = (haystack.as_bytes(), needle.as_bytes());
        if needle.is_empty() {
            return 0;
        }

        let lps = Self::build_lps(needle);
        // left walks the needle, and right walks the haystack.
        let (mut left, mut right) = (0, 0);

        while right < haystack.len() {
            if haystack[right] == needle[left] {
                left += 1;
                right += 1;
            } else if left > 0 {
                // Fall back, keeping the characters that still match.
                left = lps[left - 1];
            } else {
                // A mismatch at the start of the needle.
                right += 1;
            }

            if left == needle.len() {
                // The whole needle matched.
                return (right - left) as i32;
            }
        }
        -1
    }

    // LPS: longest proper prefix of needle[0..=right] that is also a suffix
    fn build_lps(needle: &[u8]) -> Vec<usize> {
        let mut lps = vec![0; needle.len()];
        let (mut left, mut right) = (0, 1);

        while right < needle.len() {
            if needle[right] == needle[left] {
                left += 1;
                lps[right] = left;
                right += 1;
            } else if left > 0 {
                left = lps[left - 1];
            } else {
                // lps[right] stays 0.
                right += 1;
            }
        }
        lps
    }
}

fn main() {
    let cases = [
    // ...
}

str_str works on bytes, from as_bytes(), so it can index directly. left counts how many needle characters currently match, and right walks the haystack. Each pass of the loop takes one of three branches:

1. The characters match: advance both.
2. They do not match, but some characters had matched: jump left back to lps[left - 1], keeping right where it is.
3. They do not match and nothing had matched: advance right.

When left reaches the needle’s length, the needle starts at right - left.

build_lps runs the same three-branch loop, comparing the needle against itself. Both loops only move forward, which gives the O(n + m) total.

Listing 3.15 The complete program. src/bin/kmp_pattern_matching.rs

struct Solution {}
impl Solution {
    /// @param haystack the string to search in
    /// @param needle   the pattern to find
    /// @return         first index of needle in haystack, or -1
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let (haystack, needle) = (haystack.as_bytes(), needle.as_bytes());
        if needle.is_empty() {
            return 0;
        }

        let lps = Self::build_lps(needle);
        // left walks the needle, and right walks the haystack.
        let (mut left, mut right) = (0, 0);

        while right < haystack.len() {
            if haystack[right] == needle[left] {
                left += 1;
                right += 1;
            } else if left > 0 {
                // Fall back, keeping the characters that still match.
                left = lps[left - 1];
            } else {
                // A mismatch at the start of the needle.
                right += 1;
            }

            if left == needle.len() {
                // The whole needle matched.
                return (right - left) as i32;
            }
        }
        -1
    }

    // LPS: longest proper prefix of needle[0..=right] that is also a suffix
    fn build_lps(needle: &[u8]) -> Vec<usize> {
        let mut lps = vec![0; needle.len()];
        let (mut left, mut right) = (0, 1);

        while right < needle.len() {
            if needle[right] == needle[left] {
                left += 1;
                lps[right] = left;
                right += 1;
            } else if left > 0 {
                left = lps[left - 1];
            } else {
                // lps[right] stays 0.
                right += 1;
            }
        }
        lps
    }
}

fn main() {
    let cases = [
        ("sadbutsad", "sad"),
        ("leetcode", "leeto"),
        ("aabaaabaaac", "aabaaac"),
        ("hello", ""),
    ];

    for (haystack, needle) in cases {
        let result = Solution::str_str(haystack.to_string(), needle.to_string());
        println!("str_str({haystack:?}, {needle:?}) = {result}\n");
    }
}

$ cargo run --bin kmp_pattern_matching
str_str("sadbutsad", "sad") = 0

str_str("leetcode", "leeto") = -1

str_str("aabaaabaaac", "aabaaac") = 4

str_str("hello", "") = 0

The function returns -1 when the needle is absent, following the convention of the problem it solves. In your own code, Option<usize> states that more clearly. For everyday searching, the standard library’s str::find is also linear time.

3.13 The complete files

The sections above showed these files in excerpts. Here each one is whole.

Listing 3.16 Merging overlapping intervals, with its tests. src/problems/merge_intervals.rs

//! Merge Intervals: sort by start, then merge overlapping intervals in one pass.
//!
//! The `match out.last_mut()` pattern is intentionally clean: no deep nesting,
//! no confusing boolean flags.

#[derive(Debug, PartialEq, Clone, Copy)]
pub struct Interval {
    start: i32,
    end: i32,
}
pub fn merge_intervals(mut intervals: Vec<Interval>) -> Vec<Interval> {
    if intervals.is_empty() {
        return intervals;
    }

    intervals.sort_unstable_by_key(|interval| interval.start);

    let mut merged: Vec<Interval> = Vec::with_capacity(intervals.len());
    for Interval { start, end } in intervals {
        match merged.last_mut() {
            Some(previous) if start <= previous.end => {
                previous.end = previous.end.max(end);
            }
            _ => merged.push(Interval { start, end }),
        }
    }
    merged
}

pub fn merge_intervals2(mut intervals: Vec<(i32, i32)>) -> Vec<(i32, i32)> {
    if intervals.is_empty() {
        return intervals;
    }

    intervals.sort_unstable_by_key(|(start, _)| *start);

    let mut merged: Vec<(i32, i32)> = Vec::with_capacity(intervals.len());

    for &(start, end) in &intervals {
        match merged.last_mut() {
            Some(previous) if start <= previous.1 => {
                previous.1 = previous.1.max(end);
            }
            _ => merged.push((start, end)),
        }
    }
    merged
}

/// In place: `last` is the last merged interval at the front of the vector.
/// O(1) extra space.
pub fn merge_intervals_in_place(intervals: &mut Vec<Interval>) {
    if intervals.is_empty() {
        return;
    }

    intervals.sort_unstable_by_key(|interval| interval.start);

    let mut last = 0;
    for i in 1..intervals.len() {
        match (intervals[last], intervals[i]) {
            (previous, current) if current.start <= previous.end => {
                intervals[last].end = previous.end.max(current.end);
            }
            (_, current) => {
                last += 1;
                intervals[last] = current;
            }
        }
    }
    intervals.truncate(last + 1);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn merges_overlapping_and_adjacent() {
        let input = [(1, 3), (2, 6), (8, 10), (15, 18)].map(|(start, end)| Interval { start, end });
        let expected = [(1, 6), (8, 10), (15, 18)].map(|(start, end)| Interval { start, end });
        assert_eq!(merge_intervals(input.into()), expected);
    }

    #[test]
    fn handles_empty_and_disjoint() {
        assert_eq!(merge_intervals(vec![]), vec![]);
        let input = [(1, 2), (3, 4)].map(|(start, end)| Interval { start, end });
        let expected = [(1, 2), (3, 4)].map(|(start, end)| Interval { start, end });
        assert_eq!(merge_intervals(input.into()), expected);
    }

    #[test]
    fn merges_in_place() {
        let mut intervals: Vec<Interval> = [(8, 10), (1, 3), (15, 18), (2, 6)]
            .map(|(start, end)| Interval { start, end })
            .into();
        merge_intervals_in_place(&mut intervals);
        let expected = [(1, 6), (8, 10), (15, 18)].map(|(start, end)| Interval { start, end });
        assert_eq!(intervals, expected);

        let mut empty = vec![];
        merge_intervals_in_place(&mut empty);
        assert!(empty.is_empty());
    }
}

This chapter used iterators such as iter() and enumerate() without much comment. Chapter 4 looks at them closely, along with the references they hand you and the lifetimes that keep those references valid.

Exercises

1. Change two_sum to use i64 arithmetic so that it cannot overflow, and add a test with i32::MIN.
2. Fix is_valid so that characters other than brackets are rejected, and add a test for "a".
3. Make reverse_str handle an empty string, then write a version that reverses the characters of any UTF-8 string, including "café".
4. Write a plain binary search over a sorted slice that returns Option<usize>, and test it on arrays of length 0, 1, and 2.
5. Rotate the grid counterclockwise instead, using a transpose and one other reversal.