Concise DFS solution


  • 0
    S
    1. Visit every cell using DFS.
    2. Direction for visiting next cell is based current direction.
    3. Current direction is passed to the recursive function.
    public class Solution {
        
        public static final int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
        public List<Integer> spiralOrder(int[][] matrix) {
            if ( matrix == null || matrix.length == 0 || matrix[0].length == 0 ) {
                return Collections.EMPTY_LIST;
            }  
            List<Integer> result = new ArrayList<Integer>();
            _spiralOrder( matrix, 0, 0, result, new boolean[matrix.length][matrix[0].length], 0);
            return result;
        }
        
        private void _spiralOrder(int[][] matrix, int row, int col, List<Integer> result, boolean[][] visited, int dir ) {
            if ( row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length || visited[row][col]) {
                return;
            }
            
            result.add( matrix[row][col]);
            visited[row][col] = true;
            
            for ( int i=0; i< dirs.length; i++ ) {
                _spiralOrder(matrix, row + dirs[dir][0], col +  + dirs[dir][1], result, visited, dir);
                dir++;
                dir = dir%4;
            }
        }
    }
    

Log in to reply
 

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