Problem of The Day: Rotate Image

4 min read 967 words

Problem Statement

leetcode problem link

Solution [Accepted]

class Solution:
    def reverseDiagonal(self, curr, matrix):
        l, r = 0, len(curr) - 1
        while l < r:
            lr, lc = curr[l]
            rr, rc = curr[r]
            matrix[lr][lc], matrix[rr][rc] = matrix[rr][rc], matrix[lr][lc]
            l += 1
            r -= 1

    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        ROWS = len(matrix)
        COLS = len(matrix[0])
        for row in range(ROWS):
            l, r = 0, COLS - 1
            while l < r:
                matrix[row][l], matrix[row][r] = matrix[row][r], matrix[row][l]
                l += 1
                r -= 1

        for row in range(ROWS):
            curr = []
            r = row
            c = COLS - 1
            while r >= 0 and c >= 0:
                curr.append([r, c])
                r -= 1
                c -= 1
            self.reverseDiagonal(curr, matrix)

        for row in range(ROWS - 1, 0, -1):
            curr = []
            r = row
            c = 0
            while r < ROWS and c < COLS:
                curr.append([r, c])
                r += 1
                c += 1
            self.reverseDiagonal(curr, matrix)

Editorial

Approach 2: Reverse on the Diagonal and then Reverse Left to Right

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        self.transpose(matrix)
        self.reflect(matrix)

    def transpose(self, matrix):
        n = len(matrix)
        for i in range(n):
            for j in range(i + 1, n):
                matrix[j][i], matrix[i][j] = matrix[i][j], matrix[j][i]

    def reflect(self, matrix):
        n = len(matrix)
        for i in range(n):
            for j in range(n // 2):
                matrix[i][j], matrix[i][-j - 1] = (
                    matrix[i][-j - 1],
                    matrix[i][j],
                )

public class Solution {
    public void Rotate(int[][] matrix) {
        int n = matrix.Length;
        Transpose(matrix, n);
        Reflect(matrix, n);
    }

    private void Transpose(int[][] matrix, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[j][i];
                matrix[j][i] = matrix[i][j];
                matrix[i][j] = temp;
            }
        }
    }

    private void Reflect(int[][] matrix, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - j - 1];
                matrix[i][n - j - 1] = temp;
            }
        }
    }
}