LeetCode Patterns for Rust Systems Interviews

Purpose: Insurance for companies that include LeetCode rounds. Focus on patterns, not grinding. These are easy-medium problems that actually appear in systems interviews.

How to Use This

Don't memorize solutions. Learn patterns.

Each pattern appears in 10+ problems. Learn the pattern once, solve many problems.

Time investment: 15-20 hours for all patterns Coverage: 80% of easy-medium LeetCode questions in systems interviews

Pattern 1: Hash Map (Frequency Counting)

When to use: Count occurrences, find complements, detect duplicates

Common problems: Two Sum, Contains Duplicate, Valid Anagram, Group Anagrams

Template

#![allow(unused)]
fn main() {
use std::collections::HashMap;

fn solve_with_hash_map(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    let mut seen: HashMap<i32, usize> = HashMap::new();

    for (i, &num) in nums.iter().enumerate() {
        // Check if complement exists
        if let Some(&j) = seen.get(&(target - num)) {
            return Some((j, i));
        }
        // Add current number to map
        seen.insert(num, i);
    }

    None
}
}

Interview Answer

"I use a hash map to store numbers I've seen. For each number, I check if its complement (target - num) exists in the map. If yes, I found the pair. If not, I add the current number and continue. This is O(n) time and O(n) space."

Variations

#![allow(unused)]
fn main() {
// Count frequencies
use std::collections::HashMap;

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

// Detect duplicate
fn contains_duplicate(nums: &[i32]) -> bool {
    let mut seen: std::collections::HashSet<i32> = std::collections::HashSet::new();
    for &num in nums {
        if !seen.insert(num) {
            return true; // Already exists
        }
    }
    false
}

// Group anagrams
fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
    use std::collections::HashMap;

    let mut groups: HashMap<String, Vec<String>> = HashMap::new();

    for s in strs {
        let mut key: Vec<char> = s.chars().collect();
        key.sort();
        let key_str: String = key.into_iter().collect();

        groups.entry(key_str).or_insert_with(Vec::new).push(s);
    }

    groups.into_values().collect()
}
}

Pattern 2: Sliding Window

When to use: Subarray problems, contiguous sequences, window constraints

Common problems: Maximum Average Subarray, Longest Substring Without Repeating, Permutation in String

Template

#![allow(unused)]
fn main() {
fn sliding_window_template(arr: &[i32], k: usize) -> i32 {
    if arr.len() < k {
        return 0;
    }

    // Initialize first window
    let mut window_sum: i32 = arr[..k].iter().sum();
    let mut max_sum = window_sum;

    // Slide window
    for i in k..arr.len() {
        window_sum += arr[i] - arr[i - k];
        max_sum = max_sum.max(window_sum);
    }

    max_sum
}
}

Interview Answer

"I use a sliding window. First, I calculate the sum of the first k elements. Then I slide the window by one element at a time: add the new element, subtract the element leaving the window. Track the maximum throughout. This is O(n) time and O(1) space."

Variations

#![allow(unused)]
fn main() {
// Fixed window: Maximum average subarray
fn find_max_average(nums: Vec<i32>, k: i32) -> f64 {
    let k = k as usize;
    let mut sum: i64 = nums[..k].iter().map(|&x| x as i64).sum();
    let mut max_sum = sum;

    for i in k..nums.len() {
        sum += nums[i] as i64 - nums[i - k] as i64;
        max_sum = max_sum.max(sum);
    }

    max_sum as f64 / k as f64
}

// Variable window: Longest substring without repeating
use std::collections::HashSet;

fn length_of_longest_substring(s: String) -> i32 {
    let mut chars: HashSet<char> = HashSet::new();
    let mut left = 0;
    let mut max_len = 0;

    for (right, ch) in s.chars().enumerate() {
        // Shrink window until no duplicate
        while chars.contains(&ch) {
            chars.remove(&s.chars().nth(left).unwrap());
            left += 1;
        }

        chars.insert(ch);
        max_len = max_len.max(right - left + 1);
    }

    max_len as i32
}

// String permutation check
fn check_inclusion(s1: String, s2: String) -> bool {
    if s1.len() > s2.len() {
        return false;
    }

    let k = s1.len();
    let mut s1_count = [0; 26];
    let mut s2_count = [0; 26];

    for ch in s1.bytes() {
        s1_count[(ch - b'a') as usize] += 1;
    }

    for (i, ch) in s2.bytes().enumerate() {
        s2_count[(ch - b'a') as usize] += 1;

        if i >= k {
            let left_ch = s2.as_bytes()[i - k];
            s2_count[(left_ch - b'a') as usize] -= 1;
        }

        if i >= k - 1 && s1_count == s2_count {
            return true;
        }
    }

    false
}
}

