Is there any kind of another approach to solve this problem rather than Brute Force ?
Rotate the 2D matrix
Yes, you could optimise on space complexity, you could do the rotation in-place
Algo is as follows:
The idea is for each square cycle, we swap the elements involved with the corresponding cell in the matrix in anti-clockwise direction i.e. from top to left, left to bottom, bottom to right and from right to top one at a time. We use nothing but a temporary variable to achieve this.
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
in the first cycle: rotate 1 4 16 13 the outer corner using a temp variable
followed by 2 8 14 5 …
in the 2nd cycle : rotate 6 7 11 10
enclosing the code
I want to know a simple question I bit confused something. Suppose we are using the extra space of temp arrays in our algo and if simply paste the temp result to our original arrays , then we consider that our algo is taking extra space or not ? Although in the above program I have assing the memory is statistically but suppose we assign the memory Dynamically. Can I know your point of view?
Yes, u are definitely using extra space in that scenario, whenever u declare an additional space apart from the given i/p, it is considered using additional space , in this case since temp is 2D matrix o(n^2) space is being used
Could u elaborate on what u mean by this?
@chhavibansal yes sure. Let suppose I have created a temp array varible using pointer Dynamically allocated the memory and after that I copy the temp elements to the original arrays and then delete the temp variable.
I bit Confused when analyse the algorithm I thought when we dynamically allocate the memory and don’t delete them, they are used that are counted as the space in our algo. please correct me?
See even if we delete the dynamically allocated array, for once during the course of run of the program we are using temprorary space so the worst time complexity when calculated would include the space occupied by the dynamically allocated array.
Basically when taking of worst case time or space complexity we are talking of the peek situation where max. allocation of resources is being done, it is inconsiderate of the fact that the memory is deleted later or no.
Hope this clarifies ur doubt