Image rotation for rectangular array in 0(1) space complexity

#1
  1. ) In the image rotation problem, transposing and reversing rows works as explained for nn matrix. in case we have a nm matrix, the transpose would be m*n and we can only use one array. is there a way to change the order of the array (if its dynamically allocated)?
    Here is my current code for your reference. (https://ide.codingblocks.com/s/169358)
    2.) also, before this code, i tried to work this using two functions, one for transposing matrix and another for reversing rows(didnt work). can you explain with example how one can pass a 2-d int array to a function as parameter (pass by reference) and return the same 2d array? how can we accomplish this with or without pointers… please clarify.
#2

Hey @ilovetocode, you can pass 2D array to function using double pointer and make changes to it. Here is the example
#include
using namespace std;

//function to display 2D array
void show(int **arr,int x,int y)
{
int i,j;
for(i=0;i<x;i++)
{
for(j=0;j<y;j++)
{
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
}

//main program
int main()
{
int n,m;
//input number of rows and columns
cout<<"Enter No. of rows: ";
cin>>n;
cout<<"Enter No. of columns: ";
cin>>m;

//pointer to 2D array
int **A=new int*[n];

//pointer initialization
for(int i=0;i<n;i++)
{
	A[i]=new int[m];
}

//input array elements
for(int i=0;i<n;i++)
{
	for(int j=0;j<m;j++)
	{
		cin>>A[i][j];
	}
}

//display 2D array
show(A,n,m);

return 0;

}
But If you want to change order of that dynamic array, you need to create another array of different order and then copy old content into new one

#3

Thanks for your response, I can now use my functions for the problem.
However it’s specified in the image rotation problem that we have to solve it by using space complexity (1)… I.e. we can’t use 2 arrays.
So how do we solve the problem for rectangular matrix?

#4

hey @ilovetocode, you can solve this problem with O(1) space complexity as you can do transpose without using any extra space.

#5

How can i do transpose of a rectangular matrix without using any extra space?
a matrix or order mn, after transpose will be of order nm.
where and how do i store this new matrix, if my orignal is of a different, unchangable order.
please resolve.

#6

hey @ilovetocode, this question is for square matrix and you can transpose in O(1) space for sqaure matrix.
Here islogic for it
for(int i=0;i<row;i++)
{
for(int j=0;j<i;j++)
{
swap(mat[i][j],mat[j][i]);
}
}

However for rectangular matrix, we need extra space to transpose