My recursive JAVA solution with comment, instead of using 4 for loops to go through each edge


  • 0
    C

    private void spiralOrderHelper(int[][] matrix, int i, int j, int dir, boolean[][] isVisited, ArrayList<Integer> list, int[] di, int[] dj) {

        //if the entry is already visited, no need to add it into list again
        if(!isVisited[i][j]) {
            isVisited[i][j] = true;
            list.add(matrix[i-1][j-1]);
        }
    
        //Check for the end condition for the recursion - the dead node, surrounded by the visited nodes
        if(isVisited[i-1][j]&&isVisited[i][j-1]&&isVisited[i+1][j]&&isVisited[i][j+1])
            return;
            
        //if next entry in current direction has been visited, turn to next direction
        //if next entry in current direction has not been visited, keep going in this direction
        
        //i+di[dir]: i for the next entry in current direction
        //j+dj[dir]: j for the next entry in current direction
        
        if(isVisited[i+di[dir]][j+dj[dir]])
            spiralOrderHelper(matrix, i, j, (dir==3) ? 0 : dir+1, isVisited, list, di, dj);
        else
            spiralOrderHelper(matrix, i+di[dir], j+dj[dir], dir, isVisited, list, di, dj);
    }
    
    public List<Integer> spiralOrder(int[][] matrix) {
        if(matrix==null || matrix.length==0)    return new ArrayList<Integer>();
        
        int[] di = {0, 1, 0, -1};
        int[] dj = {1, 0, -1, 0};
        
        ArrayList<Integer> resultList = new ArrayList<Integer>();
        
        boolean[][] isVisited = new boolean [matrix.length+2][matrix[0].length+2];
        for(int i=0; i<isVisited.length; i++) {
            isVisited[i][0] = isVisited[i][isVisited[0].length-1] = true;
        }
        
        for(int j=0; j<isVisited[0].length; j++) {
            isVisited[0][j] = isVisited[isVisited.length-1][j] = true;
        }
        
        //Dirction: 0: Right    1: Down    2: Left    3: Up
        spiralOrderHelper(matrix, 1, 1, 0, isVisited, resultList, di, dj);
        
        return resultList;
    }

  • 0
    T

    Good for practice, but O(n*m) space + an O(n*m) deep recursion can't compete with an O(1) space and O(n*m) time simple iterative algorithm.

    You can save stack space by putting di and dj as private static final, because they don't change, ever, so it's wasteful to pass the around.


Log in to reply
 

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