erip - 6 months ago 22

C++ Question

I've seen several questions here that don't quite answer my question. I'm trying to do a rendition of the classic matrix rotation question used so often in interview questions. Instead of focusing on the square matrix, I'm interested in M x N matrices.

For input matrix

`1 2 3`

4 5 6

7 8 9

1 2 3

I'd like to transform the matrix into

`3 2 1`

9 8 7

6 5 4

3 2 1

Here is the code I've written:

`#include <iostream>`

#include <vector>

#include <algorithm>

void do_swaps(int& a, int& b, int& c, int& d) {

std::swap(a, b);

std::swap(c, d);

}

void rotate(std::vector<std::vector<int>>& v) {

size_t m = v.size();

size_t n = v[0].size();

for(size_t i = 0; i < m/2; ++i) {

for(size_t j = 0; j <= n/2; ++j) {

do_swaps(v[i][j], v[m-i-1][n-j-1], v[m-j-1][i], v[j][n-i-1]);

}

}

}

void print(const std::vector<std::vector<int>>& v) {

size_t m = v.size();

size_t n = v[0].size();

for(size_t i = 0; i < m; ++i) {

for(size_t j = 0; j < n; ++j) {

std::cout << v[i][j] << ' ';

}

std::cout << '\n';

}

}

int main() {

std::vector<std::vector<int>> m{{1,2,3}, {4,5,6}, {7,8,9}, {1, 2, 3}};

std::cout << "Before: \n";

print(m);

rotate(m);

std::cout << "\nAfter: \n";

print(m);

}

And here's my output:

`Before:`

1 2 3

4 5 6

7 8 9

1 2 3

After:

3 2 1

9 5 7

6 8 4

3 2 1

My code works for 3 x 3 matrices (haven't tested higher dimensional matrices), but I seem to have an off by one error in my code causing the inner-most elements to remain unswapped.

In the line

`for(size_t j = 0; j <= n/2; ++j) {`

`j < (n+1)/2;`

`j < (n-1)/2;`

Can someone explain where I've gone wrong in my algorithm?

Answer

You don't take care of middle line in case when lines number is odd.

Further, you swap elements that lie on the middle column (when columns number is odd) twice. You can check if `m`

is odd with a bitwise-and with 1.

The following is an easier way to project swapped values is presented above and you don't even have to care about the middle column in this case.

```
void rotate(std::vector<std::vector<int>>& v) {
size_t m = v.size();
size_t n = v[0].size();
for (size_t i = 0; i < m / 2; ++i)
{
for (size_t j = 0; j < n; ++j)
std::swap(v[i][j], v[m - i - 1][n - j - 1]);
}
if (m&1)
for (size_t i = 0; i< n/2; ++i)
std::swap(v[m/2][i], v[m/2][n-i-1]);
}
```