Let say you have an image represented by an NXN matrix where each pixel in the image is 4 byte.So rotate this image in place by 90 degree.
Solution:
public void rotate(int[][] matrix ,in n) { for(int layer = 0, layer < n/2; ++layer) { int first =layer; int last =n-1-layer; for(int i=first;i < last; ++i) { int offset = i- first; int top=matrix[first][i]; //save top matrix[first][i]=matrix[last-offset][first];// left-top matrix[last-offset][first]=matrix[last][last - offset]; //bottom-left matrix[last][last - offset] = matrix[i][last]; //right - bottom matrix[i][last] =top; //top-right } } }
Complexity: o(n^2) because any algorithm must touch all N^2 element.
if you see closely what i am doing is:
Follow this-
1. for i=0 to n
2.temp=top[i];
3.top[i]=left[i];
4.left[i]=bottom[i];
5.bottom[i] = right[i];
6.right[i] = temp;
we are performing swap on each layer.starting from outer most layer and working our way inwards.