Solve LeetCode Patterns in Rust

Introduction

30 Second Summary

When you face a coding problem, the hard part is not writing the code. It is knowing which data structure turns a slow solution into a fast one.

In this project, you will build a test-driven Rust library that implements 4 core algorithmic patterns. Each module contains a brute-force solution and an optimized solution, backed by passing tests that prove why the right data structure matters.

What You'll Build

You run cargo test and every solution lights up green. Each module solves a real LeetCode problem using the exact data structure that matches its shape.

By the end of this project, you'll have:

• Four optimized solutions (HashMap, Two Pointers, Sliding Window, Binary Search) that pass all tests, each proving why brute force falls short at scale.
• A pattern recognition framework documented in code comments so you can look at any new problem, identify its shape, and pick the right approach immediately.
• Battle-tested Rust idioms (ownership, slices, HashMap, match on Ordering) applied to real algorithmic problems you can reference during interviews.
• Secret Mission: Implement 3Sum by combining sorting with Two Pointers and deduplication logic.

Are there any prerequisites?

You should be comfortable with basic Rust concepts: ownership, borrowing, pattern matching, Vec, and basic iterators. You do not need any prior data structures and algorithms experience.

Before We Start

Before we dive in, let's lock in what you're about to build and why it matters. This project is about developing the instinct to look at a problem and immediately know which data structure turns a slow solution into a fast one.

Set Up the Project Structure

Every algorithm pattern in this project lives in its own module. This makes each file self-contained and lets you run tests for one pattern at a time without noise from the others.

In this step, you will create a Rust library project and wire up the module structure. Once it compiles cleanly, you will know the skeleton is ready for real algorithms.

In this step, get ready to:

• Create a Rust library project with four empty module files.
• Verify the skeleton compiles with zero tests and zero errors.

Create the project and module files

A Rust library project has no main.rs. Instead it exposes functions through src/lib.rs, and you exercise them entirely with cargo test. That is the only command you will use in this project.

• Press Cmd+Space (macOS) or the Windows key (Windows) to open your search bar.
• Type Terminal and press Enter to open it.
• Move to your Desktop by running this command:

cd ~/Desktop

• Create a new Rust library project and move into it by running these commands:

cargo new dsa-patterns --lib
cd dsa-patterns

You should see a confirmation message that the library project was created.

What did cargo new --lib do?

It created a dsa-patterns folder on your Desktop containing a Cargo.toml manifest and a src/lib.rs starter file. Because you passed --lib, there is no main.rs and no binary to run.

Seeing permission denied or command not found?

If you see a "command not found" message, your Rust toolchain may not be on your PATH. Try closing and reopening your terminal, then run cargo --version to confirm Cargo is accessible.

Help me fix my cargo command

• Create the four module files with placeholder functions by running these commands:

echo 'pub fn placeholder() {}' > src/hashmap_pattern.rs
echo 'pub fn placeholder() {}' > src/two_pointers.rs
echo 'pub fn placeholder() {}' > src/sliding_window.rs
echo 'pub fn placeholder() {}' > src/binary_search.rs

What does this do?

Each echo command writes a single public function into a new .rs file. These placeholders exist solely so the compiler does not complain about empty modules. You will replace them with real algorithms in later steps.

• Confirm the files exist by running:

ls src/

You should see binary_search.rs, hashmap_pattern.rs, lib.rs, sliding_window.rs, and two_pointers.rs listed.

Missing a file?

Make sure you ran the echo commands from inside the dsa-patterns folder. If ls src/ shows only lib.rs, run pwd to check your location. It should end with dsa-patterns.

Help me find my missing module files

• Now open the project in VS Code. Press Cmd+Space (macOS) or the Windows key (Windows) to open your search bar.
• Type VS Code and press Enter to open it.
• Click File in the top menu bar.
• Click Open Folder.
• Navigate to your Desktop, select the dsa-patterns folder, and click Open.
• In the Explorer sidebar, expand src/ and click lib.rs to open it.
• Select all the existing content and delete it.
• Replace it with the module declarations below:

pub mod hashmap_pattern;
pub mod two_pointers;
pub mod sliding_window;
pub mod binary_search;

What does this code do?

Each pub mod line tells the Rust compiler to look for a matching file in the src/ directory. For example, pub mod hashmap_pattern; maps to src/hashmap_pattern.rs.

The pub keyword makes each module accessible from tests. Without it, cargo test would not be able to call the functions you write later.

• Save lib.rs with Cmd+S (macOS) or Ctrl+S (Windows).

Verify the skeleton compiles

Before you run the test command, think about what you expect. There are no test functions anywhere in the project yet.

