Mutable and immutable borrow problems with Vec>

Question

I'm solving a problem from Leetcode and encountered the fact that Rust won't let me execute it efficiently. What am I doing wrong? I know about the book article about references and borrowing and would like to know how to solve this problem despite the peculiarities of the language.

I am trying to create one reference for a vec that should change and another for a vec that will not change. Rust won't let me do that. The program works, but only when using .clone(), which will be very slow and not necessary (last_row does not change anywhere, only the values are derived from there).

Here is the working code:

use std::cmp;

fn minimum_total(mut triangle: Vec<Vec<i32>>) -> i32 {
    for i in (0..triangle.len()-1).rev() { // from penultimate (last - 1) to first
        let last_row = & triangle[i+1].clone();
        let current_row = &mut triangle[i];
        for j in 0..current_row.len() {
            current_row[j] = cmp::min(last_row[j], last_row[j+1]) + current_row[j];
        }
    }

    triangle[0][0]
}

fn main() {
    println!("{}", minimum_total(vec![vec![2],vec![3,4],vec![6,5,7],vec![4,1,8,3]]));
}

As you can see, I used .clone() to fix the borrow checker errors that show up when you try to write a program using references:

use std::cmp;

fn minimum_total(mut triangle: Vec<Vec<i32>>) -> i32 {
    for i in (0..triangle.len()-1).rev() { // from penultimate (last - 1) to first
        let current_row = &mut triangle[i];
        let last_row = &triangle[i+1];
        for j in 0..current_row.len() {
            current_row[j] = cmp::min(last_row[j], last_row[j+1]) + current_row[j];
        }
    }

    triangle[0][0]
}

fn main() {
    println!("{}", minimum_total(vec![vec![2],vec![3,4],vec![6,5,7],vec![4,1,8,3]]));
}

Terminal:

error[E0502]: cannot borrow `triangle` as immutable because it is also borrowed as mutable
 --> src\main.rs:6:25
  |
5 |         let current_row = &mut triangle[i];
  |                                -------- mutable borrow occurs here
6 |         let last_row = &triangle[i+1];
  |                         ^^^^^^^^ immutable borrow occurs here
7 |         for j in 0..current_row.len() {
  |                     ----------------- mutable borrow later used here

For more information about this error, try `rustc --explain E0502`.

However, when trying to write a program poorly everything works without any problems:

use std::cmp;

fn minimum_total(mut triangle: Vec<Vec<i32>>) -> i32 {
    for i in (0..triangle.len()-1).rev() { // from penultimate (last - 1) to first
        for j in 0..triangle[i].len() {
            triangle[i][j] = cmp::min(triangle[i+1][j], triangle[i+1][j+1]) + triangle[i][j];
        }
    }

    triangle[0][0]
}

fn main() {
    println!("{}", minimum_total(vec![vec![2],vec![3,4],vec![6,5,7],vec![4,1,8,3]]));
}

Answer 1

You can accomplish this via the split_at_mut() method, which comes from the primitive slice type (which Vec auto-derefs to). This method allows you to safely take a mutable slice and split it into two mutable slices at a given index, since it's guaranteed that the two slices won't overlap. (Note this is zero-copy, as slices are just fat pointers borrowing an existing contiguous sequence.)

The two slices then are independent for the purposes of borrow checking, so you can borrow mutably from both slices at the same time (or, in your case, mutably from one and immutably from the other).

use std::cmp;

fn minimum_total(mut triangle: Vec<Vec<i32>>) -> i32 {
    for i in (0..triangle.len()-1).rev() { // from penultimate (last - 1) to first
        let (left, right) = triangle.split_at_mut(i + 1);
        
        let current_row = left.last_mut().unwrap();
        let last_row = right.first().unwrap();
        
        for j in 0..current_row.len() {
            current_row[j] = cmp::min(last_row[j], last_row[j+1]) + current_row[j];
        }
    }

    triangle[0][0]
}

fn main() {
    println!("{}", minimum_total(vec![vec![2],vec![3,4],vec![6,5,7],vec![4,1,8,3]]));
}

Answer 2

Yes, that's the thing with Rust -- you have to code in a way that the compiler can tell it is safe. Sometimes that requires a bit of thought, but often in the end you have code that is cleaner than you would have written otherwise.

Imagine having a function that could walk through items two at a time, calling a function you specify on them, with the first being immutable, and the second being mutable. Call it pairs_mut, and calling it with function f on a,b,c,d it would result in calls to f(&a, &mut b), f(&b, &mut c), and f(&c, &mut d). A non-generic version is not that hard to write. I am hesitant to put the code here because you are trying to learn from the exercise.

NOTE: I suspect that such a facility (or perhaps something more general) exists somewhere in the Rust ecosystem, but I have looked in Iterator and the itertools crate and didn't find anything. If you know of an existing facility like this, please share a link in a comment. Otherwise perhaps I should try to get something added to itertools.

Now given pairs_mut, I hope you can see that minimum_total could run it on triangle.rev() and do that bit of dynamic programming to come up with the minimum sum. Let me know if you want me to put some actual code here, but I encourage you to try it yourself first.