HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Rotate image 90 degree clockwise

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
degreerotateimageclockwise

Problem

* Time complexity: O(N)

* Memory complexity: \$O(1)\$

Is my calculation of complexity correct for this code?

#include 
#include 
#include 

using namespace std;

using Vector = vector>;

int main()
{
    const size_t SIZE = 7;

    Vector image(SIZE, vector(SIZE));

    cout << "******* original image ******" << endl;
    int value = 0;
    for (auto& i : image)
    {
        for (auto& j : i)
        {
            cout << (j = value) << ' ';
        }

        value++;
        cout << '\n';
    }

    // rotate image 90 degree clockwise O(N)time & O(1)memory ???
    for (size_t i = 0; i < image.size(); ++i)
    {
        for (size_t j = 0; j < (image.size() - i); ++j)
        {
            swap(image[i][j], image[image.size() - j - 1][image.size() - i - 1]);
        }
    }

    cout << "\n******* rotated image ******" << endl;
    for (const auto& i : image)
    {
        for (const auto& j : i)
        {
            cout << j << ' ';
        }

        cout << '\n';
    }
}

Solution

This code doesn't rotate the image 90 degrees clockwise.

We can see this by making each entry in the matrix distinct (the important part is moving value++ inside the inner loop)

for (auto& i : image)
{
    for (auto& j : i)
    {
        cout << setfill(' ') << setw(3) << (j = value) << ' ';
        value++;
    }

    cout << '\n';
}


Then the output is

$ ./a.exe
******* original image ******
  0   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  41
 42  43  44  45  46  47  48

******* rotated image ******
 48  41  34  27  20  13   6
 47  40  33  26  19  12   5
 46  39  32  25  18  11   4
 45  38  31  24  17  10   3
 44  37  30  23  16   9   2
 43  36  29  22  15   8   1
 42  35  28  21  14   7   0

Code Snippets

for (auto& i : image)
{
    for (auto& j : i)
    {
        cout << setfill(' ') << setw(3) << (j = value) << ' ';
        value++;
    }

    cout << '\n';
}
$ ./a.exe
******* original image ******
  0   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  41
 42  43  44  45  46  47  48

******* rotated image ******
 48  41  34  27  20  13   6
 47  40  33  26  19  12   5
 46  39  32  25  18  11   4
 45  38  31  24  17  10   3
 44  37  30  23  16   9   2
 43  36  29  22  15   8   1
 42  35  28  21  14   7   0

Context

StackExchange Code Review Q#73990, answer score: 5

Revisions (0)

No revisions yet.