• Open the integrated terminal in VS Code by pressing Ctrl+` (backtick key, both macOS and Windows).
• What do you think cargo test will output? Will it error, or succeed with zero tests?
• Run the test suite:

cargo test

You should see output confirming 0 tests passed with no compilation errors. The project compiles cleanly and is ready for real code.

Seeing a compilation error?

Check that each module declaration in src/lib.rs exactly matches a filename in src/. A typo like hashmap_patterns (extra s) will fail because no matching file exists.

Also confirm each module file contains pub fn placeholder() {} and nothing else. An empty file compiles fine too, but any stray character can trigger a syntax error.

Help me debug my compilation error

✔️ Awesome, I've got everything!

Great. Double check you have saved src/lib.rs and that cargo test reports zero tests with no errors.

ⓧ I'd like to double check the full code

Here is every file you should have at this point.

pub mod hashmap_pattern;
pub mod two_pointers;
pub mod sliding_window;
pub mod binary_search;

pub fn placeholder() {}

pub fn placeholder() {}

pub fn placeholder() {}

pub fn placeholder() {}

Your skeleton is in place. Next up, you will write real algorithms. The first pattern is HashMap, where you will turn an O(n squared) brute-force Two Sum into an O(n) single-pass solution.

Implement the HashMap Pattern — Two Sum

Your project skeleton compiles cleanly with four empty modules. Now it is time to fill the first one with a real algorithm.

Most beginners solve pair-finding problems with nested loops. That approach works, but it checks every possible pair. For an array of 100,000 elements, that is nearly 5 billion comparisons. In an interview, that is an instant rejection.

In this step, you will implement Two Sum both ways. First the brute force, so you see the O(n^2) shape. Then a HashMap-powered single pass that finds the answer in O(n) time by storing what it has already seen.

In this step, get ready to:

• Implement brute force Two Sum with nested loops and verify it passes basic tests.
• Implement optimal Two Sum using HashMap and verify it handles 100,000 elements.
• Document the pattern recognition rule for future problem-solving.

Implement brute force Two Sum

The brute force approach is the simplest way to think about Two Sum: check every pair of numbers until you find two that add up to the target. No extra data structures needed.

• Open src/hashmap_pattern.rs in VS Code.
• Delete the placeholder function and replace the entire file content with the brute force implementation:

/// Brute force: O(n^2) time, O(1) space
/// Check every pair of elements
pub fn two_sum_brute(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    for i in 0..nums.len() {
        for j in (i + 1)..nums.len() {
            if nums[i] + nums[j] == target {
                return Some((i, j));
            }
        }
    }
    None
}

What does this code do?

The function takes a slice of integers and a target sum. It returns the indices of the two numbers that add up to the target, or None if no pair exists.

• The outer loop picks each element. The inner loop checks every element after it.
• This means for n elements, you do roughly n * (n-1) / 2 comparisons. That is O(n^2).
• The return type Option<(usize, usize)> is idiomatic Rust for "might not have an answer."

Now add a test module below the function so you can verify the brute force works.

• Add the following test module at the bottom of src/hashmap_pattern.rs:

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

    #[test]
    fn test_two_sum_brute_basic() {
        assert_eq!(two_sum_brute(&[2, 7, 11, 15], 9), Some((0, 1)));
    }

    #[test]
    fn test_two_sum_brute_no_solution() {
        assert_eq!(two_sum_brute(&[1, 2, 3], 10), None);
    }
}

What does this code do?

• The #[cfg(test)] attribute tells Rust to compile this module only when running tests.
• The use super::*; import brings all functions from the parent module into scope.
• Each #[test] function asserts an expected result. If the assertion fails, the test fails.

• Save src/hashmap_pattern.rs.
• Run the brute force tests by running this command in your terminal:

cargo test hashmap

You should see 2 tests pass with zero failures.

Seeing a compilation error?

• Make sure you deleted the original pub fn placeholder() {} line. It will conflict with the new code.
• Check that #[cfg(test)] appears on its own line directly above mod tests {.
• Confirm the function signature matches exactly: pub fn two_sum_brute(nums: &[i32], target: i32) -> Option<(usize, usize)>.

Help me debug my two_sum_brute compilation error

Implement the HashMap solution

The brute force passes, but think about what happens at scale. For 100,000 elements, nested loops perform nearly 5 billion comparisons. Interviewers expect O(n).

The insight: for each number, you can compute its complement (target minus the number). If you have already seen that complement, you have your pair. A HashMap gives you O(1) lookup for previously seen values.

• Add the HashMap import at the very top of src/hashmap_pattern.rs (above the brute force function):

use std::collections::HashMap;

• Add the optimized function below two_sum_brute and above the #[cfg(test)] module:

/// Optimal: O(n) time, O(n) space
/// Use HashMap to store seen values and look up complements in O(1)
pub fn two_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    let mut seen: HashMap<i32, usize> = HashMap::new();
    for (i, &num) in nums.iter().enumerate() {
        let complement = target - num;
        if let Some(&j) = seen.get(&complement) {
            return Some((j, i));
        }
        seen.insert(num, i);
    }
    None
}

What does this code do?

• A single pass through the slice. For each number, compute complement = target - num.
• Check if that complement already exists in the HashMap with .get(&complement). If yes, return both indices immediately.
• If no, insert the current number and its index into the map. Future iterations can find it.
• The if let Some(&j) pattern destructures the Option and dereferences the value in one step.

Now add tests for the HashMap solution. These go inside your existing mod tests block, below the two brute force tests.

• Add these test functions inside the mod tests { ... } block, before the closing }:

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

    #[test]
    fn test_two_sum_middle() {
        assert_eq!(two_sum(&[3, 2, 4], 6), Some((1, 2)));
    }

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

    #[test]
    fn test_two_sum_negative() {
        assert_eq!(two_sum(&[-1, -2, -3, -4, -5], -8), Some((2, 4)));
    }

    #[test]
    fn test_two_sum_large_input() {
        let mut nums: Vec<i32> = (0..100_000).collect();
        nums.push(999_999);
        let result = two_sum(&nums, 1_099_998);
        assert_eq!(result, Some((99_999, 100_000)));
    }

What does the large input test prove?

The test_two_sum_large_input test creates a Vec of 100,001 elements where the answer is the last two indices. The HashMap solution finds them in a single pass through 100,001 elements. Brute force would need roughly 5 billion pair checks to reach the same answer.

• Save src/hashmap_pattern.rs.
• Run the tests to confirm everything passes:

cargo test hashmap

You should see 7 tests pass. The large input test completes instantly thanks to the HashMap's O(1) lookups.

Tests failing or not compiling?

• If you see "cannot find function", make sure use super::*; is at the top of your mod tests block.
• If you see "unused import", confirm that use std::collections::HashMap; is on the very first line of the file and that two_sum uses it.
• Check that new tests are inside the existing mod tests { ... } block, not outside it.

Help me fix my HashMap Two Sum tests

Document the pattern recognition rule

Working code is only half the value. The other half is knowing when to reach for this pattern on a new problem.

• Add this comment block between the two_sum function and the #[cfg(test)] module:

// PATTERN RECOGNITION:
// Use HashMap when:
// - You need to check if a complement/partner/difference exists
// - You need O(1) lookup for previously seen values
// - Problem says "find two elements that satisfy condition X"
// - You are trading O(n) space for O(n) time (down from O(n^2))

Why write this down?

When you face a new problem, you do not want to re-derive the insight. These rules give you a checklist: if the problem matches any of these shapes, reach for a HashMap first.

• Save src/hashmap_pattern.rs.

Before you run the tests one final time, predict: will the number of passing tests change after adding comments?

• Confirm nothing broke by running:

cargo test hashmap

Still 7 tests passing. Comments do not affect compilation or test execution.

✔️ Awesome, I've got everything!

Confirm you have saved src/hashmap_pattern.rs and all 7 tests pass when you run cargo test hashmap.

ⓧ I'd like to double check the full code

Your src/hashmap_pattern.rs should contain these sections in order. Scroll up and confirm each is present:

• Line 1: use std::collections::HashMap; import.
• The two_sum_brute function with nested loops returning Option<(usize, usize)>.
• The two_sum function using a HashMap to store seen values.
• The // PATTERN RECOGNITION: comment block with four bullet points.
• The #[cfg(test)] mod tests block containing 7 test functions (2 brute force + 5 HashMap).

You now have a working implementation of the most common interview pattern. Next up, you will tackle a problem where HashMap cannot help at all, forcing you to learn a completely different approach.

Implement Two Pointers — Container With Most Water

After solving Two Sum with a HashMap, you might be tempted to reach for the same tool on every problem.

This step introduces Container With Most Water, a problem where HashMap cannot help. The relationship between elements depends on their positions and the gap between them, not on a complement you can look up. Two Pointers solves it in O(n) time because moving the shorter pointer inward never misses the optimal answer.

In this step, get ready to:

• Implement a brute force solution and observe its O(n^2) complexity.
• Implement an optimal Two Pointers solution in O(n) time with O(1) space.
• Document the pattern recognition rule for when Two Pointers applies.

Implement brute force Container With Most Water

The Container With Most Water problem gives you an array of heights. Each height represents a vertical line. You pick two lines and calculate how much water the container between them holds. The area equals the shorter height multiplied by the distance between the lines.

Why can't HashMap solve this?

In Two Sum, each element had a fixed complement you could look up. Here, the "best partner" for a line depends on how far away the other line is AND how tall it is. There is no single value to store or look up. The relationship is positional, not arithmetic.

• Open src/two_pointers.rs in VS Code.
• Delete the placeholder function and replace it with the brute force implementation and its test by pasting this code:

/// Brute force: O(n^2) time, O(1) space
/// Check every pair of lines
pub fn max_area_brute(height: &[i32]) -> i32 {
    let mut max_water = 0;
    for i in 0..height.len() {
        for j in (i + 1)..height.len() {
            let width = (j - i) as i32;
            let h = height[i].min(height[j]);
            max_water = max_water.max(width * h);
        }
    }
    max_water
}

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

    #[test]
    fn test_max_area_brute() {
        assert_eq!(max_area_brute(&[1, 8, 6, 2, 5, 4, 8, 3, 7]), 49);
    }
}

What does this code do?

• The nested loops check every possible pair of lines. For each pair, it calculates the width (distance between indices) and the height (the shorter of the two lines).
• The .min() and .max() methods on primitives keep the code clean. No need for if-else comparisons.
• The test uses the classic LeetCode example: heights [1, 8, 6, 2, 5, 4, 8, 3, 7] with expected answer 49 (lines at indices 1 and 8, heights 8 and 7, width 7).

• Save src/two_pointers.rs.
• Run the brute force test by running this command:

cargo test two_pointers

You should see 1 test passed. The brute force works, but it checks every pair. That is O(n^2) time.

Seeing a compilation error?

• Make sure you deleted the entire pub fn placeholder() {} line before pasting the new code.
• Check that the function signature matches exactly: pub fn max_area_brute(height: &[i32]) -> i32.

Help me debug my max_area_brute compilation error in Rust

Implement the Two Pointers solution

The brute force checks n*(n-1)/2 pairs. The Two Pointers approach starts at both edges and moves inward, solving it in a single pass.

Why does moving the shorter pointer work?

The shorter wall limits the water level. Moving the taller wall inward can only decrease width while the height stays capped at the same short wall. Moving the shorter wall inward might find a taller wall that increases the area enough to compensate for the lost width.

This is a provably safe narrowing of the search space. You never skip a configuration that could be optimal.

• In src/two_pointers.rs, add the optimized function above the #[cfg(test)] line by pasting this code:

/// Optimal: O(n) time, O(1) space
/// Two pointers from edges, move the shorter one inward
pub fn max_area(height: &[i32]) -> i32 {
    let mut left = 0;
    let mut right = height.len() - 1;
    let mut max_water = 0;

    while left < right {
        let width = (right - left) as i32;
        let h = height[left].min(height[right]);
        max_water = max_water.max(width * h);

        if height[left] < height[right] {
            left += 1;
        } else {
            right -= 1;
        }
    }

    max_water
}

What does this code do?

• Two mutable usize indices start at the outer edges of the slice. No extra data structure needed.
• Each iteration computes the area, then moves the pointer with the smaller height inward. The while left < right loop guarantees the pointers converge.
• O(1) extra space and O(n) time. Each element is visited at most once.

• Now add the remaining tests inside the existing mod tests block, below the test_max_area_brute function:

    #[test]
    fn test_max_area_basic() {
        assert_eq!(max_area(&[1, 8, 6, 2, 5, 4, 8, 3, 7]), 49);
    }

    #[test]
    fn test_max_area_two_elements() {
        assert_eq!(max_area(&[1, 1]), 1);
    }

    #[test]
    fn test_max_area_descending() {
        assert_eq!(max_area(&[5, 4, 3, 2, 1]), 6);
    }

    #[test]
    fn test_max_area_equal_heights() {
        assert_eq!(max_area(&[3, 3, 3, 3]), 9);
    }

What do these tests cover?

• The classic example (same as brute force) confirms both approaches agree.
• Two elements is the minimum valid input. Only one container possible.
• Descending heights test the case where the left pointer always moves.
• Equal heights test the else branch. When heights are equal, the right pointer moves.

• Save src/two_pointers.rs.
• Run the tests to confirm both solutions produce the same results:

cargo test two_pointers

You should see 5 tests passed. Both the brute force and the Two Pointers solution agree on every input.

Tests failing or not compiling?

• If you see "cannot find function", make sure max_area is placed above #[cfg(test)], not inside the test module.
• Check that the new tests are inside the mod tests block's closing brace, not after it.

Help me debug my Two Pointers tests

Document the pattern recognition rule

The final piece is a comment block that captures when to reach for Two Pointers on a new problem. This is your cheat sheet for interviews.

• In src/two_pointers.rs, add this comment block between the max_area function and the #[cfg(test)] line:

// PATTERN RECOGNITION:
// Use Two Pointers when:
// - Input is sorted, OR you work with boundaries/extremes of an array
// - You need to find a pair/range that optimizes some metric
// - Moving one pointer narrows the search space provably
// - O(1) extra space is desired
// - HashMap CANNOT help because the relationship depends on positions/distance

How is this different from HashMap's rule?

HashMap solves "does a complement exist?" in O(1). Two Pointers solves "which boundary pair optimizes a metric?" in O(n). The key signal is whether the relationship between elements is arithmetic (complement) or positional (distance, width, area).

• Save src/two_pointers.rs.

Before you run the final check, predict: will adding comments change any test results?

• Confirm everything still compiles and passes by running:

cargo test two_pointers

You should see 5 tests passed, same as before. Comments never affect compilation or test results in Rust.

✔️ Awesome, I've got everything!

Great. Double check you have saved src/two_pointers.rs and all 5 tests pass.

ⓧ I'd like to double check the full code

Scroll up and confirm your src/two_pointers.rs contains these sections in order:

• The max_area_brute function (brute force with nested loops).
• The max_area function (two pointers with left/right indices).
• The PATTERN RECOGNITION comment block.
• The #[cfg(test)] mod tests block with 5 test functions: test_max_area_brute, test_max_area_basic, test_max_area_two_elements, test_max_area_descending, test_max_area_equal_heights.

You now have two patterns in your toolkit: HashMap for complement lookups, and Two Pointers for boundary optimization. Next up, you will tackle a problem that needs BOTH same-direction pointers AND a HashMap to track state inside a sliding window.

Implement Sliding Window — Longest Substring Without Repeating Characters

You now have two patterns in your toolkit: HashMap for complement lookups and Two Pointers for boundary narrowing. Both solved their respective problems in O(n) time. But what happens when you need to find the longest substring with no repeating characters?

A simple pair of converging pointers cannot solve this because you need to track STATE inside the window. You need to know which characters are currently in the substring. Sliding Window combines two same-direction pointers with a HashMap that maintains the window's contents. This is the pattern for any "longest/shortest subarray or substring with property X" problem.

In this step, get ready to:

• Implement the sliding window function using HashMap to track character positions.
• Add comprehensive tests covering edge cases and mixed inputs.
• Document the pattern recognition rule for identifying sliding window problems.

Understand the window mechanics

The problem is: given a string, find the length of the longest substring without repeating characters. The key insight is that you expand a right pointer to explore new characters, and jump the left pointer forward whenever you encounter a repeat.

A HashMap<char, usize> stores the last-seen index of each character. When you see a character that already exists in the map at or after left, you jump left past that position to restore validity.

• In src/sliding_window.rs, delete the placeholder function and replace it with the sliding window implementation:

use std::collections::HashMap;

/// Sliding Window: O(n) time, O(min(n, alphabet_size)) space
/// Track last-seen index of each character, expand right, jump left past repeats
pub fn length_of_longest_substring(s: &str) -> usize {
    let mut char_index: HashMap<char, usize> = HashMap::new();
    let mut left = 0;
    let mut max_len = 0;

    for (right, ch) in s.chars().enumerate() {
        if let Some(&prev_idx) = char_index.get(&ch) {
            left = left.max(prev_idx + 1);
        }
        char_index.insert(ch, right);
        max_len = max_len.max(right - left + 1);
    }

    max_len
}

What does this code do?

• char_index: HashMap<char, usize> stores the last position where each character appeared. This gives O(1) lookup to check for repeats.
• left marks the start of the current valid window. It only moves forward, never backward.
• left = left.max(prev_idx + 1) is the key line. When a repeat is found, it jumps left past the previous occurrence. The .max() ensures it never moves backward (old entries may linger in the map from before the current window).
• right - left + 1 calculates the current window length at each position, tracking the maximum.

Why not Two Pointers here?

In Container With Most Water, you didn't need to know what was between the two pointers. Here, you need to know exactly which characters are inside the current window. That state tracking is what separates Sliding Window from plain Two Pointers.

• Save src/sliding_window.rs.
• Verify it compiles by running:

cargo check

You should see no errors. The function compiles but has no tests yet.

Seeing a compile error?

• Make sure you deleted the pub fn placeholder() {} line. The file should only contain the new function.
• Check that use std::collections::HashMap; is the very first line of the file.

Help me debug my sliding_window.rs compile error.

Add comprehensive tests

Good tests for substring problems cover boundary conditions: empty input, single characters, all-same characters, and inputs with no repeats at all. These edge cases catch off-by-one errors in the window logic.

• Add the test module with edge case tests at the bottom of src/sliding_window.rs, below the pattern recognition comment placeholder (you will add the comment in the next substep):

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

    #[test]
    fn test_empty_string() {
        assert_eq!(length_of_longest_substring(""), 0);
    }

    #[test]
    fn test_single_char() {
        assert_eq!(length_of_longest_substring("a"), 1);
    }

    #[test]
    fn test_all_same() {
        assert_eq!(length_of_longest_substring("aaaa"), 1);
    }

    #[test]
    fn test_no_repeats() {
        assert_eq!(length_of_longest_substring("abcd"), 4);
    }
}

What do these tests cover?

• Empty string tests that the function handles zero-length input gracefully (returns 0).
• Single char confirms the base case of a one-character window.
• All same ("aaaa") tests that the left pointer jumps correctly on every character.
• No repeats ("abcd") tests that the window expands to the full string length.

• Save src/sliding_window.rs and run the edge case tests:

cargo test sliding_window

You should see 4 tests pass. The edge cases confirm your window logic handles boundaries correctly.

Now add the mixed-input tests that exercise the full sliding window behavior. These are the classic LeetCode examples.

• Inside your mod tests block, add these tests before the closing }:

    #[test]
    fn test_abcabcbb() {
        assert_eq!(length_of_longest_substring("abcabcbb"), 3);
    }

    #[test]
    fn test_pwwkew() {
        assert_eq!(length_of_longest_substring("pwwkew"), 3);
    }

    #[test]
    fn test_with_spaces() {
        assert_eq!(length_of_longest_substring("hello world"), 6);
    }

Why these specific test cases?

• "abcabcbb" returns 3 ("abc"). The window must contract when a repeats at index 3.
• "pwwkew" returns 3 ("wke" or "kew"). Tests that the window recovers after consecutive repeats.
• "hello world" returns 6 ("o worl" or similar). Confirms spaces count as valid characters.

• Save src/sliding_window.rs.

Before you run the tests again, predict: will all 7 tests pass, or will the mixed-input cases reveal a bug in the window logic?

• Run the full test suite for this module:

cargo test sliding_window

You should see all 7 tests pass. The left.max(prev_idx + 1) pattern handles every case correctly because it never moves the left pointer backward.

Tests failing?

• If test_all_same fails, check that you have left = left.max(prev_idx + 1) and not left = prev_idx + 1. Without .max(), left can jump backward.
• If test_with_spaces fails, make sure you are iterating with s.chars().enumerate() and not byte indexing.

Help me debug my sliding window tests.

Write the pattern recognition rule

Just like the previous modules, you will document when to reach for this pattern. The next time you see a problem asking for the "longest substring with property X", this comment block tells you exactly what to do.

• In src/sliding_window.rs, add this comment block between the length_of_longest_substring function and the #[cfg(test)] line:

// PATTERN RECOGNITION:
// Use Sliding Window when:
// - Problem asks for longest/shortest subarray or substring with a condition
// - You need to track a running state (frequency, sum, character set) in the window
// - The window only moves forward (left pointer never goes backward)
// - Often combines with HashMap for O(1) state tracking within the window
// - Key insight: expand right to explore, contract left to restore validity

How does this differ from Two Pointers?

Two Pointers converge from opposite ends and need no state between the pointers. Sliding Window moves both pointers in the same direction and maintains a data structure (often a HashMap) tracking what is inside the current window.

The signal is the problem's phrasing. "Longest/shortest subarray or substring with condition X" almost always means Sliding Window.

• Save src/sliding_window.rs.

✔️ Awesome, I've got everything!

Great. Double check you have saved the file.

ⓧ I'd like to double check the full code

Your src/sliding_window.rs should contain these sections in order:

• The use std::collections::HashMap; import at the top.
• The length_of_longest_substring function with doc comments, HashMap, left/right pointers, and the left.max(prev_idx + 1) pattern.
• The PATTERN RECOGNITION comment block (5 bullet points about when to use Sliding Window).
• The #[cfg(test)] mod tests block with all 7 tests: empty string, single char, all same, no repeats, abcabcbb, pwwkew, with spaces.

Scroll up and confirm each chunk is present in your file.

Three patterns down. You can now solve complement lookups (HashMap), boundary optimization (Two Pointers), and substring/subarray condition problems (Sliding Window). Next up, you will tackle the only O(log n) pattern: Binary Search on sorted data.

Implement Binary Search — Halving the Search Space

Your Sliding Window solution tracks state across a moving window. Now you have a different scenario: the data is already sorted, and you need to find a single value.

When data is sorted, you can eliminate half the remaining candidates with a single comparison. Binary Search is the only pattern in this project with O(log n) time. Recognizing "the input is sorted and I need to find a position" should trigger this pattern immediately.

In this step, get ready to:

• Implement standard binary search with O(log n) time using Rust's Ordering enum.
• Implement Search Insert Position, a variant that finds where a value belongs in sorted order.
• Document the pattern recognition rule for when binary search is the right tool.

Implement standard binary search

The key insight is the exclusive upper bound pattern: right starts at nums.len() (one past the last index), and the loop runs while left < right. This matches Rust's range conventions and avoids off-by-one errors.

• Open src/binary_search.rs in VS Code.
• Delete the placeholder function and replace the entire file contents with the following code:

use std::cmp::Ordering;

/// Standard Binary Search: O(log n) time, O(1) space
/// Find exact target in sorted slice, return its index
pub fn binary_search(nums: &[i32], target: i32) -> Option<usize> {
    let mut left: usize = 0;
    let mut right: usize = nums.len();

    while left < right {
        let mid = left + (right - left) / 2;
        match nums[mid].cmp(&target) {
            Ordering::Equal => return Some(mid),
            Ordering::Less => left = mid + 1,
            Ordering::Greater => right = mid,
        }
    }

    None
}

What does this code do?

• use std::cmp::Ordering imports the enum with variants Equal, Less, and Greater for clean comparisons.
• left + (right - left) / 2 computes the midpoint without integer overflow. In other languages, (left + right) / 2 can overflow. This habit transfers.
• The match expression branches on the comparison result. If equal, return immediately. If the midpoint is too small, discard the left half. If too large, discard the right half.
• When left == right, the search space is empty. Return None.

Now add tests that cover the important edge cases: target found in the middle, at the start, at the end, not present, and on an empty slice.

• Add the following test module at the bottom of src/binary_search.rs:

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

    #[test]
    fn test_binary_search_found() {
        assert_eq!(binary_search(&[1, 3, 5, 7, 9], 5), Some(2));
    }

    #[test]
    fn test_binary_search_first() {
        assert_eq!(binary_search(&[1, 3, 5, 7, 9], 1), Some(0));
    }

    #[test]
    fn test_binary_search_last() {
        assert_eq!(binary_search(&[1, 3, 5, 7, 9], 9), Some(4));
    }

    #[test]
    fn test_binary_search_not_found() {
        assert_eq!(binary_search(&[1, 3, 5, 7, 9], 4), None);
    }

    #[test]
    fn test_binary_search_empty() {
        assert_eq!(binary_search(&[], 5), None);
    }
}

Why these specific test cases?

Binary search has classic off-by-one failure modes. Testing the first element, last element, and a missing value catches the most common bugs in boundary logic.

• Save src/binary_search.rs.
• Run the binary search tests by running this command:

cargo test binary_search

You should see 5 tests pass with output showing each test name in green.

Seeing a compilation error?

• Make sure use std::cmp::Ordering; is at the very top of the file. Without it, the match arms won't resolve.
• Check that pub fn placeholder() {} is fully deleted. A leftover function won't break compilation but signals you didn't replace the file correctly.
• Confirm the #[cfg(test)] and mod tests block is inside the same file, not in a separate file.

Why won't my binary search tests compile?

Implement Search Insert Position

Standard binary search returns None when the target is missing. But many problems ask: "where would this value go if I inserted it?" The structure is nearly identical, but instead of returning None, you return left. That is the position where the target belongs to maintain sorted order.

• In src/binary_search.rs, add the following function between the binary_search function and the #[cfg(test)] block:

/// Search Insert Position: O(log n) time, O(1) space
/// Find index where target is or would be inserted to keep sorted order
pub fn search_insert(nums: &[i32], target: i32) -> usize {
    let mut left: usize = 0;
    let mut right: usize = nums.len();

    while left < right {
        let mid = left + (right - left) / 2;
        if nums[mid] < target {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    left
}

What changed from the standard version?

• No match on Ordering. Instead, a simple if nums[mid] < target check. If the midpoint is smaller, the target belongs further right. Otherwise (equal or greater), narrow from the right.
• The return type is usize instead of Option<usize>. The answer always exists: either the target's current index or its correct insertion point.
• When the loop ends, left is the boundary where all elements to its left are strictly less than target. That is exactly the insertion point.

Now add tests for the insertion cases. These need to cover: target already present, target between two elements, target before all elements, and target after all elements.

• Add these tests inside the existing mod tests block, after the test_binary_search_empty test:

    #[test]
    fn test_search_insert_present() {
        assert_eq!(search_insert(&[1, 3, 5, 6], 5), 2);
    }

    #[test]
    fn test_search_insert_between() {
        assert_eq!(search_insert(&[1, 3, 5, 6], 2), 1);
    }

    #[test]
    fn test_search_insert_before_all() {
        assert_eq!(search_insert(&[1, 3, 5, 6], 0), 0);
    }

    #[test]
    fn test_search_insert_after_all() {
        assert_eq!(search_insert(&[1, 3, 5, 6], 7), 4);
    }

Why test the extremes?

Inserting before all elements tests that left stays at 0. Inserting after all elements tests that left reaches nums.len(). These are the two boundary traps that catch most binary search bugs.

• Save src/binary_search.rs.
• Run the tests again by running:

cargo test binary_search

You should now see 9 tests passing: 5 for binary_search and 4 for search_insert.

Tests failing for search_insert?

• Check that search_insert returns left (not right or mid). When the loop exits, left == right, but the convention is to return left.
• Make sure the condition is if nums[mid] < target (strictly less than). Using <= changes the behavior when the target is already present.
• Confirm the new tests are inside the existing mod tests { ... } block, not in a second test module.

Why is my search_insert returning the wrong index?

Write the pattern recognition rule

Like the previous modules, finish with a comment block that documents when to reach for binary search on a new problem.

• In src/binary_search.rs, add the following comment block between the search_insert function and the #[cfg(test)] block:

// PATTERN RECOGNITION:
// Use Binary Search when:
// - Input is sorted (or there is a monotonic condition)
// - You need to find an exact value or the boundary where a condition flips
// - O(log n) is expected or required
// - Variant: "binary search on answer" - search space is a range of possible
//   answers, not array indices (e.g., "minimum capacity to ship packages")

What is binary search on answer?

Some problems don't search an array at all. Instead, the "search space" is a range of possible answers (e.g., 1 to 1,000,000). You check if a given answer is feasible, then binary search over that range. The structure is identical: halve the space each iteration.

• Save src/binary_search.rs.

Before you run the final check, predict: will all tests across all four modules pass? Is there any reason a change in binary_search.rs could break the other modules?

• Run the full test suite by running:

cargo test

All tests across all four modules pass. Each module is isolated, so changes in one cannot affect another. You should see all tests green across hashmap_pattern, two_pointers, sliding_window, and binary_search.

✔️ Awesome, I've got everything!

Great. Double check you have saved src/binary_search.rs and all 9 binary search tests pass.

ⓧ I'd like to double check the full code

Here is the complete src/binary_search.rs file. Scroll through each section and confirm yours matches:

• The use std::cmp::Ordering; import at the top.
• The binary_search function using a match on Ordering.
• The search_insert function using an if/else and returning left.
• The PATTERN RECOGNITION comment block.
• The #[cfg(test)] mod tests block with 9 test functions (5 for binary_search, 4 for search_insert).

Secret mission

Implement 3Sum with Sorting + Two Pointers

3Sum is one of the top-5 most-asked interview questions. It requires combining two patterns you already know: sorting as preprocessing, plus Two Pointers for the inner search. Can you solve it while handling the tricky deduplication logic?

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your project folder to continue practicing, or delete it entirely.

Resources you used:

• The dsa-patterns project folder on your Desktop (local files only).

Keep everything running

No action needed. Choose this if you want to keep practicing by adding more LeetCode problems to your pattern library.

• Your dsa-patterns folder stays on your Desktop, ready for you to add new modules.
• Run cargo test any time to verify all your solutions still pass.

Pause - I'll come back to this later

There are no running processes or services to shut down. Your project is just files on disk.

• Your dsa-patterns folder will be waiting on your Desktop whenever you return.
• No memory or CPU is consumed while the project sits idle.

Delete - I don't want to use this again

Remove all project files and start fresh if you ever want to redo this project.

• Delete the project folder by running this command in your terminal (macOS/Linux):

rm -rf ~/Desktop/dsa-patterns

• On Windows, run this in PowerShell:

Remove-Item -Recurse -Force ~\Desktop\dsa-patterns

• Confirm the folder is gone by running ls ~/Desktop (macOS/Linux) or ls ~\Desktop (Windows). You should no longer see dsa-patterns in the output.

That's a Wrap!

That's a Wrap!

Nice work. You just built a test-driven Rust library that implements 4 core algorithmic patterns, each backed by passing tests and a documented recognition rule.

You've learned how to:

• Solve problems using HashMap, Two Pointers, Sliding Window, and Binary Search patterns in Rust, transforming O(n²) brute-force solutions into O(n) and O(log n) optimized versions.
• Recognize a problem's shape (complement lookup, narrowing bounds, expanding window, sorted search) and pick the right data structure before writing code.
• Exercise Rust's ownership and borrowing model in algorithmic contexts, including slices, iterators, HashMap, and match on Ordering.
• Secret Mission: Implemented 3Sum by combining sorting with Two Pointers and deduplication logic.

Ready to quiz yourself?