202610051630 Leetcode Rotate Image

#project

Problem

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Constraints:

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

Solution

For a given $(i,j)$ pair, where $i$ is the row and $j$ is the column, we want to transform the value at that coordinate. Let's write down a 3x3 case and see if we can't glean the general formula from old position to new position.

Which brings us to the general formula $f(i,j)=(j,max(j)-i)$. If we imagine we could allocate a new vector for this problem, the solution would look something like this.

pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
    let max_j = matrix.len() - 1;
    let mut new = matrix.clone();
    for i in 0..matrix.len() {
        for j in 0..matrix.len() {
            new[j][max_j - i] = matrix[i][j];
        }
    }
    new
}

But since we can't allocate, we need to do something a little smarter. At first, I wondered if we could just swap the current $(i,j)$ with its destination, but this is obviously incorrect.

So after looking at it for a little bit, I visually realized that if we swap rows for columns and then reverse each row, we end up with the right thing. The only remaining gotcha is that we have to not run over the indices for positions we already swapped. We only need to do the "upper half triangle" of the matrix, which we can do by using the range for j in i..matrix.len().

[1] [2] [3] -> 1 swaps with 1  2 swaps with 4  3 swaps with 7
 4  [5] [6] -> don't re-swap   5 swaps with 5  6 swaps with 8
 7   8  [9] -> don't re-swap   don't re-swap   9 swaps with 9

But this shows us a further optimization we can make by restricting the range to for j in (i+1)..matrix.len()

 1  [2] [3] -> skip diagonal  2 swaps with 4  3 swaps with 7
 4   5  [6] -> don't re-swap  skip diagonal   6 swaps with 8
 7   8   9  -> don't re-swap  don't re-swap   skip diagonal

This gives us a working solution.

pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
    for i in 0..matrix.len() {
        for j in (i + 1)..matrix.len() {
            let tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }

    for row in matrix {
        row.reverse();
    }
}

I'm aware of the various "swap two variables without a temporary variable" tricks that are available to us here, but... no thanks.

Unfortunately, clippy is letting us down on this solution. It triggers the clippy::needless_range_loop lint even though we do in fact need the j index specifically to do the swap. There's a way around this by splitting the rows and zipping the pairs.

pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
    for j in 1..matrix.len() {
        let (above, below) = matrix.split_at_mut(j);
        for (row, cell) in above.iter_mut().zip(&mut below[0]) {
            std::mem::swap(&mut row[j], cell);
        }
    }

    for row in matrix {
        row.reverse();
    }
}

In my opinion, this reads terribly compared to the previous one which clearly shows the iteration and swap.

So we could include a #[allow(clippy::needless_range_loop)] right above the for j loop. But that feels like a failure to me for some reason even though it's clearly a false positive.

Our last option is to do the looping the same, but then get the two rows in a get_disjoint_mut which also then allows us to do a true std::mem::swap instead of the temp variable dance.

pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
    for i in 0..matrix.len() {
        for j in (i + 1)..matrix.len() {
            let [row_i, row_j] = matrix.get_disjoint_mut([i, j]).expect("i < j < len");
            std::mem::swap(&mut row_i[j], &mut row_j[i]);
        }
    }

    for row in matrix {
        row.reverse();
    }
}

I'll let you be the judge of which of these versions you'd prefer to read.