DEV Community

loading...

LeetCode - Rotate Image

Alkesh Ghorpade
Ruby on Rails and Golang consultant
Originally published at alkeshghorpade.me ・4 min read

Container

Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/rotate-image

Example 1:

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

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]]
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: matrix = [[1]]
Output: [[1]]
Enter fullscreen mode Exit fullscreen mode

Example 4:

Input: matrix = [[1, 2], [3, 4]]
Output: [[3, 1], [4, 2]]
Enter fullscreen mode Exit fullscreen mode

Constraints:

- matrix.length == n
- matrix[i].length == n
- 1 <= n <= 20
- -1000 <= matrix[i][j] <= 1000
Enter fullscreen mode Exit fullscreen mode

Explanation

Rotate Groups of Four Cells

The first solution we can think of is to rotate
the four corners of the matrix.
We repeat this of the subsequent cells too.

Container

Let's check the algorithm.

- initialize m = matrix.size, tmp

- loop for i = 0; i < m / 2; i++
    - loop for j = i; j < m - 1 - i; j++
      - tmp = matrix[i][j]
      - matrix[i][j] = matrix[m - 1 - j][i]
      - matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j]
      - matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i]
      - matrix[j][m - 1 - i] = tmp
Enter fullscreen mode Exit fullscreen mode

The time complexity of the program is O(M) as each cell is getting read once and written once.
Space complexity is O(1) because we do not use any other additional data structures.

C++ solution
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int m = matrix.size(), tmp;
        int j = 0;

        for(int i = 0; i < m/2; i++){
            for(int j = i; j < m - 1 - i; j++){
                tmp = matrix[i][j];
                matrix[i][j] = matrix[m - 1 - j][i];
                matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j];
                matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i];
                matrix[j][m - 1 - i] = tmp;
            }
        }
    }
};
Enter fullscreen mode Exit fullscreen mode
Golang solution
func rotate(matrix [][]int)  {
    m := len(matrix)
    tmp := 0

    for i := 0; i < m / 2; i++ {
        for j := i; j < m - 1 - i; j++ {
            tmp = matrix[i][j];
            matrix[i][j] = matrix[m - 1 - j][i];
            matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j];
            matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i];
            matrix[j][m - 1 - i] = tmp;
        }
    }
}
Enter fullscreen mode Exit fullscreen mode
Javascript solution
var rotate = function(matrix) {
    let m = matrix.length;
    let tmp = 0;
    let i, j;

    for(i = 0; i < m/2; i++){
        for(j = i; j < m - 1 - i; j++){
            tmp = matrix[i][j];
            matrix[i][j] = matrix[m - 1 - j][i];
            matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j];
            matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i];
            matrix[j][m - 1 - i] = tmp;
        }
    }
};
Enter fullscreen mode Exit fullscreen mode

Let's dry-run our algorithm to see how the solution works.

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

Step 1: m = matrix.length
        m = 3

Step 2: tmp = 0

Step 3: loop i = 0; i < 3/2
        0 < 3/2
        0 < 1
        true

        j = i; j < 3 - 1 - 0
        0 < 2
        true

        tmp = matrix[i][j]
        tmp = 1

        matrix[i][j] = matrix[m - 1 - j][i]
        matrix[0][0] = matrix[3 - 1 - 0][0]
        matrix[0][0] = matrix[2][0]
        matrix[0][0] = 7

        matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j]
        matrix[3 - 1 - 0][0] = matrix[3 - 1 - 0][3 - 1 - 0]
        matrix[2][0] = matrix[2][2]
        matrix[2][0] = 9

        matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i]
        matrix[3 - 1 - 0][3 - 1 - 0] = matrix[0][3 - 1 - 0]
        matrix[2][2] = matrix[0][2]
        matrix[2][2] = 3

        matrix[j][m - 1 - i] = tmp
        matrix[0][3 - 1 - 0] = 1
        matrix[0][2] = 1

        j++
        j = 1

Step 4: j < 2
        1 < 2
        true

        tmp = matrix[0][1]
        tmp = 2

        matrix[i][1] = matrix[m - 1 - j][i]
        matrix[0][1] = matrix[3 - 1 - 1][0]
        matrix[0][1] = matrix[1][0]
        matrix[0][1] = 4

        matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - 1]
        matrix[3 - 1 - 1][0] = matrix[3 - 1 - 0][3 - 1 - 1]
        matrix[1][0] = matrix[2][1]
        matrix[1][0] = 8

        matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i]
        matrix[3 - 1 - 0][3 - 1 - 1] = matrix[1][3 - 1 - 0]
        matrix[2][1] = matrix[1][2]
        matrix[2][1] = 6

        matrix[1][m - 1 - i] = tmp
        matrix[1][3 - 1 - 0] = 1
        matrix[1][2] = 2

        j++
        j = 2

Step 5: j < 2
        2 < 2
        false

Step 6: i++
        i = 1

        1 < 3/2
        1 < 1
        false

Output:
[[7, 4, 1], [8, 5, 2], [9, 6, 3]]
Enter fullscreen mode Exit fullscreen mode

Discussion (0)