Find max values of all subarrays of specific length

Question

This is one of the coding questions that I subscribe to and I wanted to solve it in Rust. I would really appreciate your feedback for improving this code and writing idiomatic Rust.

Given an array of integers and a number k, where 1 <= k <= length of the array, compute the maximum values of each subarray of length k.

For example, given array = [10, 5, 2, 7, 8, 7] and k = 3, we should get: [10, 7, 8, 8], since:

10 = max(10, 5, 2)
7 = max(5, 2, 7)
8 = max(2, 7, 8)
8 = max(7, 8, 7)

Do this in \$O(n)\$ time and \$O(k)\$ space. You can modify the input array in-place and you do not need to store the results. You can simply print them out as you compute them.

This is my first attempt: https://gist.github.com/ginghamtaus/236e8a1d75237a47769ca74b23ac45ac

This is my second attempt: https://gist.github.com/ginghamtaus/6e0003e43e020130c8fd9346c9019522

use std::collections::VecDeque;
fn main() {
 let a = [10, 5, 2, 7, 8, 7];
 let k = 3;
 let mut deque: VecDeque<usize> = VecDeque::new();
 for i in 0..a.len() {
 match deque.front() {
 None => deque.push_back(i),
 Some(_) => {
 let mut done = false;
 while !done {
 match deque.back() {
 Some(&x) => {
 if a[i] > a[x] {
 deque.pop_back();
 }
 else {
 done = true;
 }
 },
 _ => { done = true; }
 }
 }
 deque.push_back(i); 
 }
 }
 if i + 1 >= k {
 match deque.front() {
 Some(&x) => {
 println!("max({:?}) = {}", &a[i+1-k..i+1], a[x]);
 if x <= (i + 1 - k) {
 deque.pop_front();
 }
 },
 _ => ()
 };
 }
 }
}

• Masaki Hara: It seems to take Ω((n-k)k) time for decreasing sequences.
• GinghamTaus: Yes you are right!
• Boiethios: I'm pretty sure that for a small slice, the straight-forward solution s.windows(k).filter_map(|s| s.iter().max()) is faster

Answer 1

1. Run rustfmt. It will automatically tell you such things as:

   • else blocks in Rust belong on the same line as the closing } and opening {
   • spaces belong around binary arithmetic operators: &a[i + 1 - k..i + 1].

2. Run clippy. It will automatically tell you such things as:

   • You are using match for a single pattern. Use if let instead.

3. Don't specify types of variables if type inference can handle it.

4. If you don't care about the value of an Option, use is_some / is_none instead of matching on it.

5. Both branches end with push_back, that shared logic should be pulled out of the conditional.

6. If all you care about is if the front of the queue is present, all you really care about is if it is empty.

7. You can continue to simplify by transofrming that into a while let and using break.

8. I'd create a function (or an Iterator implementation) to separate the algorithm and the driver.

use std::collections::VecDeque;
fn max_of_subarrays<F>(a: &[i32], k: usize, f: F)
where
 F: Fn(&[i32], i32),
{
 let mut deque = VecDeque::new();
 for i in 0..a.len() {
 while let Some(&x) = deque.back() {
 if a[i] > a[x] {
 deque.pop_back();
 } else {
 break;
 }
 }
 deque.push_back(i);
 if i + 1 >= k {
 if let Some(&x) = deque.front() {
 f(&a[i + 1 - k..i + 1], a[x]);
 if x <= (i + 1 - k) {
 deque.pop_front();
 }
 }
 }
 }
}
fn main() {
 let a = [10, 5, 2, 7, 8, 7];
 let k = 3;
 max_of_subarrays(&a, k, |sub, max| {
 println!("max({:?}) = {}", sub, max);
 });
}

---

Truthfully, I wouldn't do any of that unless I had a really good reason. Instead, I'd just use the less efficient algorithm but very concise implementation:

fn main() {
 let a = [10, 5, 2, 7, 8, 7];
 let k = 3;
 for (sub, max) in a.windows(k).flat_map(|sub| sub.iter().max().map(|max| (sub, max))) {
 println!("max({:?}) = {}", sub, max);
 }
}

I didn't take the time to benchmark this, but there's no allocation required here, so I'd expect it to be faster than the better algorithm in certain cases.