Pattern 3: Two Pointers

When to use: Sorted arrays, pair finding, partitioning

Common problems: Two Sum II (Sorted), Valid Palindrome, Container With Most Water

Template

#![allow(unused)]
fn main() {
fn two_pointers_template(arr: &[i32], target: i32) -> Option<(usize, usize)> {
    let mut left = 0;
    let mut right = arr.len() - 1;

    while left < right {
        let sum = arr[left] + arr[right];

        if sum == target {
            return Some((left, right));
        } else if sum < target {
            left += 1;
        } else {
            right -= 1;
        }
    }

    None
}
}

Interview Answer

"I use two pointers starting from both ends of the sorted array. I check their sum. If it equals the target, I'm done. If it's less than target, I move the left pointer right to increase the sum. If it's more, I move the right pointer left to decrease the sum. This is O(n) time and O(1) space."

Variations

#![allow(unused)]
fn main() {
// Valid palindrome
fn is_palindrome(s: String) -> bool {
    let chars: Vec<char> = s.chars().collect();
    let mut left = 0;
    let mut right = chars.len() - 1;

    while left < right {
        if !chars[left].is_alphanumeric() {
            left += 1;
            continue;
        }
        if !chars[right].is_alphanumeric() {
            right -= 1;
            continue;
        }
        if chars[left].to_lowercase().ne(&chars[right].to_lowercase()) {
            return false;
        }
        left += 1;
        right -= 1;
    }

    true
}

// Container with most water
fn max_area(height: Vec<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
}

// Remove duplicates from sorted array
fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
    if nums.is_empty() {
        return 0;
    }

    let mut write_idx = 1;

    for read_idx in 1..nums.len() {
        if nums[read_idx] != nums[read_idx - 1] {
            nums[write_idx] = nums[read_idx];
            write_idx += 1;
        }
    }

    write_idx as i32
}
}

Pattern 4: Fast/Slow Pointers (Linked List Cycle Detection)

When to use: Cycles in linked lists, middle of list, circular arrays

Common problems: Linked List Cycle, Middle of Linked List, Happy Number

Template

#![allow(unused)]
fn main() {
fn has_cycle(head: Option<&ListNode>) -> bool {
    let mut slow = head;
    let mut fast = head;

    while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
        slow = slow.unwrap().next;
        fast = fast.unwrap().next.as_ref().unwrap().next;

        if slow == fast {
            return true;
        }
    }

    false
}
}

Interview Answer

"I use Floyd's cycle detection algorithm with two pointers. One moves one step at a time (slow), the other moves two steps (fast). If there's a cycle, fast will eventually catch up to slow. If there's no cycle, fast reaches the end. This is O(n) time and O(1) space."

Variations

#![allow(unused)]
fn main() {
// Find middle of linked list
fn middle_node(head: Option<&ListNode>) -> Option<&ListNode> {
    let mut slow = head;
    let mut fast = head;

    while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
        slow = slow.unwrap().next;
        fast = fast.unwrap().next.as_ref().unwrap().next;
    }

    slow
}

// Find cycle start
fn detect_cycle(head: Option<&ListNode>) -> Option<&ListNode> {
    let mut slow = head;
    let mut fast = head;

    // Detect if cycle exists
    while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
        slow = slow.unwrap().next;
        fast = fast.unwrap().next.as_ref().unwrap().next;

        if slow == fast {
            break;
        }
    }

    // No cycle
    if fast.is_none() || fast.as_ref().unwrap().next.is_none() {
        return None;
    }

    // Find cycle start
    slow = head;
    while slow != fast {
        slow = slow.unwrap().next;
        fast = fast.unwrap().next;
    }

    slow
}

#[derive(PartialEq)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}
}

Pattern 5: Tree Traversal (DFS)

When to use: Tree problems, recursion, hierarchical data

