Leetcode 54 Spiral Matrix and 59 Spiral Matrix II

Leetcode 54 Spiral Matrix and 59 Spiral Matrix II

Leetcode 54 Spiral Matrix
Edit Spiral Matrix on GitHub

The problem description is as follow:

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].

Analysis

The moment you get this problem, you should think recursively:

1. Given a matrix of m rows and n columns, peel the first layer of the matrix just like peeling an onion
2. After peeling the first layer, the matrix now contains (m-2) rows and (n-2) columns
3. For the new (m-2)*(n-2) matrix, do the same peeling job recursively 
4. At some point, the row number or column number must be 0 or 1, after peeling this last layer, end the recursive process

Here comes the easiest part:

public class Solution {
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> result = new ArrayList<Integer>();
 
        if(matrix == null || matrix.length == 0) return result;
 
        int m = matrix.length;
        int n = matrix[0].length;
 
        int x=0; 
        int y=0;
 
        while(m>0 && n>0){
 
            //if one row or one column left, no circle can be formed
            if(m==1){
                for(int i=0; i<n; i++){
                    result.add(matrix[x][y++]);
                }
                break;
            }else if(n==1){
                for(int i=0; i<m; i++){
                    result.add(matrix[x++][y]);
                }
                break;
            }
 
            //below, process the circle
 
            //top - move right
            for(int i=0;i<n-1;i++){
                result.add(matrix[x][y++]);
            }
 
            //right - move down
            for(int i=0;i<m-1;i++){
                result.add(matrix[x++][y]);
            }
 
            //bottom - move left
            for(int i=0;i<n-1;i++){
                result.add(matrix[x][y--]);
            }
 
            //left - move up
            for(int i=0;i<m-1;i++){
                result.add(matrix[x--][y]);
            }
 
            x++;
            y++;
            m-=2;
            n-=2;
        }
 
        return result;
    }
}

Leetcode 59 Spiral Matrix II
Edit Spiral Matrix II on GitHub

The problem description is as follow:

Given an integer n, generate a square matrix filled with elements from 1 to n^2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

Well, this problem is exactly the same as the previous, only the other way around. Instead of peeling the onion layer by layer, we need to create the onion layer by layer.

public class Solution {
    public int[][] generateMatrix(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (n<=0){
            return new int[0][0];
        }
        int [][] matrix=new int[n][n];
        int total = n*n;
        int beginX=0;
        int endX=n-1;
        
        int beginY=0;
        int endY=n-1;
        int current=1;
        
        while (current<=total){
            for (int col=beginX; col<=endX; col++){
                
                matrix[beginY][col]=current++;
            }
            beginY++;
            for (int row=beginY; row<=endY; row++){
                matrix[row][endX]=current++;
            }
            endX--;
            
            for (int col=endX; col>=beginX; col--){
                matrix[endY][col]=current++;
            }
            endY--;
            
            for (int row=endY; row>=beginY; row--){
                matrix[row][beginX]=current++;
            }
            beginX++;
        }
                       
        return matrix;
    }
}