LeetCode 75 study plan - impressions
I’ve recently decided to brush up my skills on LeetCode-style interview tasks which I haven’t solved for a long while, so I’ve decided to start on the LeetCode 75 study plan.
As I’ve also recently set out to make a blog, what better than to connect the two and write problem solving impressions in a series of blog posts, one for each day?
Day 1
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
}5min
1071. Greatest Common Divisor of Strings
Try all possible lengths 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()
}10min
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()
}5min
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
}10min
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
}5min
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(" ")
}1min
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()
}15min
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()
}10min, first submission passed
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
}45min
Day 2
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 }
}5min
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()
}10min
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
}10min
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()
}10min
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
}10min
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
}10min
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
}10min
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
}1min
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)
}5min
Day 3
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()
]
}2min
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))
}10min
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()
}5min
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("")
}3min
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
})
}15min
394. Decode String