Common problems: Maximum Depth, Same Tree, Subtree of Another Tree, Validate BST

Template

#![allow(unused)]
fn main() {
fn dfs_template(root: Option<&TreeNode>) -> i32 {
    match root {
        None => 0,
        Some(node) => {
            let left = dfs_template(node.left.as_deref());
            let right = dfs_template(node.right.as_deref());
            left.max(right) + 1
        }
    }
}
}

Interview Answer

"I use depth-first search recursively. For each node, I recursively process its left and right children. The base case is when the node is null. I combine results from left and right subtrees. This is O(n) time and O(h) space where h is tree height."

Variations

#![allow(unused)]
fn main() {
// Maximum depth
fn max_depth(root: Option<&TreeNode>) -> i32 {
    match root {
        None => 0,
        Some(node) => {
            1 + max_depth(node.left.as_deref())
                .max(max_depth(node.right.as_deref()))
        }
    }
}

// Same tree check
fn is_same_tree(p: Option<&TreeNode>, q: Option<&TreeNode>) -> bool {
    match (p, q) {
        (None, None) => true,
        (None, Some(_)) | (Some(_), None) => false,
        (Some(p_node), Some(q_node)) => {
            p_node.val == q_node.val
                && is_same_tree(p_node.left.as_deref(), q_node.left.as_deref())
                && is_same_tree(p_node.right.as_deref(), q_node.right.as_deref())
        }
    }
}

// Validate BST
fn is_valid_bst(root: Option<&TreeNode>) -> bool {
    fn validate(node: Option<&TreeNode>, min: i64, max: i64) -> bool {
        match node {
            None => true,
            Some(n) => {
                let val = n.val as i64;
                val > min && val < max
                    && validate(n.left.as_deref(), min, val)
                    && validate(n.right.as_deref(), val, max)
            }
        }
    }

    validate(root, i64::MIN, i64::MAX)
}

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Box<TreeNode>>,
    pub right: Option<Box<TreeNode>>,
}
}

Pattern 6: BFS (Level Order Traversal)

When to use: Level-order traversal, shortest path in unweighted graph

Common problems: Binary Tree Level Order, Word Ladder, Minimum Depth

Template

#![allow(unused)]
fn main() {
use std::collections::VecDeque;

fn bfs_template(root: Option<&TreeNode>) -> Vec<Vec<i32>> {
    let mut result = Vec::new();
    let mut queue = VecDeque::new();

    if let Some(node) = root {
        queue.push_back(node);
    }

    while !queue.is_empty() {
        let level_size = queue.len();
        let mut level = Vec::new();

        for _ in 0..level_size {
            if let Some(node) = queue.pop_front() {
                level.push(node.val);

                if let Some(left) = &node.left {
                    queue.push_back(left);
                }
                if let Some(right) = &node.right {
                    queue.push_back(right);
                }
            }
        }

        result.push(level);
    }

    result
}
}

Interview Answer

"I use breadth-first search with a queue. I start with the root node, then process level by level. For each node, I add its children to the queue. I track the number of nodes at each level to separate levels. This is O(n) time and O(w) space where w is maximum width."

Variations

#![allow(unused)]
fn main() {
// Minimum depth of binary tree
fn min_depth(root: Option<&TreeNode>) -> i32 {
    use std::collections::VecDeque;

    let mut queue = VecDeque::new();
    if let Some(node) = root {
        queue.push_back((node, 1));
    }

    while let Some((node, depth)) = queue.pop_front() {
        if node.left.is_none() && node.right.is_none() {
            return depth;
        }

        if let Some(left) = &node.left {
            queue.push_back((left, depth + 1));
        }
        if let Some(right) = &node.right {
            queue.push_back((right, depth + 1));
        }
    }

    0
}

// Level order successor
fn level_order_successor(root: &TreeNode, key: i32) -> Option<i32> {
    use std::collections::VecDeque;

    let mut queue = VecDeque::new();
    queue.push_back(root);

    while let Some(node) = queue.pop_front() {
        if node.val == key {
            return queue.front().map(|n| n.val);
        }

        if let Some(left) = &node.left {
            queue.push_back(left);
        }
        if let Some(right) = &node.right {
            queue.push_back(right);
        }
    }

    None
}
}

Pattern 7: DFS (Graph Traversal)

