LeetCode 75 study plan solutions

This is a record of my solving of the LeetCode 75 study plan, in August/September 2026.

Some problems are commented, and for some just a final solution is given.

Array/String

1768. Merge Strings Alternately

zip chars + append the remains

pub fn merge_alternately(word1: String, word2: String) -> String {
  let m1 = word1.chars().zip(word2.chars()).map(|(a, b)| format!("{a}{b}")).join("");
  let m2 = if word1.len() > word2.len() { &word1[word2.len()..] } else { &word2[word1.len()..] };
  m1 + m2
}

1071. Greatest Common Divisor of Strings

Try all possible lengths $(0..min\left(|𝑎|,|𝑏|\right)$ and check if both lens divisible by it and same prefix and trim_start_matches leaves an empty string

pub fn gcd_of_strings(str1: String, str2: String) -> String {
  (1..=str1.len().min(str2.len()))
    .rev()
    .find(|n| str1.len().is_multiple_of(*n) && str2.len().is_multiple_of(*n)
        && &str1[..*n] == &str2[..*n]
        && str1.trim_start_matches(&str1[..*n]).is_empty()
        && str2.trim_start_matches(&str1[..*n]).is_empty()
    )
    .map(|n| str1[..n].to_string())
    .unwrap_or_default()
}

1431. Kids With the Greatest Number of Candies

Find maximum + map over array

pub fn kids_with_candies(candies: Vec<i32>, extra_candies: i32) -> Vec<bool> {
  let max = candies.iter().max().unwrap();
  candies.iter().map(|c| c + extra_candies >= *max).collect()
}

605. Can Place Flowers

Greedy solution works, after correcting a bug - not looking to the right

pub fn can_place_flowers(flowerbed: Vec<i32>, n: i32) -> bool {
  flowerbed.iter().enumerate().fold((n, false), |(n, p), (i, c)| {
    if *c == 0 && flowerbed.get(i + 1).is_none_or(|c| *c == 0) && !p && n > 0 {
      (n-1, true)
    } else {
      (n, *c == 1)
    }
  }).0 == 0
}

345. Reverse Vowels of a String

Collect all vowels in a vec in one pass, reversed. In another pass, fold-construct a new string by replacing i-th vowel with the one from the rev-vowels list.

pub fn reverse_vowels(s: String) -> String {
  let vowels = s.chars().filter_map(|c| match c.to_ascii_lowercase() {
    'a' | 'e' | 'i' | 'o' | 'u' => Some(c),
    _ => None
  }).rev().collect::<Vec<_>>();

  s.chars().fold((0, String::new()), |(i, mut s), c| {
    let (c, i) = match c.to_ascii_lowercase() {
      'a' | 'e' | 'i' | 'o' | 'u' => (vowels[i], i + 1),
      _ => (c, i)
    };
    s.push(c);
    (i, s)
  }).1
}

151. Reverse Words in a String

Having itertools available, this is just split + filter nonempty + rev + join

pub fn reverse_words(s: String) -> String {
  s.split(' ').filter(|p| !p.is_empty()).rev().join(" ")
}

238. Product of Array Except Self

Calculate prefix & suffix products, multiply them at each place. Had a copy-paste bug, pushing a instead of p in rhs which took me 5mins to find.

pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
  let (lhs, _) = nums.iter()
    .fold((vec![], 1), |(mut v, p), a| { v.push(p); (v, p * a) });
  let (rhs, _) = nums.iter().rev()
    .fold((vec![], 1), |(mut v, p), a| { v.push(p); (v, p * a) });

  nums.iter().enumerate().map(|(i, _)| lhs[i] * rhs[nums.len() - 1 - i]).collect()
}

334. Increasing Triplet Subsequence

Same trick as above, but slower than others.

pub fn increasing_triplet(nums: Vec<i32>) -> bool {
  let (min_l, _) = nums.iter()
    .fold((vec![], i32::MAX), |(mut v, m), c| { v.push(m); (v, m.min(*c)) });
  let (max_r, _) = nums.iter().rev()
    .fold((vec![], i32::MIN), |(mut v, m), c| { v.push(m); (v, m.max(*c)) });

  nums.iter().enumerate()
    .find(|&(i, c)| min_l[i] < *c && *c < max_r[nums.len() - i - 1])
    .is_some()
}

After consulting other solutions, this is what’s faster.

pub fn increasing_triplet(nums: Vec<i32>) -> bool {
  nums.iter().try_fold((i32::MAX, i32::MAX), |(a, b), c| {
    if *c <= a {
      Some((*c, b))
    } else if *c <= b {
      Some((a, *c))
    } else if *c > b {
      None
    } else {
      Some((a, b))
    }
  }).is_none()
}

It works because: TODO

443. String Compression

A hard one in Rust, most things have to be done manually, lots of places to err.

pub fn compress(mut chars: &mut Vec<char>) -> i32 {
  let n = chars.len();
  let (mut r, mut w) = (0, 0);

  while r < n {
    let nc = chars[r..].iter().take_while(|x| **x == chars[r]).count();

    chars[w] = chars[r]; w += 1;

    if nc > 1 {
      let mut p10 = 1;
      while p10 <= nc { p10 *= 10; }
      p10 /= 10;

      while p10 > 0 {
        chars[w] = ((nc / p10 % 10) as u8 + b'0') as char;
        w += 1;
        p10 /= 10;
      }
    }

    r += nc;
  }

  w as i32
}

Two Pointers

283. Move Zeroes

Inplace modifications unnatural for Rust. First submission failed on > 0 check, there were negative numbers.

