Solution by awice


  • 0

    Approach #1: Simulation [Accepted]

    Intuition

    Draw the path that the spiral makes. We know that the path should turn clockwise whenever it would otherwise go out of bounds or into a cell that was previously visited.

    Algorithm

    Let the array have R rows and C columns. seen[r][c] denotes that the cell on the r-th row and c-th column was previously visited. Our current position is (r, c), facing direction di, and we want to visit R * C total cells.

    As we move through the matrix, our candidate next position is (cr, cc). If the candidate is in the bounds of the matrix and unseen, then it becomes our next position; otherwise, our next position is the one after performing a clockwise turn.

    Java

    class Solution {
        public List<Integer> spiralOrder(int[][] matrix) {
            List ans = new ArrayList();
            if (matrix.length == 0) return ans;
            int R = matrix.length, C = matrix[0].length;
            boolean[][] seen = new boolean[R][C];
            int[] dr = {0, 1, 0, -1};
            int[] dc = {1, 0, -1, 0};
            int r = 0, c = 0, di = 0;
    
            for (int i = 0; i < R * C; i++) {
                ans.add(matrix[r][c]);
                seen[r][c] = true;
                int cr = r + dr[di];
                int cc = c + dc[di];
                if (0 <= cr && cr < R && 0 <= cc && cc < C && !seen[cr][cc]){
                    r = cr;
                    c = cc;
                } else {
                    di = (di + 1) % 4;
                    r += dr[di];
                    c += dc[di];
                }
            }
    
            return ans;
        }
    }
    

    Python

    class Solution(object):
        def spiralOrder(self, matrix):
            if not matrix: return []
            R, C = len(matrix), len(matrix[0])
            seen = [[False] * C for _ in matrix]
            ans = []
    
            dr = [0, 1, 0, -1]
            dc = [1, 0, -1, 0]
            r = c = di = 0
    
            for _ in range(R * C):
                ans.append(matrix[r][c])
                seen[r][c] = True
                cr, cc = r + dr[di], c + dc[di]
                if 0 <= cr < R and 0 <= cc < C and not seen[cr][cc]:
                    r, c = cr, cc
                else:
                    di = (di + 1) % 4
                    r, c = r + dr[di], c + dc[di]
    
            return ans
    

    Complexity Analysis

    • Time Complexity: $$O(N)$$, where $$N$$ is the total number of elements in the input matrix. We add every element in the matrix to our final answer.

    • Space Complexity: $$O(N)$$, the information stored in seen and in ans.


    Approach #2: Layer-by-Layer [Accepted]

    Intuition

    The answer will be all the elements in clockwise order from the first-outer layer, followed by the elements from the second-outer layer, and so on.

    Algorithm

    We define the k-th outer layer of a matrix as all elements that have minimum distance to some border equal to k. For example, the following matrix has all elements in the first-outer layer equal to 1, all elements in the second-outer layer equal to 2, and all elements in the third-outer layer equal to 3.

    [[1, 1, 1, 1, 1, 1, 1],
     [1, 2, 2, 2, 2, 2, 1],
     [1, 2, 3, 3, 3, 2, 1],
     [1, 2, 2, 2, 2, 2, 1],
     [1, 1, 1, 1, 1, 1, 1]]
    

    For each outer layer, we want to iterate through it's elements in clockwise order starting from the top left corner. Suppose the current outer layer has top-left coordinates (r1, c1) and bottom-right coordinates (r2, c2).

    Then, the top row is (r1, c) for c = c1 ... c2. The rest of the right side is (r, c2) for r = r1+1 ... r2. Then, if there are four sides to this layer (ie., r1 < r2 and c1 < c2), we iterate through the bottom side and left side as shown in the solutions below.

    Java

    class Solution {
        public List<Integer> spiralOrder(int[][] matrix) {
            List ans = new ArrayList();
            if (matrix.length == 0) return ans;
    
            int r1 = 0, r2 = matrix.length - 1;
            int c1 = 0, c2 = matrix[0].length - 1;
            while (r1 <= r2 && c1 <= c2) {
                for (int c = c1; c <= c2; c++) ans.add(matrix[r1][c]);
                for (int r = r1 + 1; r <= r2; r++) ans.add(matrix[r][c2]);
                if (r1 < r2 && c1 < c2) {
                    for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
                    for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
                }
                r1++; r2--;
                c1++; c2--;
            }
            return ans;
        }
    }
    

    Python

    class Solution(object):
        def spiralOrder(self, matrix):
            def spiral_coords(r1, c1, r2, c2):
                for c in range(c1, c2 + 1):
                    yield r1, c
                for r in range(r1 + 1, r2 + 1):
                    yield r, c2
                if r1 < r2 and c1 < c2:
                    for c in range(c2 - 1, c1, -1):
                        yield r2, c
                    for r in range(r2, r1, -1):
                        yield r, c1
    
            if not matrix: return []
            ans = []
            r1, r2 = 0, len(matrix) - 1
            c1, c2 = 0, len(matrix[0]) - 1
            while r1 <= r2 and c1 <= c2:
                for r, c in spiral_coords(r1, c1, r2, c2):
                    ans.append(matrix[r][c])
                r1 += 1; r2 -= 1
                c1 += 1; c2 -= 1
            return ans
    

    Complexity Analysis

    • Time Complexity: $$O(N)$$, where $$N$$ is the total number of elements in the input matrix. We add every element in the matrix to our final answer.

    • Space Complexity: $$O(N)$$, the information stored in ans.


Log in to reply
 

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