When to use: Pathfinding, connectivity, cycle detection in graphs

Common problems: Number of Islands, Clone Graph, Course Schedule, Valid Tree

Template

#![allow(unused)]
fn main() {
fn dfs_graph_template(graph: &Vec<Vec<usize>>, start: usize, visited: &mut Vec<bool>) {
    visited[start] = true;

    for &neighbor in &graph[start] {
        if !visited[neighbor] {
            dfs_graph_template(graph, neighbor, visited);
        }
    }
}
}

Interview Answer

"I use depth-first search to traverse the graph. I mark each node as visited when I first encounter it. For unvisited neighbors, I recursively continue the traversal. This is O(V + E) time where V is vertices and E is edges."

Variations

#![allow(unused)]
fn main() {
// Number of islands
fn num_islands(grid: &mut Vec<Vec<char>>) -> i32 {
    if grid.is_empty() {
        return 0;
    }

    let mut count = 0;
    let rows = grid.len();
    let cols = grid[0].len();

    for i in 0..rows {
        for j in 0..cols {
            if grid[i][j] == '1' {
                count += 1;
                dfs_islands(grid, i, j);
            }
        }
    }

    count
}

fn dfs_islands(grid: &mut Vec<Vec<char>>, i: usize, j: usize) {
    let rows = grid.len();
    let cols = grid[0].len();

    if i >= rows || j >= cols || grid[i][j] != '1' {
        return;
    }

    grid[i][j] = '0'; // Mark as visited

    dfs_islands(grid, i + 1, j);
    dfs_islands(grid, i, j + 1);
    if i > 0 { dfs_islands(grid, i - 1, j); }
    if j > 0 { dfs_islands(grid, i, j - 1); }
}

// Clone graph
use std::collections::HashMap;

fn clone_graph(node: Option<&Node>) -> Option<Node> {
    fn dfs(node: &Node, cloned: &mut HashMap<i32, Node>) -> Node {
        if let Some(cloned_node) = cloned.get(&node.val) {
            return cloned_node.clone();
        }

        let new_node = Node {
            val: node.val,
            neighbors: Vec::new(),
        };
        cloned.insert(node.val, new_node.clone());

        for neighbor in &node.neighbors {
            new_node.neighbors.push(dfs(neighbor, cloned));
        }

        new_node
    }

    node.map(|n| dfs(&n, &mut HashMap::new()))
}

#[derive(Debug, Clone)]
pub struct Node {
    pub val: i32,
    pub neighbors: Vec<Node>,
}
}

Pattern 8: Stack (Monotonic)

When to use: Nested structures, matching pairs, next greater element

Common problems: Valid Parentheses, Min Stack, Daily Temperatures, Largest Rectangle

Template

#![allow(unused)]
fn main() {
fn valid_parentheses(s: String) -> bool {
    let mut stack: Vec<char> = Vec::new();
    let mapping = [(')', '('], ('}', '{'), (']', '[')];

    for ch in s.chars() {
        if ch == '(' || ch == '{' || ch == '[' {
            stack.push(ch);
        } else {
            if let Some(&top) = stack.last() {
                if mapping.iter().any(|&(close, open)| close == ch && open == top) {
                    stack.pop();
                } else {
                    return false;
                }
            } else {
                return false;
            }
        }
    }

    stack.is_empty()
}
}

Interview Answer

"I use a stack to match opening and closing brackets. When I see an opening bracket, I push it. When I see a closing bracket, I check if it matches the top of the stack. If yes, I pop. If no or stack is empty, it's invalid. At the end, stack should be empty. This is O(n) time and O(n) space."

Variations

#![allow(unused)]
fn main() {
// Min stack
use std::collections::VecDeque;

struct MinStack {
    stack: Vec<(i32, i32)>, // (value, current_min)
}

impl MinStack {
    fn new() -> Self {
        MinStack { stack: Vec::new() }
    }

    fn push(&mut self, val: i32) {
        let min = if let Some(&(_, current_min)) = self.stack.last() {
            current_min.min(val)
        } else {
            val
        };
        self.stack.push((val, min));
    }

    fn pop(&mut self) {
        self.stack.pop();
    }

    fn top(&self) -> i32 {
        self.stack.last().unwrap().0
    }

    fn get_min(&self) -> i32 {
        self.stack.last().unwrap().1
    }
}

// Daily temperatures (next greater element)
fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
    let n = temperatures.len();
    let mut answer = vec![0; n];
    let mut stack: Vec<usize> = Vec::new(); // indices

    for i in 0..n {
        while let Some(&j) = stack.last() {
            if temperatures[i] > temperatures[j] {
                answer[j] = (i - j) as i32;
                stack.pop();
            } else {
                break;
            }
        }
        stack.push(i);
    }

    answer
}
}