pub fn move_zeroes(nums: &mut Vec<i32>) {
  let (mut r, mut w, n) = (0, 0, nums.len());

  while r < n {
    if nums[r] != 0 { nums[w] = nums[r]; w += 1 }
    r += 1
  }

  while w < n { nums[w] = 0; w += 1 }
}

392. Is Subsequence

For each place in the target string t, calculate the position of the first occurence of c on the left for each possible c, then try to match chars from s from the end to t (start at the end of t, find first occurrence from the end of the last char of s, and so on until the first char of s is matched, or until there is no match left).

pub fn is_subsequence(s: String, t: String) -> bool {
  let pv = t.chars().enumerate().fold(vec![[None; 26]], |mut v, (i, c)| {
    let mut cv = *v.last().unwrap();
    cv[(c as u32 - b'a' as u32) as usize] = Some(i);
    v.push(cv);
    v
  });

  s.chars().rev().try_fold(t.len(), |i, c| pv[i][(c as u32 - b'a' as u32) as usize]).is_some()
}

11. Container With Most Water

This one I saw a few years ago, and then I couldn’t solve for a while, but now I remembered the outline of the solution so it was easy to do.

pub fn max_area(height: Vec<i32>) -> i32 {
  let (mut l, mut r) = (0, height.len() - 1);
  let mut max = (r - l) as i32 * height[l].min(height[r]);

  while l < r {
    if height[l] < height[r] { l += 1 } else { r -= 1 }
    max = max.max((r - l) as i32 * height[l].min(height[r]))
  }

  max
}

1679. Max Number of K-Sum Pairs

First, calculate counts of occurrences each number in the array. Then for each occurrence of n find the count of k-n, having special treatment for when n == k-n, and sum them.

pub fn max_operations(nums: Vec<i32>, k: i32) -> i32 {
  let cnts = nums.iter().fold(HashMap::<i32, i32>::new(), |mut m, a| {
    *m.entry(*a).or_default() += 1;
    m
  });

  cnts.iter().map(|(a, n)|
    if *a < k - *a {
      cnts.get(&(k - *a)).cloned().unwrap_or_default().min(*n)
    } else if *a == k - *a {
      n / 2
    } else {
      0
    }
  ).sum()
}

Sliding Window

643. Maximum Average Subarray I

Sliding window sum, but issues when k = 1 and with negative answers (max was set to 0 at first).

pub fn find_max_average(nums: Vec<i32>, k: i32) -> f64 {
  nums.iter().enumerate().fold((f64::MIN, 0), |(max, prev), (i, a)| {
    let curr = prev + a - if i >= k as usize { nums[i - k as usize] } else { 0 };
    if i + 1 < k as usize {
      (max, curr)
    } else {
      (max.max(curr as f64 / k as f64), curr)
    }
  }).0
}

1456. Maximum Number of Vowels in a Substring of Given Length

Same trick as above, just we need to iterate over byte string to have random access for i - kth char.

pub fn max_vowels(s: String, k: i32) -> i32 {
  let isvow = |c: u8| if matches!(c, b'a' | b'e' | b'i' | b'o' | b'u') { 1 } else { 0 };
  let bs = s.as_bytes();

  bs.iter().enumerate().fold((0, 0), |(max, prev), (i, c)| {
    let curr = prev + isvow(*c) - if i >= k as usize { isvow(bs[i - k as usize]) } else { 0 };
    (max.max(curr), curr)
  }).0
}

1004. Max Consecutive Ones III

pub fn longest_ones(nums: Vec<i32>, k: i32) -> i32 {
  nums.iter().enumerate().fold((0, 0, k), |(max, mut n, r), (i, a)| {
    if *a == 1 {
      (max.max(n + 1), n + 1, r)
    } else if r > 0 {
      (max.max(n + 1), n + 1, r - 1)
    } else {
      while nums[i - n as usize] == 1 { n -= 1 };
      (max, n, 0)
    }
  }).0
}

1493. Longest Subarray of 1′s After Deleting One Element

Basically the same trick as above, but I had some edge case issues

pub fn longest_subarray(nums: Vec<i32>) -> i32 {
  nums.iter().enumerate().fold((0, 0, 0), |(max, mut n, z), (i, a)| {
    if *a == 1 {
      (max.max(n + 1), n + 1, z)
    } else if z == 0 {
      (max.max(n + 1), n + 1, 1)
    } else {
      while nums[i - n as usize] == 1 { n -= 1 }
      (max, n, 1)
    }
  }).0 - 1
}

Prefix Sum

1732. Find the Highest Altitude

The simplest one yet, just a fold sum + max

pub fn largest_altitude(gain: Vec<i32>) -> i32 {
  gain.iter().fold((0, 0), |(max, prev), d| (max.max(prev + d), prev + d)).0
}

724. Find Pivot Index

Simple prefix and suffix sum, zipping them and finding where they match

pub fn pivot_index(nums: Vec<i32>) -> i32 {
  let lhs = nums.iter().fold(vec![0], |mut v, a| { v.push(v.last().unwrap() + a); v });
  let rhs = nums.iter().rev().fold(vec![0], |mut v, a| { v.push(v.last().unwrap() + a); v});

  lhs.iter().skip(1).zip(rhs.iter().skip(1).rev()).position(|(l, r)| l == r).map(|s| s as i32).unwrap_or(-1)
}

Hash Map/Set

2215. Find the Difference of Two Arrays

Build hash sets from each array, find their differences.

