Java recursive solution by mutating the array each time. Inefficient but interesting.


  • 1
    Y
    /**
     * mutate the original matrix each time and recursively solve the question. 
    **/
    public List<Integer> spiralOrder(int[][] matrix) {
            List<Integer> result = new LinkedList<>();
            if (matrix == null || matrix.length == 0) {
                return result;
            }
            
            for (int i = 0; i < matrix[0].length; i++) {
                result.add(matrix[0][i]); //Add the first row of the matrix into result list
            }
            
            //Construct a new array without the first row by let the last column of the original matrix be the first row in the new column and so on. Like left rotate the original matrix without the first row. 
            if (matrix.length > 1) {
                int[][] newMatrix = new int[matrix[1].length][matrix.length - 1];
                int row = 0;
                for (int i = matrix[1].length - 1; i >= 0; i--) {
                    for (int j = 1; j < matrix.length; j++) {
                        newMatrix[row][j - 1] = matrix[j][i];
                        //System.out.println(row + " " + (j - 1) + ":" + newMatrix[row][j - 1] + ", ");
                    }
                    row++;
                }
                result.addAll(spiralOrder(newMatrix));
            }
            
            return result;
        }
    

    I think the time complexity is O(m * n * (min{m, n})^2) and the space complexity is O(m * n).
    Please let me know if you have any optimization choice.


  • 0
    R

    it's a smart approach. Thanks


  • 0

    Nice, but you do not necessarily have to copy the matrix each time. You could create a new recursive function that take (always) the original matrix and boundary variables as parameters.


Log in to reply
 

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