Rotate Image and Spiral Matrix

Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Suffered from this problem for a long time. Finally came up with an elegant solution.

Complete code,

1:  public class Solution {  
2:    public void rotate(int[][] matrix) {  
3:      int n = matrix.length;  
4:      if(n <= 1)  
5:        return;  
6:      for(int i = 0; i < n/2; i++) {  
7:        for(int j = i; j < n-i-1; j++) {  
8:          int tmp = matrix[i][j];  
9:          matrix[i][j] = matrix[n-1-j][i];  
10:          matrix[n-1-j][i] = matrix[n-1-i][n-1-j];  
11:          matrix[n-1-i][n-1-j] = matrix[j][n-1-i];  
12:          matrix[j][n-1-i] = tmp;  
13:        }  
14:      }  
15:    }  
16:  }  

There is a similar problem. It's tricky to solve it use the above solution. Found a really nice solution online.

Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,

Given the following matrix:

[

 [ 1, 2, 3 ],

 [ 4, 5, 6 ],

 [ 7, 8, 9 ]

]

You should return [1,2,3,6,9,8,7,4,5].

Refer to the original solution from http://ideone.com/bt8A5O

1:  public class Solution {  
2:    public List<Integer> spiralOrder(int[][] matrix) {  
3:      List<Integer> res = new LinkedList<Integer> ();  
4:      int m = matrix.length;  
5:      if(m == 0)  
6:        return res;  
7:      int n = matrix[0].length;  
8:      int left = 0;  
9:      int right = n-1;  
10:      int top = 0;  
11:      int bottom = m-1;  
12:      while(true) {  
13:        for(int i = left; i <= right; i++)  
14:          res.add(matrix[top][i]);  
15:        top++;  
16:        if(top>bottom || right<left)  
17:          break;  
18:        for(int i = top; i <= bottom; i++)  
19:          res.add(matrix[i][right]);  
20:        right--;  
21:        if(top>bottom || right<left)  
22:          break;  
23:        for(int i = right; i >= left; i--)  
24:          res.add(matrix[bottom][i]);  
25:        bottom--;  
26:        if(top>bottom || right<left)  
27:          break;  
28:        for(int i = bottom; i >= top; i--)  
29:          res.add(matrix[i][left]);  
30:        left++;  
31:        if(top>bottom || right<left)  
32:          break;  
33:      }  
34:      return res;  
35:    }  
36:  }