pub fn find_difference(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<Vec<i32>> {
  let s1 = nums1.into_iter().collect::<HashSet<_>>();
  let s2 = nums2.into_iter().collect::<HashSet<_>>();
  vec![
    s1.iter().filter(|a| !s2.contains(a)).copied().collect(),
    s2.iter().filter(|a| !s1.contains(a)).copied().collect()
  ]
}

1207. Unique Number of Occurrences

pub fn unique_occurrences(arr: Vec<i32>) -> bool {
  let ocs = arr.iter().fold(
    HashMap::<i32, usize>::new(),
    |mut m, a| { *m.entry(*a).or_default() += 1; m }
  );

  ocs.values().try_fold(
    vec![false; 1001],
    |mut v, o| if v[*o] { None } else { v[*o] = true; Some(v) }
  ).is_some()
}

1657. Determine if Two Strings are Close

Strings are close if they contain the same set of characters and if they have the same set of character occurrences.

pub fn close_strings(word1: String, word2: String) -> bool {
  if word1.len() != word2.len() { return false }

  let w1c = word1.as_bytes().iter().fold([0; 26], |mut m, c| { m[(c - b'a') as usize] += 1; m });
  let w2c = word2.as_bytes().iter().fold([0; 26], |mut m, c| { m[(c - b'a') as usize] += 1; m });

  let w1cc = w1c.iter().fold(HashMap::<_, usize>::new(), |mut m, c| { *m.entry(*c).or_default() += 1; m });
  let w2cc = w2c.iter().fold(HashMap::<_, usize>::new(), |mut m, c| { *m.entry(*c).or_default() += 1; m });

  std::iter::zip(w1c, w2c).all(|(c1, c2)| (c1 == 0) == (c2 == 0))
    && w1cc.iter().all(|(c, n)| w2cc.get(c).is_some_and(|nn| nn == n))
}

2352. Equal Row and Column Pairs

Rows in HashMap, columns to row + lookup + sum

pub fn equal_pairs(grid: Vec<Vec<i32>>) -> i32 {
  let rmap = grid.iter().fold(HashMap::<_, usize>::new(), |mut m, r| { *m.entry(r).or_default() += 1; m });

  (0..grid[0].len()).map(|j| {
    let col = grid.iter().map(|r| r[j]).collect::<Vec<_>>();
    rmap.get(&col).copied().unwrap_or_default() as i32
  }).sum()
}

Stack

2390. Removing Stars From a String

Iterate over chars, push them on a stack, pop if we encounter a *, join the remaining ones into a string at the end.

pub fn remove_stars(s: String) -> String {
  s.chars().fold(vec![], |mut v, c| {
    if c == '*' { v.pop(); } else { v.push(c); }
    v
  }).into_iter().join("")
}

735. Asteroid Collision

We need to replay the collisions with a stack:

pub fn asteroid_collision(asteroids: Vec<i32>) -> Vec<i32> {
  asteroids.iter().fold(vec![], |mut v, a| {
    if *a > 0 {
      v.push(*a);
    } else {
      let aa = a.abs();
      loop {
        match v.last().cloned() {
          None               => { v.push(*a); break }
          Some(b) if b < 0   => { v.push(*a); break },
          Some(b) if b > aa  => { break },
          Some(b) if b == aa => { v.pop(); break },
          Some(b)            => { v.pop(); }
        }
      }
    }
    v
  })
}

394. Decode String

pub fn decode_string(s: String) -> String {
  s.chars().fold((None, vec![(1, String::new())]), |(mut n, mut rs), c| match c {
    '0'..='9' => (n.map(|p| p * 10 + c.to_digit(10).unwrap()).or(c.to_digit(10)), rs),
    '['       => (None, { rs.push((n.unwrap() as usize, String::new())); rs }),
    ']'       => (None, { let (n, s) = rs.pop().unwrap(); rs.last_mut().unwrap().1.push_str(&s.repeat(n)); rs }),
    _         => (None, { rs.last_mut().unwrap().1.push(c); rs }),
  }).1.pop().unwrap().1
}

Queue

933. Number of Recent Calls

struct RecentCounter(VecDeque<i32>);

impl RecentCounter {
  fn new() -> Self { Self(VecDeque::new()) }
    
  fn ping(&mut self, t: i32) -> i32 {
    self.0.push_back(t);
    while self.0.front().is_some_and(|f| f + 3000 < t) { self.0.pop_front(); }
    self.0.len() as i32
  }
}

649. Dota2 Senate

pub fn predict_party_victory(senate: String) -> String {
  let (mut r, mut d) = senate.chars()
    .fold((0, 0), |(r, d), c| if c == 'R' { (r + 1, d) } else { (r, d + 1) });
  let mut ss = senate.chars().collect::<VecDeque<_>>();

  let (mut d_kills, mut r_kills) = (0, 0);

  while r > 0 && d > 0 {
    match ss.pop_front().unwrap() {
      'R' if r_kills > 0 => { r -= 1; r_kills -= 1; },
      'R' => { d_kills += 1; ss.push_back('R'); },
      'D' if d_kills > 0 => { d -= 1; d_kills -= 1; }
      'D' => { r_kills += 1; ss.push_back('D'); },
      _ => unreachable!(),
    }
  }

  if d > 0 { "Dire".into() } else { "Radiant".into() }
}

Linked List

2095. Delete the Middle Node of a Linked List

pub fn delete_middle(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
  let mut nodes = vec![];
  let mut cur = head;

  while let Some(n) = cur {
    nodes.push(n.val);
    cur = n.next;
  }

  nodes.iter().enumerate().rev()
    .fold(None, |n, (i, v)| if i == nodes.len() / 2 { n } else { Some(ListNode { val: *v, next: n }.into()) } )
}

pub fn delete_middle(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
  let len = {
    let mut i = 0;
    let mut cur = &head;

    while let Some(n) = cur {
      cur = &n.next;
      i += 1;
    }

    i
  };

  let mut nhead = None::<Box<ListNode>>;
  let mut curr = &mut nhead;
  let mut i = 0;

  while let Some(mut n) = head {
    head = n.next.take();

    if i != len / 2 { curr = &mut curr.insert(n).next; }

    i += 1;
  }

  nhead
}

328. Odd Even Linked List

pub fn odd_even_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
  let (mut odd_h, mut even_h) = (None, None);
  let (mut odd_c, mut even_c) = (&mut odd_h, &mut even_h);
  let mut is_odd = true;

  while let Some(mut n) = head {
    head = n.next.take();

    if is_odd {
      odd_c = &mut odd_c.insert(n).next;
    } else {
      even_c = &mut even_c.insert(n).next;
    }
    is_odd = !is_odd;
  }

  *odd_c = even_h;

  odd_h
}

