Complete explanation with Java solution


  • 1
    J

    The Problem Statement
    You are given an nxn 2D matrix representing an image. Rotate the image by 90 degrees (clockwise).
    Example
    Given a matrix:
    [1,2,3]
    [4,5,6]
    [7,8,9]
    Rotate it by 90 degrees (clockwise), return:
    [7,4,1]
    [8,5,2]
    [9,6,3]

    Solution
    The key to the problem is finding a way to swap elements, which requires an intermediate step as explained by @shichaotan. The intermediate step involves reversing the row order. The swap step involves diagonally swapping all but the 1st element.

     Input     Inter. Step   Swap Step
    [1,2,3]      [7,8,9]      [7,4,1]
    [4,5,6]  =>  [4,5,6]  =>  [8,5,2]
    [7,8,9]      [1,2,3]      [9,6,3]
    

    Now, let's evaluate the each swap (the headings represent positions):

     Input     Inter. Step    01<->10  02<->20  12<->21
    [1,2,3]      [7,8,9]      [7,4,9]  [7,4,1]  [7,4,1]
    [4,5,6]  =>  [4,5,6]  =>  [8,5,6]=>[8,5,6]=>[8,5,2]
    [7,8,9]      [1,2,3]      [1,2,3]  [9,2,3]  [9,6,3]
    

    The Code
    See this GitHub link for my complete solution with test cases.

       public static void rotate(int[][] matrix) {
          // Reverse rows - Since we are *swapping* rows,
          // only do this for half of them
          for (int r = 0; r<matrix.length/2; r++) {
             int tmp[] = matrix[r];
             matrix[r] = matrix[matrix.length-1-r];
             matrix[matrix.length-1-r] = tmp;
          }
    
          // Diagonal swap
          // Visit each row, but skip cols by row+1
          for (int r = 0; r<matrix.length; r++) {
             for (int c = r+1; c<matrix[r].length; c++) {
                 int tmp = matrix[r][c];
                 matrix[r][c] = matrix[c][r];
                 matrix[c][r] = tmp;
             }
          }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.