Rotate Image / Rotate a square matrix by 90 degrees - Leetcode problem

 Question Link : https://leetcode.com/problems/rotate-image/

 Problem: 

        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.

Constraint: 

        Rotation must be done in-place( O(1) space ).

Approach:

1. Notice how an element changes its position (index) .

2. It follows the formula : [new_x][new_y]=[old_y][N-1-old_x]   where N=no. of rows

3. Now let's follow the formula and check 

        1 will go to 3's place

        3 will go to 9's place

        9 will go to 7's place

        7 will go to 1's place

    Thus,  1->3->9->7

3. Thus by using the recursion function go() below we can loop this.

4. And while backtracking the recursion we will move the elements to its new index.

5. First element was saved in temp variable, which when going back will be put in place.

6. We will traverse the array like a concentric circle, first outer square,then inner square.

7. ref will be used to get the next point from where we need to start traversing.

Here is the code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
    int n;
    int temp;
public:
    void rotate(vector<vector<int>>& m) {
        
        n=m.size();
        
        int ref=0;
        
        for(int row=0;row<(n/2);row++)
        {
             for(int col=row;col<(n-1-ref);col++)
             {
                  temp=m[row][col];
                  
                  go(row,col,1,m);
             }
            ref++;
            
        }
        
    }
    
    void go(int row,int col,int len,vector<vector<int>>& m)
    {
         
        
        int fut_x=col;
        int fut_y=n-1-row;
        
        
        if(len<4)
             go(fut_x,fut_y,len+1,m);
        
        if(len!=1)
             m[fut_x][fut_y]=m[row][col];
        else  m[fut_x][fut_y]=temp;
    }
};