2130. Maximum Twin Sum of a Linked List

pub fn pair_sum(mut head: Option<Box<ListNode>>) -> i32 {
  let mut v = vec![];
  while let Some(n) = head {
    v.push(n.val);
    head = n.next;
  }

  v.iter().zip(v.iter().rev()).fold(i32::MIN, |m, (a, b)| m.max(a + b))
}

Binary Tree — DFS

104. Maximum Depth of Binary Tree

pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
  let mut s = root.into_iter().map(|n| (n, 1)).collect::<Vec<_>>();
  let mut maxd = 0;

  while !s.is_empty() {
    let (n, d) = s.pop().unwrap();
    let n = n.borrow();

    maxd = maxd.max(d);
    if let Some(l) = n.left.clone() { s.push((l, d + 1)); }
    if let Some(r) = n.right.clone() { s.push((r, d + 1)); }
  }

  maxd
}

872. Leaf-Similar Trees

pub fn leaf_similar(
  root1: Option<Rc<RefCell<TreeNode>>>,
  root2: Option<Rc<RefCell<TreeNode>>>
) -> bool {
  let leaves = |r: Option<Rc<RefCell<TreeNode>>>| {
    let mut ls = vec![];
    let mut s = r.into_iter().collect::<Vec<_>>();

    while let Some(n) = s.pop() {
      let n = n.borrow();

      if let Some(l) = n.left.clone() { s.push(l); }
      if let Some(r) = n.right.clone() { s.push(r); }
      if n.left.is_none() && n.right.is_none() { ls.push(n.val); }
    }

    ls
  };

  leaves(root1) == leaves(root2)
}

1448. Count Good Nodes in Binary Tree

pub fn good_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
  let mut s = root.into_iter().map(|n| (n, i32::MIN)).collect::<Vec<_>>();
  let mut n_good = 0;

  while let Some((n, m)) = s.pop() {
    let n = n.borrow();

    if n.val >= m { n_good += 1 }

    if let Some(l) = n.left.clone() { s.push((l, m.max(n.val))); }
    if let Some(r) = n.right.clone() { s.push((r, m.max(n.val))); }
  }

  n_good
}

437. Path Sum III

pub fn path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> i32 {
  let mut n_ts = 0;
  let mut s = root.into_iter().map(|n| (n, Vec::<i64>::new())).collect::<Vec<_>>();

  while let Some((n, mut v)) = s.pop() {
    let n = n.borrow();

    let cs = v.last().cloned().unwrap_or_default() + n.val as i64;

    if cs == target_sum as i64 { n_ts += 1 }

    n_ts += v.iter().filter(|c| cs - *c == target_sum as i64).count();

    v.push(cs);

    if let Some(l) = n.left.clone() { s.push((l, v.clone())) }
    if let Some(r) = n.right.clone() { s.push((r, v)) }
  }

  n_ts as i32
}

1372. Longest ZigZag Path in a Binary Tree

pub fn longest_zig_zag(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
  let mut s = root.into_iter().map(|n| (n, 0, 0)).collect::<Vec<_>>();
  let mut maxz = 0;

  while let Some((n, lm, rm)) = s.pop() {
    let n = n.borrow();

    maxz = maxz.max(lm.max(rm));

    if let Some(l) = n.left.clone() { s.push((l, rm + 1, 0)); }
    if let Some(r) = n.right.clone() { s.push((r, 0, lm + 1)); }
  }

  maxz
}

236. Lowest Common Ancestor of a Binary Tree

pub fn lowest_common_ancestor(
  root: Option<Rc<RefCell<TreeNode>>>,
  p: Option<Rc<RefCell<TreeNode>>>,
  q: Option<Rc<RefCell<TreeNode>>>
) -> Option<Rc<RefCell<TreeNode>>> {
  let (p, q) = (p.unwrap(), q.unwrap());

  let mut ns = vec![];

  let (mut pi, mut qi) = (0, 0);

  let mut s = root.into_iter().map(|n| (n, -1, 0)).collect::<Vec<_>>();
  while let Some((n, ip, d)) = s.pop() {
    let i = ns.len() as i32;

    if n == p { pi = i }
    if n == q { qi = i }

    ns.push((ip, n.clone(), d));

    let n = n.borrow();

    if let Some(r) = n.right.clone() { s.push((r, i, d + 1)) }
    if let Some(l) = n.left.clone() { s.push((l, i, d + 1)) }
  }

  while pi != qi {
    if ns[pi as usize].2 > ns[qi as usize].2 {
      pi = ns[pi as usize].0;
    } else {
      qi = ns[qi as usize].0;
    }
  }

  Some(ns[pi as usize].1.clone())
}

Binary Tree — BFS

199. Binary Tree Right Side View

