Why doesn't this pass the borrow checker?

user_9307942 0
Viewed 71

I'm trying to solve the Spiral Order question on leetcode by splitting off the top and bottom rows one by one, and I ran into a problem with the borrow checker that I can't make sense of. This is the minimal example that creates the compile error:

pub fn f(mut matrix: &mut [Vec<i32>]) {
    while let Some((_, remainder)) = matrix.split_first_mut() {
        matrix = remainder;
        if let Some((_, remainder)) = matrix.split_first_mut() {
            matrix = remainder;
        }
    }
}

And this is my full code, for context of what I'm trying to accomplish:

impl Solution {
    pub fn spiral_order(mut matrix: Vec<Vec<i32>>) -> Vec<i32> {
        let mut matrix = &mut matrix[..];
        if matrix.is_empty() {
            return Vec::new();
        }
        let mut ans = Vec::with_capacity(matrix.len() * matrix[0].len());
        while let Some((head, tail)) = matrix.split_first_mut() {
            ans.append(head);
            matrix = tail;
            for row in matrix.iter_mut() {
                ans.push(row.pop().unwrap());
            }
            if let Some((head, tail)) = matrix.split_last_mut() {
                matrix = tail;
                ans.extend(head.into_iter().rev().map(|&mut x| x));
            }
        }
        ans
    }
}

It seems to think that the inner borrow conflicts with the subsequent outer borrow in the next iteration of the loop, but I think it should be okay because I move the remainder back into matrix, so there is a valid &mut [Vec<i32>] in there before the iteration ends. Why is this failing to compile, and how should it be fixed?

borrowing borrow-checker rust multidimensional-array reference
1 Answers

I can't explain why your original version doesn't compile but I don't think split_first_mut and split_last_mut are the tools for the job. I was to simplify the implementation and make it compile by switching to remove and pop instead:

fn spiral_order(mut matrix: Vec<Vec<i32>>) -> Vec<i32> {
    if matrix.is_empty() {
        return Vec::new();
    }
    let mut ans = Vec::with_capacity(matrix.len() * matrix[0].len());
    while !matrix.is_empty() {
        let mut head = matrix.remove(0);
        ans.append(&mut head);
        for row in matrix.iter_mut() {
            ans.push(row.pop().unwrap());
        }
        if let Some(head) = matrix.pop() {
            ans.extend(head.into_iter().rev());
        }
    }
    ans
}

playground

More optimal solution, without any matrix mutations or copies:

fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
    if matrix.len() == 0 || matrix[0].len() == 0 {
        return Vec::new();
    }

    let mut row = 0;
    let mut col = 0;
    let mut up = 0;
    let mut down = matrix.len() as i32 - 1;
    let mut left = 0;
    let mut right = matrix[0].len() as i32 - 1;
    let mut dir = (0, 1);
    let mut ans = Vec::with_capacity(matrix.len() * matrix[0].len());

    for _ in 0..(matrix.len() * matrix[0].len()) {
        ans.push(matrix[row as usize][col as usize]);

        match dir {
            (0, 1) if col == right => {
                dir = (1, 0);
                up += 1;
            }
            (1, 0) if row == down => {
                dir = (0, -1);
                right -= 1;
            }
            (0, -1) if col == left => {
                dir = (-1, 0);
                down -= 1;
            }
            (-1, 0) if row == up => {
                dir = (0, 1);
                left += 1;
            }
            _ => (),
        }

        row += dir.0;
        col += dir.1;
    }

    ans
}

playground

user_27669080
Related