54. Spiral Matrix.md

54. Spiral Matrix

---

leetcode-cn Daily Challenge on March 15th, 2021.

---

Difficulty : Medium

Related Topics : Array

---

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

---

Solution

• mine
  • Java

    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.3 MB, less than 73.61% of Java online submissions

      // O(N)time
      // O(1)space `(not contain res)`
      // N is matrix element count
      public List<Integer> spiralOrder(int[][] matrix) {
          List<Integer> res = new LinkedList<>();
          if(matrix.length == 0) return res;
          int[][] add = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
          int x = 0 , y = 0;
          int l = -1,  t = -1, r = matrix[0].length, b = matrix.length;
          int index = 0;
          while(res.size() < matrix.length * matrix[0].length){
              res.add(matrix[x][y]);
              if( index % 2 != 0 && (x + add[index][0] <= t || x + add[index][0] >= b)
              || index % 2 == 0 && (y + add[index][1] <= l || y + add[index][1] >= r)){
                  switch(index){
                      case 0 :
                          t++;
                          break;
                      case 1 :
                          r--;
                          break;
                      case 3 :
                          b--;
                          break;
                      default:
                          l++;
                          break;
                  }
                  index = (index + 1) % 4;
              }
              x += add[index][0];
              y += add[index][1];
          }
          return res;
      }
      

    • directions Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.5 MB, less than 47.53% of Java online submissions

      // O(N)time  O(N)space `(not contain res)`
      // N is matrix element count
      public List<Integer> spiralOrder(int[][] matrix) {
          int row, col;
          if (matrix == null
                  || (row = matrix.length) == 0
                  || (col = matrix[0].length) == 0) {
              return new ArrayList<>();
          }
          List<Integer> res = new ArrayList<>(row * col);
          boolean[][] record = new boolean[row][col];
          int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
          int x = 0, y = 0;
          int direction = 0;
          for (int i = 0; i < row * col; i++) {
              res.add(matrix[x][y]);
              record[x][y] = true;
              int nextX = x + directions[direction][0];
              int nextY = y + directions[direction][1];
              if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col || record[nextX][nextY]) {
                  direction = (direction + 1) % directions.length;
              }
              x = x + directions[direction][0];
              y = y + directions[direction][1];
          }
          return res;
      }
      

    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.1 MB, less than 64.94% of Java online submissions

      public List<Integer> spiralOrder(int[][] matrix) {
          List<Integer> res = new ArrayList<>();
          int[][] add = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
          int l = 0, t = 0, r = matrix[0].length - 1, b = matrix.length - 1;
          int x = 0, y = 0;
          int index = 0;
          while (x >= t && y >= l && x <= b && y <= r) {
              res.add(matrix[x][y]);
              int x1 = x + add[index % add.length][0];
              int y1 = y + add[index % add.length][1];
              if (x1 < t || x1 > b || y1 < l || y1 > r) {
                  index++;
                  x += add[index % add.length][0];
                  y += add[index % add.length][1];
                  if (x1 < t) {
                      l++;
                  } else if (x1 > b) {
                      r--;
                  } else if (y1 < l) {
                      b--;
                  } else {
                      t++;
                  }
              } else {
                  x = x1;
                  y = y1;
              }
          }
          return res;
      }
      

---

• the most votes

• Layer-by-Layer Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.5 MB, less than 54.80% of Java online submissions

  // O(N)time  O(N)space `(not contain res)`
  // N is matrix element count
  public List<Integer> spiralOrder(int[][] matrix) {
      List<Integer> res = new ArrayList<Integer>();
      if (matrix.length == 0) {
          return res;
      }
      int rowBegin = 0;
      int rowEnd = matrix.length-1;
      int colBegin = 0;
      int colEnd = matrix[0].length - 1;
  
      while (rowBegin <= rowEnd && colBegin <= colEnd) {
          // Traverse Right
          for (int j = colBegin; j <= colEnd; j ++) {
              res.add(matrix[rowBegin][j]);
          }
          rowBegin++;
  
          // Traverse Down
          for (int j = rowBegin; j <= rowEnd; j ++) {
              res.add(matrix[j][colEnd]);
          }
          colEnd--;
  
          if (rowBegin <= rowEnd) {
              // Traverse Left
              for (int j = colEnd; j >= colBegin; j --) {
                  res.add(matrix[rowEnd][j]);
              }
          }
          rowEnd--;
  
          if (colBegin <= colEnd) {
              // Traver Up
              for (int j = rowEnd; j >= rowBegin; j --) {
                  res.add(matrix[j][colBegin]);
              }
          }
          colBegin ++;
      }
      return res;
  }
  

---