class Solution {

    public void rotate(int[][] matrix) {

        //1.transpose

        for(int i = 0; i < matrix.length; i++){

            for(int j = 0; j < i; j++){

                int temp = matrix[i][j];

                matrix[i][j] = matrix[j][i];

                matrix[j][i] = temp;

            }

        }

        //flip the matrix horizontally

        for(int i = 0; i < matrix.length; i++){

            for(int j = 0; j < matrix[0].length / 2; j++){

                int temp = matrix[i][j];

                matrix[i][j] = matrix[i][matrix[0].length - 1 -j];

                matrix[i][matrix[0].length - 1 -j] = temp;

            }

        }

    }

}

class Solution {

    public List<Integer> spiralOrder(int[][] matrix) {

        List<Integer> res = new ArrayList<Integer>();

        if(matrix == null || matrix.length == 0 || matrix[0].length == 0)

            return res;

        int rowBegin = 0, rowEnd = matrix.length - 1, colBegin = 0, colEnd = matrix[0].length - 1;

        while(rowBegin <= rowEnd && colBegin <= colEnd){

            //to right

            for(int j = colBegin; j <= colEnd; j++)  res.add(matrix[rowBegin][j]);

            rowBegin++;

            for(int i = rowBegin; i <= rowEnd; i++)  res.add(matrix[i][colEnd]);

            colEnd--;

            for(int j = colEnd; j >= colBegin && rowBegin <= rowEnd; j--)  res.add(matrix[rowEnd][j]);

            rowEnd--;

            for(int i = rowEnd; i >= rowBegin && colBegin <= colEnd; i--) res.add(matrix[i][colBegin]);

            colBegin++;

        }

        return res;

    }

}

class Solution {

    public int[][] generateMatrix(int n) {

        if(n == 0)

            return null;

        int[][] matrix = new int[n][n];

        int rowBegin = 0, rowEnd = n - 1, colBegin = 0, colEnd = n - 1;

        int count = 0;

        while(rowBegin <= rowEnd && colBegin <= colEnd){

            //right

            for(int j = colBegin; j <= colEnd; j++)

                matrix[rowBegin][j] = ++count;

            rowBegin++;

            //down

            for(int i = rowBegin; i <= rowEnd; i++)

                matrix[i][colEnd] = ++count;

            colEnd--;

            //left

            for(int j = colEnd; j >= colBegin; j--)

                matrix[rowEnd][j] = ++count;

            rowEnd--;

            //up

            for(int i = rowEnd; i >= rowBegin; i--)

                matrix[i][colBegin] = ++count;

            colBegin++;

        }

        return matrix;

    }

}