Array Algorithm: Rotate an image

Solution

We will try to rotate on the paper to find the rules on how it rotates. It looks like we just pull out 4 elements top, right, bottom, and left then swap its value.
But how do it continuously? We can think of an iterator from 0 to the size of a row, each iteration just increase i variable straightforward, and the size of a row is equal to the size of the column, then we can play around with the i variable and the length of the row to reach all the matrix positions.
But it is not enough, a matrix may have several layers based on its size, imagine a 3x3 Rubik, you rotate the outside layer but not the center cell, and for the 4x4 matrix, you have no center cell, 2 layers will be rotating. So we can come to the rule of the number of layers like layers = matrix length / 2.
Now we play around with layer, size(length), and i (a row iterator) to reach all the matrix positions. Let resolve a subproblem first.

var top = matrix[layer][i];
var right = matrix[i][length - layer];
var bot = matrix[length - layer][length -i];
var left = matrix[length - i][layer];
  • Top will be fixed the row, only the column moving by i
  • Right fixed by the column, only the row moving by i
  • Bottom fixed by the row, opposite of the top
  • Left fixed by the column, opposite of the right
// top = left
matrix[layer][i] = left;
// right = top
matrix[i][length - layer] = top;
// bot = right
matrix[length - layer][length - i] = right;
// left = bot
matrix[length - i][layer] = bot;
public class Solution {
public void Rotate(int[][] matrix) {
var layers = matrix.Length / 2;
var length = matrix.Length - 1;

for(var layer = 0; layer < layers; layer++){

for(var i = layer; i < length - layer; i++){
var top = matrix[layer][i];
var right = matrix[i][length - layer];
var bot = matrix[length - layer][length -i];
var left = matrix[length - i][layer];

// top = left
matrix[layer][i] = left;
// right = top
matrix[i][length - layer] = top;
// bot = right
matrix[length - layer][length - i] = right;
// left = bot
matrix[length - i][layer] = bot;
}
}
}
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Finn Nguyen

Finn Nguyen

Software Engineer who is highly interested in building high scalability systems.