pub fn right_side_view(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
  let mut rs = vec![];
  let mut s = root.into_iter().map(|n| (n, 0)).collect::<Vec<_>>();

  while let Some((n, d)) = s.pop() {
    let n = n.borrow();

    if d >= rs.len() { rs.push(n.val) } else { rs[d] = n.val; }

    if let Some(r) = n.right.clone() { s.push((r, d + 1)) }
    if let Some(l) = n.left.clone() { s.push((l, d + 1)) }
  }

  rs
}

1161. Maximum Level Sum of a Binary Tree

pub fn max_level_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
  let mut ls = vec![];
  let mut s = root.into_iter().map(|n| (n, 0)).collect::<Vec<_>>();

  while let Some((n, d)) = s.pop() {
    let n = n.borrow();

    if d >= ls.len() { ls.push(n.val) } else { ls[d] += n.val }

    if let Some(l) = n.left.clone() { s.push((l, d + 1)) }
    if let Some(r) = n.right.clone() { s.push((r, d + 1)) }
  }

  ls.iter().enumerate().max_by_key(|(d, s)| (*s, -(*d as i32))).map(|(d, _)| d as i32 + 1).unwrap()
}

Binary Search Tree

700. Search in a Binary Search Tree

pub fn search_bst(root: Option<Rc<RefCell<TreeNode>>>, val: i32) -> Option<Rc<RefCell<TreeNode>>> {
  let mut s = root.into_iter().collect::<Vec<_>>();

  while let Some(n) = s.pop() {
    let v = n.borrow().val;

    if v == val { return Some(n) }
    else if let Some(l) = n.borrow().left.clone() && val < v { s.push(l) }
    else if let Some(r) = n.borrow().right.clone() { s.push(r) }
  }

  None
}

450. Delete Node in a BST

The hardest one to me so far, borrow checking + data layout made it unergonomic.

pub fn delete_node(root: Option<Rc<RefCell<TreeNode>>>, key: i32) -> Option<Rc<RefCell<TreeNode>>> {
  let root = root?;

  let v = root.borrow().val;

  if key < v {
    let l = Self::delete_node(root.borrow_mut().left.take(), key);
    root.borrow_mut().left = l;
    return Some(root)
  }
  if key > v {
    let r = Self::delete_node(root.borrow_mut().right.take(), key);
    root.borrow_mut().right = r;
    return Some(root)
  }

  match (root.borrow().left.clone(), root.borrow().right.clone()) {
    (None,    None)    => None,
    (None,    Some(r)) => Some(r),
    (Some(l), None)    => Some(l),
    (Some(l), Some(r)) => {
      let mut rl = r.clone();
      loop {
          let nl = rl.borrow().left.clone();
          if let Some(n) = nl { rl = n } else { break }
      }

      rl.borrow_mut().left = Some(l);
      Some(r)
    }
  }
}

Graphs — DFS

841. Keys and Rooms

pub fn can_visit_all_rooms(rooms: Vec<Vec<i32>>) -> bool {
  let mut visited = vec![false; rooms.len()];
  let mut s = vec![0];

  while let Some(i) = s.pop() {
    if !visited[i as usize] {
      visited[i as usize] = true;
      s.extend(&rooms[i as usize]);
    }
  }

  visited.iter().all(|v| *v)
}

547. Number of Provinces

pub fn find_circle_num(is_connected: Vec<Vec<i32>>) -> i32 {
  let n = is_connected.len();
  let mut ps = vec![-1; n];
  let mut pi = 0;

  for i in 0..n {
    if ps[i] == -1 {
      pi += 1;
      let mut s = vec![i];

      while let Some(i) = s.pop() {
        if ps[i] == -1 {
          ps[i] = pi;
          s.extend((0..n).filter(|j| is_connected[i][*j] == 1));
        }
      }
    }
  }

  pi
}

1466. Reorder Routes to Make All Paths Lead to the City Zero

pub fn min_reorder(n: i32, connections: Vec<Vec<i32>>) -> i32 {
  let g = connections.iter().fold(
    vec![vec![]; n as usize],
    |mut g, e| {
      g[e[0] as usize].push((e[1] as usize, true));
      g[e[1] as usize].push((e[0] as usize, false));
      g
    }
  );

  let mut tc = 0;
  let mut s = vec![(0, 0)];
  let mut vis = vec![false; n as usize];

  while let Some((n, c)) = s.pop() {
    if !vis[n] {
      vis[n] = true;
      tc += c;

      for (x, d) in &g[n] {
        s.push((*x, if *d { 1 } else { 0 }));
      }
    }
  }

  tc
}

399. Evaluate Division

pub fn calc_equation(
  equations: Vec<Vec<String>>, values: Vec<f64>, queries: Vec<Vec<String>>
) -> Vec<f64> {
  let terms = equations.iter().flat_map(|e| [e[0].as_str(), e[1].as_str()]).collect::<HashSet<_>>();
  let terms = terms.into_iter().enumerate().map(|(i, e)| (e, i)).collect::<HashMap<_, _>>();

  let n = terms.len();
  let g = equations.iter().zip(values).fold(vec![vec![]; n], |mut g, (e, v)| {
    let a = terms[e[0].as_str()];
    let b = terms[e[1].as_str()];

    g[a].push((b, v));
    g[b].push((a, 1.0 / v));
    g
  });

  queries.iter().map(|q| {
    let a = if let Some(a) = terms.get(q[0].as_str()) { *a } else { return -1.0 };
    let b = if let Some(b) = terms.get(q[1].as_str()) { *b } else { return -1.0 };

    let mut s = vec![(a, 1.0)];
    let mut vis = vec![false; n];
    while let Some((n, v)) = s.pop() {
      if n == b { return v }
      if !vis[n] {
        vis[n] = true;
        s.extend(g[n].iter().map(|(c, m)| (*c, m * v)));
      }
    }

    -1.0
  }).collect()
}

