We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
My solution in Java language.
Time complexity: O(m * n).
Space complexity: O(n + m).
publicstaticvoidmatrixRotation(List<List<Integer>>matrix,intr){// Write your code here/* *Level of abstraction: - A rectangle. - A circle. - A element in that circle. Each level contains a loop or whatever related. *Ideas: - Identify each circle, store variables about the position of 4 corners, boolean arrays to check if a element is shifted or not, and if it has assigned new value or not. - Handle rotation in each circle inside the rectangle + Storing a queue to swap elements - With each element in specific position: + Identify its place in the circle. + Check if how far it can move until it reach its new position. + In the new position, if it didnt shift, then add its value to the queue and assign new value. + If a position is shifted but not assigned, assign the first value from queue. - Handle the next one until cannot. *Step to rotate in each circle: - Find the length of the circle: l = 2*(m+n)-4. - Assign r := r % l - Identify the position in the circle. - Move until it reach the final position. - ... *///Prepare before going into circle levelintm=matrix.size()-1;intn=matrix.get(0).size()-1;int[]o={0,0};intrTemp;while(m>0&&n>0){//Prepare before traverse through elements.int[]corners={o[1],o[0]+m,o[1]+n,o[0]};intl=2*(m+n);rTemp=r%l;boolean[]shift=newboolean[l];boolean[]assign=newboolean[l];Queue<Integer>q=newLinkedList<>();//Starting position:int[]pos={o[0],o[1]};intp=0;intvPos;//value of posint[]fPos;// final posfor(;p<l;p++){if(assign[p])vPos=q.poll();elsevPos=matrix.get(pos[0]).get(pos[1]);fPos=shift(pos,corners,rTemp);if(!shift[(p+rTemp)%l])q.add(matrix.get(fPos[0]).get(fPos[1]));matrix.get(fPos[0]).set(fPos[1],vPos);//Update in boolean arraysshift[p]=true;assign[(p+rTemp)%l]=true;//Assign new positionpos=shift(pos,corners,1);}//Assign new m,n, and left top elementm-=2;n-=2;o[0]++;o[1]++;}//Printfor(inti=0;i<matrix.size();i++){for(intj=0;j<matrix.get(0).size();j++){System.out.print(matrix.get(i).get(j)+" ");}System.out.println();}}staticint[]shift(int[]pos,int[]corners,intstep){int[]newPos={pos[0],pos[1]};intdirect;inti=0;while(i<step){if(newPos[0]==corners[3]&&newPos[1]!=corners[0]){direct=0;if(step-i>=newPos[1]-corners[direct]){i+=newPos[1]-corners[direct];newPos[1]=corners[direct];}else{newPos[1]-=(step-i);i=step;}}elseif(newPos[0]!=corners[1]&&newPos[1]==corners[0]){direct=1;if(step-i>=corners[direct]-newPos[0]){i+=corners[direct]-newPos[0];newPos[0]=corners[direct];}else{newPos[0]+=(step-i);i=step;}}elseif(newPos[0]==corners[1]&&newPos[1]!=corners[2]){direct=2;if(step-i>=corners[direct]-newPos[1]){i+=corners[direct]-newPos[1];newPos[1]=corners[direct];}else{newPos[1]+=(step-i);i=step;}}elseif(newPos[0]!=corners[3]&&newPos[1]==corners[2]){direct=3;if(step-i>=newPos[0]-corners[direct]){i+=newPos[0]-corners[direct];newPos[0]=corners[direct];}else{newPos[0]-=(step-i);i=step;}}}returnnewPos;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Matrix Layer Rotation
You are viewing a single comment's thread. Return to all comments →
My solution in Java language. Time complexity: O(m * n). Space complexity: O(n + m).