CODEWITHSUNDEEP
algorithm
Pierre-Alexandre
Pierre-Alexandre

Reputation: 775

Rotate Image - Java

I am doing a question where, given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation. This my my code:

   class Solution {
        public void rotate(int[][] matrix) {
            int size = matrix.length;
            for(int i = 0 ; i < matrix.length; i++){
                for(int y = 0 ; y < matrix[0].length ; y++){
                    matrix[i][y] = matrix[size - y - 1][i];
                    System.out.println(size - y - 1);
                    System.out.println(i);
                    System.out.println("");
                }
            }
        }
    }

This is the input and output results:

I do not really understand why I am getting duplicates in my output such as the number seven 3 times. On my System.out.println statement, I am getting the correct list of indexes :

2
0

1
0

0
0

2
1

1
1

0
1

2
2

What can be wrong?

Upvotes: 0

Views: 226

Answers (1)

Anuj
Anuj

Reputation: 1665

I have found a solution. I will try my best to explain it.

Let us consider an array of size 4.

1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16

Now lets look at the numbers present only on the outside of the array:

1  2  3  4
5        8
9        12
13 14 15 16

We will proceed by storing the first element 1 in a temporary variable. Next we will replace 1 by 13, 13 by 16, 16 by 4 and at last 4 by 1 (whose value we already stored in the temporary variable).

We will do the same for all the elements of the first row.

Here is a pseudocode if you just want to rotate this outer ring, lets call it an outer ring:

for i = 0 to n-1
{
    temp = A[0][i];
    A[0][i] = A[n-1-i][0];
    A[n-1-i][0] = A[n-1-0][n-1-i];
    A[n-1-0][n-1-i] = A[i][n-1-0];
    A[i][n-1-0] = temp;
}

The code runs for a total of n times. Once for each element of first row. Implement this code an run it. You will see only the outer ring is rotated. Now lets look at the inner ring:

   6  7   
  10 11

Now the loop in pseudocode only needs to run for 2 times and also our range of indexes has decreased. For outer ring, the loop started from i = 0 and ended at i = n-1. However, for the inner ring the for loop need to run from i = 1 to i = n-2.

If you had an array of size n, to rotate the xth ring of the array, the loop needs to run from i = x to i = n-1-x.

Here is the code to rotate the entire array:

x = 0;
int temp;

while (x < n/2)
{
    for (int i = x;i < n-1-x;i++)
    {
        temp = arr[x][i];
        arr[x][i] = arr[n-1-i][x];
        arr[n-1-i][x] = arr[n-1-x][n-1-i];
        arr[n-1-x][n-1-i] = arr[i][n-1-x];
        arr[i][n-1-x] = temp;
    }

    x++;
}

Here each value of x denotes the xth ring.

0 <= x <= n-1

The reason why the outer loop runs only for x < n/2 times is because each array has n/2 rings when n is even and n/2 + 1 rings if n is odd.

I hope I have helped you. Do comment if face any problems with the solution or its explanation.

Upvotes: 1

Related Questions