Pattern 9: Binary Search

When to use: Sorted arrays, search space reduction, monotonic functions

Common problems: Binary Search, Search in Rotated Array, Find Peak Element

Template

#![allow(unused)]
fn main() {
fn binary_search_template(nums: &[i32], target: i32) -> Option<usize> {
    let mut left = 0;
    let mut right = nums.len() - 1;

    while left <= right {
        let mid = left + (right - left) / 2;

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

    None
}
}

Interview Answer

"I use binary search on the sorted array. I maintain left and right pointers. In each iteration, I check the middle element. If it equals the target, I return. If it's less, I search the right half. If it's more, I search the left half. This is O(log n) time and O(1) space."

Variations

#![allow(unused)]
fn main() {
// Search in rotated sorted array
fn search(nums: Vec<i32>, target: i32) -> i32 {
    let mut left = 0;
    let mut right = nums.len() - 1;

    while left <= right {
        let mid = left + (right - left) / 2;

        if nums[mid] == target {
            return mid as i32;
        }

        // Left half is sorted
        if nums[left] <= nums[mid] {
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // Right half is sorted
        else {
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    -1
}

// Find minimum in rotated sorted array
fn find_min(nums: Vec<i32>) -> i32 {
    let mut left = 0;
    let mut right = nums.len() - 1;

    while left < right {
        let mid = left + (right - left) / 2;

        if nums[mid] > nums[right] {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    nums[left]
}
}

Pattern 10: Dynamic Programming (1D)

When to use: Optimization with overlapping subproblems, optimal substructure

Common problems: Climbing Stairs, House Robber, Best Time to Buy/Sell Stock

Template

#![allow(unused)]
fn main() {
fn dp_template(n: usize) -> i32 {
    if n <= 1 {
        return n as i32;
    }

    let mut dp = vec![0; n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for i in 2..=n {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    dp[n]
}
}

Interview Answer

"I use dynamic programming. I define dp[i] as the answer for subproblem i. I build up the solution from smaller subproblems. Each dp[i] depends on previous computed values. I optimize space by only keeping the last two values. This is O(n) time and O(1) space."

Variations

#![allow(unused)]
fn main() {
// Climbing stairs
fn climb_stairs(n: i32) -> i32 {
    if n <= 2 {
        return n;
    }

    let mut prev2 = 1;
    let mut prev1 = 2;

    for _ in 3..=n {
        let current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    prev1
}

// House robber
fn rob(nums: Vec<i32>) -> i32 {
    let mut prev1 = 0; // max money if we don't rob current
    let mut prev2 = 0; // max money if we rob current

    for num in nums {
        let current = prev1.max(prev2 + num);
        prev2 = prev1;
        prev1 = current;
    }

    prev1
}

// Best time to buy and sell stock
fn max_profit(prices: Vec<i32>) -> i32 {
    let mut min_price = i32::MAX;
    let mut max_profit = 0;

    for price in prices {
        min_price = min_price.min(price);
        max_profit = max_profit.max(price - min_price);
    }

    max_profit
}
}

Quick Reference for Interviews

When to use which pattern:

Time to learn each pattern: 1-2 hours Total time for all patterns: 15-20 hours Coverage: 80% of easy-medium LeetCode in systems interviews

How to Practice

Don't grind 500 problems. Practice these patterns:

1. Learn the pattern (30 minutes)

   • Read the template
   • Understand the approach
   • Memorize the interview answer

2. Implement variations (1-2 hours)

   • Do 5-10 problems using this pattern
   • Focus on the pattern, not the problem

3. Whiteboard practice (30 minutes)

   • Write the template from memory
   • Explain it out loud
   • Do this for each pattern

Total: 2-3 hours per pattern × 10 patterns = 20-30 hours

This is enough for 90% of easy-medium LeetCode in systems interviews.