Graphs — BFS

1926. Nearest Exit from Entrance in Maze

pub fn nearest_exit(maze: Vec<Vec<char>>, entrance: Vec<i32>) -> i32 {
  let (ei, ej) = (entrance[0], entrance[1]);
  let (n, m) = (maze.len() as i32, maze[0].len() as i32);

  let mut s = [(ei, ej, 0)].into_iter().collect::<VecDeque<_>>();
  let mut vis = vec![vec![false; m as usize]; n as usize];

  while let Some((i, j, c)) = s.pop_front() {
    if (i == 0 || i == n-1 || j == 0 || j == m-1) && (i != ei || j != ej) { return c }

    if !vis[i as usize][j as usize] {
      vis[i as usize][j as usize] = true;
      for (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1)] {
        let (ni, nj) = (i + di, j + dj);
        if 0 <= ni && ni < n && 0 <= nj && nj < m && maze[ni as usize][nj as usize] == '.' {
          s.push_back((ni, nj, c+1));
        }
      }
    }
  }

  -1
}

994. Rotting Oranges

pub fn oranges_rotting(mut grid: Vec<Vec<i32>>) -> i32 {
  let (n, m) = (grid.len() as i32, grid[0].len() as i32);

  let mut s = VecDeque::new();
  let (mut nf, mut maxd) = (0, 0);
  for (i, r) in grid.iter().enumerate() {
    for (j, c) in r.iter().enumerate() {
      match c {
        1 => { nf += 1 },
        2 => { s.push_back((i as i32, j as i32, 0)) },
        _ => {}
      }
    }
  }

  while let Some((i, j, d)) = s.pop_front() {
    if grid[i as usize][j as usize] != 2 {
      grid[i as usize][j as usize] = 2;
      nf -= 1;
      maxd = maxd.max(d);
    }

    for (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1)] {
      let (ni, nj) = (i + di, j + dj);
      if 0 <= ni && ni < n && 0 <= nj && nj < m && grid[ni as usize][nj as usize] == 1 {
        s.push_back((ni, nj, d+1));
      }
    }
  }

  if nf == 0 { maxd } else { -1 }
}

Heap / Priority Queue

215. Kth Largest Element in an Array

pub fn find_kth_largest(nums: Vec<i32>, k: i32) -> i32 {
  let mut h = std::collections::BinaryHeap::new();

  for n in nums {
    h.push(std::cmp::Reverse(n));
    if h.len() > k as usize { h.pop(); }
  }

  h.pop().unwrap().0
}

2336. Smallest Number in Infinite Set

struct SmallestInfiniteSet {
  right: i32,
  left:  std::collections::BinaryHeap<std::cmp::Reverse<i32>>,
}

impl SmallestInfiniteSet {
  fn new() -> Self {
    Self { right: 1, left: Default::default() }
  }
  
  fn pop_smallest(&mut self) -> i32 {
    if self.left.is_empty() {
      self.right += 1;
      self.right - 1
    } else {
      self.left.pop().unwrap().0
    }
  }
  
  fn add_back(&mut self, num: i32) {
    if num < self.right && !self.left.iter().any(|v| v.0 == num) {
      self.left.push(std::cmp::Reverse(num))
    }
  }
}

2542. Maximum Subsequence Score

pub fn max_score(nums1: Vec<i32>, nums2: Vec<i32>, k: i32) -> i64 {
  let mut ord = (0..nums1.len()).collect::<Vec<_>>();
  ord.sort_by_key(|i| Reverse(nums2[*i]));

  let mut pq1 = ord.iter().take(k as usize).map(|i| Reverse(nums1[*i])).collect::<BinaryHeap<_>>();

  let sum = pq1.iter().map(|n| n.0 as i64).sum::<i64>();
  let min = nums2[ord[k as usize - 1]] as i64;
  let max = sum * min;

  ord.iter().skip(k as usize).fold((max, sum), |(max, sum), i| {
    let v = pq1.pop().unwrap().0 as i64;
    let min = nums2[*i] as i64;

    pq1.push(Reverse(nums1[*i]));

    let sum = sum - v + nums1[*i] as i64; 
    (max.max(sum * min), sum)
  }).0
}

2462. Total Cost to Hire K Workers

pub fn total_cost(costs: Vec<i32>, k: i32, candidates: i32) -> i64 {
  let rc = (candidates as usize).min(costs.len() - candidates as usize);
  let mut fi = candidates as usize;
  let mut ri = costs.len() - rc - 1;

  let mut pq = costs.iter().map(|c| (c, true)).enumerate().take(fi)
    .chain(costs.iter().map(|c| (c, false)).enumerate().rev().take(rc))
    .map(|(i, (c, f))| Reverse((*c, i, f)))
    .collect::<BinaryHeap<_>>();

  (0..k).fold(0, |tc, _| {
    let (c, i, f) = pq.pop().unwrap().0;

    if f && fi <= ri {
      pq.push(Reverse((costs[fi], fi, true)));
      fi += 1;
    } else if fi <= ri {
      pq.push(Reverse((costs[ri], ri, false)));
      ri -= 1;
    }
      
    tc + c as i64
  })
}

Binary Search

374. Guess Number Higher or Lower

unsafe fn guessNumber(n: i32) -> i32 {
  let (mut lo, mut hi) = (0, n as i64);
  while lo < hi {
    let mid = (lo + hi + 1) / 2;
    match guess(mid as i32) {
      -1 => { hi = mid - 1 },
      0 => { return mid as i32 }
      1 => { lo = mid }
      _ => unreachable!()
    }
  }
  0
}

2300. Successful Pairs of Spells and Potions

