Rotate Image (Leetcode 48)

Difficulty: Medium Link: April Leetcode Challenge: Day 25

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.

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]]

Example 3:

Input: matrix = [[1]]
Output: [[1]]

Example 4:

Input: matrix = [[1,2],[3,4]]
Output: [[3,1],[4,2]]

Constraints

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

Solution

The problem is simple if we can understand the trick which will lead us to the solution. This problem can be solved in various ways, but we will be looking using the matrix properties and operations. If we look carefully, the every column of the matrix in input gets converted into a column in the output (But in reverse). Now what operation does it closely resembles to?

Matrix Transpose

Matrix Transpose on 3x 3

Matrix Transpose

To find the transpose of the matrix, we simply need to traverse in using two loops and swap the element at (i , j) to (j, i). This is a simple operation and after that we can see that every column value maps to a row but elements need to be reversed. We can now loop through every row and reverse the matrix.

Reverse

Be careful to loop till only half columns while reversing otherwise elements would get reversed twice and the matrix remains the same.

Code

Swift

class Solution {
func rotate(_ matrix: inout [[Int]]) {
let n = matrix.count
// Transpose
for i in 0..<n {
for j in 0..<n {
if i <= j {
(matrix[i][j],matrix[j][i]) = (matrix[j][i] ,matrix[i][j])
}
}
}
// Reverse rows
for i in 0..<n {
var low = 0, high = n 1
while low < high, low < n/2 {
( matrix[i][low], matrix[i][high] ) = (matrix[i][high], matrix[i][low])
low += 1
high -= 1
}
}
}
}

Python

lass Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
for i in xrange(n):
for j in xrange(n):
if i < j:
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for l in matrix:
l.reverse()

Java

public void rotate(int[][] matrix) {
if (matrix == null || matrix.length <= 1) {
return;
}
int n = matrix.length;
// Transpose
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// Reverse rows
for (int i = 0; i < n; i++) {
int head = 0;
int tail = n 1;
while (head < tail) {
int temp = matrix[i][head];
matrix[i][head] = matrix[i][tail];
matrix[i][tail] = temp;
head++;
tail;
}
}
}

Complexity Analysis

We are iterating every element in the 2D matrix hence complexity would be in the order of matrix elements. Same is for the transpose and reversing row operations. Since solution was required to be in-place it is a constant space operation.

Time = O(N2)

Space = O(1)

Leave a Reply

Your email address will not be published. Required fields are marked *