Rotating matrix by 90 degress in anticlockwise direction , where am i going wrong

Question

Given a square matrix mat[ ][ ] of size N x N. The task is to rotate it by 90 degrees in anti-clockwise direction without using any extra space. Problem Link

My Logic - for a matrix N x N, rotate the outer window in an anticlockwise direction by swapping elements starting from left column -> bottom row -> right column -> top row using temp variable X-1 time where X is the dimension of the outer window. I don't know why it's not working. Please Help me spot the problem.

#include<bits/stdc++.h>
using namespace std;

int main() {
int t=1; cin>>t;
while (t--) {
    int n; cin>>n; vector<vector<int>>a(n,vector<int>(n));
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>a[i][j];
    
    for(int k=0;k<n;k++) {
        int i=k, j=0, p=n-1-k, q=p-i, temp;
        while (q-- && i<p) {
            temp=a[i][i];j=i;
            while (j<=p) {
                swap(temp, a[j][i]);j++; 
            }j=i+1; 
            while (j<=p) {
                swap(temp, a[p][j]);j++;
            }j=p-1;
            while (j>=i) {
                swap(temp, a[j][p]); j--;
            }j=p-1;
            while (j>=i) {
                swap(temp, a[i][j]); j--;
            }
        }
    }
    for(int i=0;i<n;i++) {
         for(int j=0;j<n;j++) cout<<a[i][j]<<" ";
        cout<<"\n";
    }
    cout<<"\n";
}
}

Thank You

Answer 1

[Note: my previous solution uses extra memory, this one doesn't. So, I've deleted the previous solution and totally updated it to provide the new one].

Well, this problem can be solved easily if we are able to use extra space, but that is not the case. Anyway, it can also be solved easily without using another extra space.

At first, let me explain my solution for this problem. Then, I'll tell you about the wrong doing in your code. My solution is similar to your approach. It considers the input array as layers of rings or loops. See below:

0 0 0 0 0
0 1 1 1 0
0 1 2 1 0
0 1 1 1 0
0 0 0 0 0

The outer ring is the 0's, the inner ring is the 1's and so on...

Now, for arguments sake, let's assume we're using extra space b(we won't use this space in solution though). Also, let us assume, b is the solved array that contains the rotated matrix. Then, we may say:

b[(n + n - j - 1) % n][i] = a[i][j] // for any i, j
// here "n" is dimension of matrix
// "i", represents ith indexed row of a
// "j", represents jth indexed column of a

// if you having problem, how this thing just dropped from sky, then
// just write down in paper, for some index (x, y) what it becomes when it is rotated
// you'll see some formula like I've described above

Okay, now, if you're clear with the formula, let me describe how this helps to solve problem:

In the previous ring figure(the one I've used for showing rings), you can see that the corner elements of the 0's rings just changed with each other, i.e. the corner elements just swap places with each other when the matrix rotated, they never interfere with other elements. This is also, true for other elements too. There is always four elements in a group, and they just swap position with each other! There's only one exception is the center(if n is odd). And the center never changes position...

If you've also, observed the loop/group of four elements, those just swap position with each other, then we can just find out the next element's position from present element's position and place the present element's value and we're done... So, how do find out next position's value. Notice, we've already talked about it, how b's result is calculated from a. So, we may write something below:

pair<int, int> getNext(pair<int, int> x, int n) {
    return make_pair((n + n - x.second - 1) % n, x.first);
}

Now, come to rings, how many are there, that we should care about, well it's (n/2) rings. So, we'll just go to each ring, iterate through the elements of the first row of each ring(except the last one, cause it's included in the corner) and run a loop of four to replace the value properly in position. The full code is given below:

#include <iostream>
#include <string>

#define N 128

// returns next postition based on present position
// next position means where the present position value should
// be transferred after rotation
pair<int, int> getNext(pair<int, int> x, int n) {
    return make_pair((n + n - x.second - 1) % n, x.first);
}

int main() {
    int a[N][N];

    int n;
    scanf("%d", &n);

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    
    for(int h = 0; h < (n / 2); h++) {
        int s = h;
        int e = n - h - 1;

        for(int k = s; k < e; k++) {
            auto p = make_pair(s, k); // row = s, and col = k
            int t = a[p.first][p.second];

            for(int c=0; c<4; c++) {
                auto p2 = getNext(p, n);
                int temp = a[p2.first][p2.second];

                a[p2.first][p2.second] = t;

                t = temp;
                p = p2;
            }
        }
    }

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }

    return 0;
}

Now, what is wrong with your code:

I guess, you've already understood, that your algo is not correct...and the implementation is buggy too...

[P.S.]: pls, don't just copy paste the code, first understand it. Also, write code in a manner, so other's can read...and if any error you find with the algo I've provided or you may have problem with understanding any concept, let me know in the comment...

Answer 2

I would like to suggest an approach that looks more simpler.

Let's assume that you have a vector of vectors of the type char like this.

a b c d 
e f g h 
i j k l 
m n o p

The result vector must look like

d h l p 
c g k o 
b f j n 
a e i m 

The result vector can be built in two steps.

In the first step the rows of the source vector are swapped.

m n o p 
i j k l 
e f g h 
a b c d 

In the second step there are swapped elements relative to the side diagonal that is for example 'm' is swapped with 'd', 'n' is swapped with 'h' and 'o' is swapped with 'l'. Then these operations are repeated for element of the second row the second column from the end of the vector.

Here is a demonstrative program.

#include <iostream>
#include <utility>
#include <vector>

int main() 
{
    std::vector<std::vector<char>> a =
    {
        { 'a', 'b', 'c', 'd' },
        { 'e', 'f', 'g', 'h' },
        { 'i', 'j', 'k', 'l' },
        { 'm', 'n', 'o', 'p' },
    };
    
    auto n = a.size();
    
    for ( const auto &row : a )
    {
        for ( const auto &item : row )
        {
            std::cout << item << ' ';
        }
        std::cout << '\n';
    }
    std::cout << '\n';
    
    for ( size_t i = 0; i < n / 2; i++ )
    {
        std::swap( a[i], a[n-i-1] );
    }

    for ( const auto &row : a )
    {
        for ( const auto &item : row )
        {
            std::cout << item << ' ';
        }
        std::cout << '\n';
    }
    std::cout << '\n';
    
    for ( size_t i = 0; i + 1 < n; i++ )
    {
        for ( size_t j = 0; j + i + 1 < n; j++ )
        {
            std::swap( a[i][j], a[n-j -1][n - i -1]);
        }
    }
    
    for ( const auto &row : a )
    {
        for ( const auto &item : row )
        {
            std::cout << item << ' ';
        }
        std::cout << '\n';
    }
    std::cout << '\n';

    return 0;
} 

The program output is

a b c d 
e f g h 
i j k l 
m n o p 

m n o p 
i j k l 
e f g h 
a b c d 

d h l p 
c g k o 
b f j n 
a e i m