pub fn successful_pairs(spells: Vec<i32>, mut potions: Vec<i32>, success: i64) -> Vec<i32> {
  potions.sort();

  spells.into_iter()
    .map(|s| (potions.len() - potions.partition_point(|p| (*p as i64 * s as i64) < success)) as i32)
    .collect()
}

162. Find Peak Element

pub fn find_peak_element(nums: Vec<i32>) -> i32 {
  let (mut lo, mut hi) = (0, nums.len() - 1);

  while lo < hi {
    let mid = (lo + hi + 1) / 2;
    let (p, c, n) = (
      if mid > 0 { nums[mid - 1] } else { i32::MIN },
      nums[mid],
      if mid < nums.len() - 1 { nums[mid + 1] } else { i32::MIN }
    );
    if p < c && c > n { hi = mid; break }
    else if p < c && c < n { lo = mid + 1 }
    else if p > c { hi = mid - 1 }
  }
  
  hi as i32
}

875. Koko Eating Bananas

pub fn min_eating_speed(piles: Vec<i32>, h: i32) -> i32 {
  let (mut lo, mut hi) = (1, *piles.iter().max().unwrap());

  while lo < hi {
    let mid = (lo + hi) / 2;
    let kh = piles.iter().map(|b| (*b + mid - 1) / mid).sum::<i32>();
    if kh <= h { hi = mid } else { lo = mid + 1 }
  }

  hi
}

Backtracking

17. Letter Combinations of a Phone Number

pub fn letter_combinations(digits: String) -> Vec<String> {
  let letters = |c: char| -> &'static [char] {
    match c {
      '2' => &['a', 'b', 'c'],
      '3' => &['d', 'e', 'f'],
      '4' => &['g', 'h', 'i'],
      '5' => &['j', 'k', 'l'],
      '6' => &['m', 'n', 'o'],
      '7' => &['p', 'q', 'r', 's'],
      '8' => &['t', 'u', 'v'],
      '9' => &['w', 'x', 'y', 'z'],
      _   => unreachable!(),
    }
  };

  digits.chars().fold(vec![String::new()], |v, c| {
    letters(c).iter().fold(vec![], |mut vv, c| {
      vv.extend(v.iter().map(|s| format!("{s}{c}")));
      vv
    })
  })
}

216. Combination Sum III

pub fn combination_sum3(k: i32, n: i32) -> Vec<Vec<i32>> {
  (0..k).fold(
    vec![(vec![], 0, 0)],
    |v, c| v.into_iter().flat_map(
      |(ds, m, s)| (m+1..=9).filter_map(|d| if s + d + 9*(k - c) < n {
        None
      } else {
        let mut ds = ds.clone();
        ds.push(d);
        if c == k - 1 && s + d != n { None } else { Some((ds, d, s + d)) }
      }).collect::<Vec<_>>()
    ).collect()
  ).into_iter().map(|(ds, _, _)| ds).collect()
}

DP — 1D

1137. N-th Tribonacci Number

pub fn tribonacci(n: i32) -> i32 {
  let mut tri = vec![0; (n+1) as usize];
  for i in (1..=(n as usize)) {
    tri[i] = if i < 3 { 1 } else { tri[i-1] + tri[i-2] + tri[i-3] }
  }
  tri[n as usize]
}

746. Min Cost Climbing Stairs

pub fn min_cost_climbing_stairs(cost: Vec<i32>) -> i32 {
  let n = cost.len();
  (0..=n).fold(vec![0; n+1], |mut cs, i| {
    cs[i] = if i < n { cost[i] } else { 0 } + i32::min(
      if i > 0 { cs[i-1] } else { 0 },
      if i > 1 { cs[i-2] } else { 0 }
    );
    cs
  })[n]
}

198. House Robber

pub fn rob(nums: Vec<i32>) -> i32 {
  let n = nums.len();
  let (_, _, bly, bln) = (1..n).fold((0, 0, nums[0], 0), |(bppy, bppn, bpy, bpn), i| (
    bpy,
    bpn,
    nums[i] + i32::max(bppy, bppn),
    i32::max(bpy, bpn)
  ));
  i32::max(bly, bln)
}

790. Domino and Tromino Tiling

pub fn num_tilings(n: i32) -> i32 {
  match n {
    1 => 1,
    2 => 2,
    _ => (3..=n).fold((1i64, 1i64, 2i64), |(a, b, c), _| (b, c, (2*c + a) % 1_000_000_007)).2 as i32
  }
}

DP — multidimensional

62. Unique Paths

pub fn unique_paths(m: i32, n: i32) -> i32 {
  let (n, m) = (n as usize, m as usize);
  let mut ways = vec![vec![0; m]; n];

  for i in 0..n {
    for j in 0..m {
      ways[i][j] = if i == 0 && j == 0 { 1 }
        else if i == 0 { ways[i][j-1] }
        else if j == 0 { ways[i-1][j] }
        else { ways[i-1][j] + ways[i][j-1] };
    }
  }

  ways[n-1][m-1]
}

1143. Longest Common Subsequence

pub fn longest_common_subsequence(text1: String, text2: String) -> i32 {
  let (n, m) = (text1.len(), text2.len());
  let mut best = vec![vec![0; m+1]; n+1];

  for i in 0..=n {
    for j in 0..=m {
      best[i][j] = if i == 0 || j == 0 { 0 }
        else if text1.as_bytes()[i-1] == text2.as_bytes()[j-1] { best[i-1][j-1] + 1 }
        else { usize::max(best[i-1][j], best[i][j-1]) };
    }
  }

  best[n][m] as i32
}

714. Best Time to Buy and Sell Stock with Transaction Fee

