An recursive solution JAVA


  • 1

    The idea, start traverse to the right. The next direction after right is down. Actually, the direction is like this: right - down - left - up - right - down - left - up... etc. When should we change direction? If the cell we're traversing has already been visited. The base case is, even after change the direction, the cell is still visited. The code is not so elegant, but just wanna share the idea:)

    public class Solution {
        private static final int[][] DIRS = new int[][]{{0, 1},{1, 0},{0, -1}, {-1, 0}};
        
        public List<Integer> spiralOrder(int[][] matrix) {
            List<Integer> res = new ArrayList<>();
            if (matrix.length == 0 || matrix[0].length == 0) {
                return res;
            }
            
            int m = matrix.length, n = matrix[0].length;
            boolean[][] visited = new boolean[m][n];
            
            search(0, 0, 0, matrix, visited, res);
            return res;
        }
        
        private void search(int x, int y, int index, int[][] matrix, boolean[][] visited, List<Integer> res) {
            res.add(matrix[x][y]);
            visited[x][y] = true;
            
            int[] dir = DIRS[index % 4];
            int i = x + dir[0];
            int j = y + dir[1];
            if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || visited[i][j]) {
                int[] dir2 = DIRS[(++index) % 4];
                i = x + dir2[0];
                j = y + dir2[1];
                if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || visited[i][j]) {
                    return;
                }
            }
            search(i, j, index, matrix, visited, res);
        }
    }
    

Log in to reply
 

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