segmentation fault in rotation of vectors by 90 degrees clockwise in o(1) space complexity

Question

Note: Try to solve this task in-place (with O(1) additional memory), since this is what you'll be asked to do during an interview.

You are given an n x n 2D matrix that represents an image. Rotate the image by 90 degrees (clockwise).

Example

For

a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] the output should be

rotateImage(a) = [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

This is my code *

    std::vector<std::vector<int>> 
      rotateImage(std::vector<std::vector<int>> a) {
      int size=a.size();
      int tmp1=0,tmp2=0,tmp3=0;
      for(int i=0;i<size;i++)
      {
         for(int j=0;j<size;j++)
        {
           tmp3=a[size-1-j][i];
           tmp2=a[size-1-i][size-1-j];
           tmp1=a[j][size-1-i];
           a[j][size-1-i]=a[i][j];
           a[size-1-i][size-1-j]=tmp1;
           a[size-1-j][i]=tmp2;
           a[i][j]=tmp3;
           tmp1=0;
           tmp2=0;
           tmp3=0;
         }
      } 

      for (int i = 0; i < a.size(); i++) 
       {     //displaying
         for (int j = 0; j < a[i].size(); j++) 
           cout << a[i][j] << " ";
       cout << endl; 
      } 
     }

    expected output=[[7, 4, 1],
                     [8, 5, 2],
                     [9, 6, 3]]

but its showing a segmentation fault

*** Error in `main': munmap_chunk(): invalid pointer: 
            0x0000000000400ae0 
                               ***
           ======= Backtrace: =========
           /lib64/libc.so.6(+0x7c91c)[0x7f9f833ac91c]
          / lib64/libc.so.6(cfree+0x12c)[0x7f9f833bd0cc]
          main[0x40238a]
           main[0x402019]
           main[0x401b22]
          main[0x401575]
          main[0x401287]
          main[0x402524]
         main[0x4021a2]
         main[0x401d5b]
         main[0x40187f]
          main[0x40138d]
         main[0x400f89]
        /lib64/libc.so.6(__libc_start_main+0xea)[0x7f9f833504da]
         main[0x400a3a]

Good chances are, the error is in the code reading the matrix. Make sure the code that does not call `rotateImage` works before testing your code. — Sergey Kalinichenko, Jul 21 '19 at 08:14
My gues would be that you did not initialize the array in the first place. I checked your code (and initialized the variables). It does not segfault. But it does nothing. The code is not correct. You will find several solutions here on SO. See for example: https://stackoverflow.com/questions/2893101/how-to-rotate-a-n-x-n-matrix-by-90-degrees — A M, Jul 21 '19 at 08:47
`std::vector> rotateImage(std::vector> a)` This function signature is incompatible with the requirement of solving the problem in-place. Try `void rotateImage(std::vector> & a)`. — n. m. could be an AI, Jul 21 '19 at 09:27

gilad · Answer 1 · 2019-07-21T13:11:37.967

0

Change your function header to

void rotateImage(std::vector<std::vector<int>> a)

Your function is defined to return a std::vector<std::vector<int>> but you are not returning anything, this creates a problem with the vector's destructor.

edited Jul 21 '19 at 13:11

answered Jul 21 '19 at 08:30

gilad

426
1
5
15

score 0 · Answer 2 · answered Jul 21 '19 at 09:30

For a generic n (and if we can assume that the matrix is n x n), an in-place solution that requires O(1) additional memory is:

#include <vector>
#include <iostream>

// Gets x,y indices of element in position pos on a ring of side n
void posToIdx(int n, int pos, int & x, int & y) {
    if(pos < n) {
        x = 0;
        y = pos;
    }
    else if(pos < 2*n-1) {
        x = pos-n+1;
        y = n-1;
    }
    else if(pos < 3*n-2) {
        x = n-1;
        y = 3*n-3-pos;
    }
    else {
        x = 4*n-4-pos;
        y = 0;
    }
}


void rotateRing(std::vector<std::vector<int>> & a, int ring) {
    int n = a.size()-2*ring;
    int c = 4*n - 4;
    int x, y, x2, y2;
    posToIdx(n, c, x, y);
    x+=ring;
    y+=ring;
    int tmp = a[x][y];
    for(int i=c; i>0;--i) {
        posToIdx(n, i-1, x, y);
        x+=ring;
        y+=ring;
        posToIdx(n, i, x2, y2);
        x2+=ring;
        y2+=ring;
        a[x2][y2]=a[x][y];
    }
    posToIdx(n, 1, x2, y2);
    x2+=ring;
    y2+=ring;
    a[x2][y2]=tmp;
}

void rotateImage(std::vector<std::vector<int>> & a) {
    int n = a.size();

    for(int i=0;i<n/2;i++) {
       for(int j=0;j<n-2*i-1;j++) {
        rotateRing(a,i);
       }
    }
}

void print(std::vector<std::vector<int>> a) {
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < a[i].size(); j++) {
            std::cout << a[i][j] << " ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
}


int main()
{

    std::vector<std::vector<int>> a = {{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}};
    //std::vector<std::vector<int>> a = {{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}};
    //std::vector<std::vector<int>> a = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
    //std::vector<std::vector<int>> a = {{1,2,3},{4,5,6},{7,8,9}};

    print(a);
    rotateImage(a);
    print(a);

    return 0;
}

(tested up to n=6)

Welcome to StackOverflow. Please post minified and easily useable code in your questions and answers while using StackOverflow. Thank you. — Arka Mukherjee, Jul 21 '19 at 09:36

segmentation fault in rotation of vectors by 90 degrees clockwise in o(1) space complexity

2 Answers2