pub fn max_profit(prices: Vec<i32>, fee: i32) -> i32 {
  let n = prices.len();

  (1..n).fold((0, -prices[0]), |(ba, bb), i| (
    ba.max(bb + prices[i] - fee),
    bb.max(ba - prices[i])
  )).0
}

72. Edit Distance

pub fn min_distance(word1: String, word2: String) -> i32 {
  let (n, m) = (word1.len(), word2.len());
  let mut dist = vec![vec![0; m+1]; n+1];
  for i in 0..=n {
    for j in 0..=m {
      dist[i][j] = if j == 0 { i }
        else if i == 0 { j }
        else { usize::min(
          usize::min(
            dist[i-1][j],
            dist[i][j-1]
          ) + 1,
          dist[i-1][j-1] + if word1.as_bytes()[i-1] == word2.as_bytes()[j-1] { 0 } else { 1 }
        )};
    }
  }
  dist[n][m] as i32
}

Bit Manipulation

338. Counting Bits

pub fn count_bits(n: i32) -> Vec<i32> {
  (0..=(n as usize)).fold(vec![0; n as usize + 1], |mut v, i| {
    v[i] = v[i/2] + i as i32 % 2;
    v
  })
}

136. Single Number

pub fn single_number(nums: Vec<i32>) -> i32 {
  nums.into_iter().fold(0, |a, b| a ^ b)
}

1318. Minimum Flips to Make a OR b Equal to c

pub fn min_flips(mut a: i32, mut b: i32, mut c: i32) -> i32 {
  let mut n = 0;
  while a > 0 || b > 0 || c > 0 {
    if c & 1 == 1 {
      n += if (a | b) & 1 == 0 { 1 } else { 0 };
    } else {
      n += (a & 1) + (b & 1);
    }
    a /= 2;
    b /= 2;
    c /= 2;
  }
  n
}

Trie

208. Implement Trie (Prefix Tree)

This was ridiculous, how simple the implementation is with fold/try_fold and entry/get.

#[derive(Default)]
struct Node {
  filled: bool,
  children: BTreeMap<char, Node>,
}

struct Trie { root: Node }

impl Trie {
  fn new() -> Self {
    Self { root: Node::default() }
  }
  
  fn insert(&mut self, word: String) {
    word.chars()
      .fold(&mut self.root, |mut n, c| n.children.entry(c).or_insert(Node::default()))
      .filled = true;
  }
  
  fn search(&self, word: String) -> bool {
    word.chars()
      .try_fold(&self.root, |n, c| n.children.get(&c))
      .is_some_and(|n| n.filled)
  }
  
  fn starts_with(&self, prefix: String) -> bool {
    prefix.chars()
      .try_fold(&self.root, |n, c| n.children.get(&c))
      .is_some()
  }
}

1268. Search Suggestions System

pub fn suggested_products(mut products: Vec<String>, search_word: String) -> Vec<Vec<String>> {
  products.sort();

  (1..=search_word.len()).map(|i| {
    let pfx = &search_word[..i];
    let pos = products.partition_point(|w| w.as_str() < pfx);
    products[pos..].iter().take_while(|w| w.starts_with(pfx)).take(3).cloned().collect()
  }).collect()
}

Intervals

435. Non-overlapping Intervals

pub fn erase_overlap_intervals(mut intervals: Vec<Vec<i32>>) -> i32 {
  intervals.sort_by_key(|i| i[1]);
  intervals.into_iter().fold(
    (0, i32::MIN),
    |(n, l), i| if i[0] < l { (n+1, l) } else { (n, i[1]) }
  ).0
}

452. Minimum Number of Arrows to Burst Balloons

pub fn find_min_arrow_shots(mut points: Vec<Vec<i32>>) -> i32 {
  points.sort_by_key(|p| p[1]);
  points.iter()
    .fold((0, i64::MIN), |(a, l), p| if p[0] as i64 <= l { (a, l) } else { (a+1, p[1] as i64) })
    .0
}

Monotonic Stack

739. Daily Temperatures

pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
  let mut next = vec![0; temperatures.len()];
  
  temperatures.iter().enumerate().fold(vec![], |mut v, (i, t)| {
      while let Some(j) = v.pop_if(|j| temperatures[*j] < *t) {
          next[j] = (i - j) as i32;
      }
      v.push(i);
      v
  });

  next
}

901. Online Stock Span

struct StockSpanner {
  prev: Vec<(i32, i32)>
}

impl StockSpanner {
  fn new() -> Self {
    Self { prev: Vec::new() }
  }
  
  fn next(&mut self, price: i32) -> i32 {
    let mut v = 1;
    while let Some((_, n)) = self.prev.pop_if(|(a, _)| *a <= price) { v += n; }
    self.prev.push((price, v));
    v
  }
}

Conclusion

Rust is great for arrays. The list/tree tasks have unergonomic signatures in Rust.

Extras

1383. Maximum Performance of a Team

pub fn max_performance(n: i32, speed: Vec<i32>, efficiency: Vec<i32>, k: i32) -> i32 {
  let mut ord = (0..n as usize).collect::<Vec<_>>();
  ord.sort_by_key(|i| Reverse(efficiency[*i]));

  let r = ord.into_iter().fold((BinaryHeap::new(), 0, 0), |(mut top_s, sum, max), i| {
      top_s.push(Reverse(speed[i]));

      let prev = if top_s.len() > k as usize { top_s.pop().unwrap().0 as u64 } else { 0 };

      let sum = sum - prev + speed[i] as u64;
      let min = efficiency[i] as u64;

      (top_s, sum, max.max(sum * min))
  }).2;

  (r % 1_000_000_007) as i32
}