Traverse an N * N 2D array in spiral order clock-wise starting from the top left corner. Return the list of traversal sequence.

Assumptions

• The 2D array is not null and has size of N * N where N > = 0

Examples

{ {1, 2, 3},

{4, 5, 6},

{7, 8, 9} }

the traversal sequence is [1, 2, 3, 6, 9, 8, 7, 4, 5]

Solution 1: recursion, 一层一层往内recursion。注意size和offset

  public List<Integer> spiral(int[][] matrix) {
    List<Integer> ans = new ArrayList<>();
    helper(matrix, ans, matrix.length, 0);
    return ans;
  }
  private void helper(int[][] matrix, List<Integer> ans, int size, int offset) {
    if (size == 0) {
      return;
    }
    if (size == 1) {
      ans.add(matrix[offset][offset]);
      return;
    }
    for (int i = 0; i < size - 1; i++) { //每一行/列最后一个元素留作下一个for的头
      ans.add(matrix[offset][offset + i]);
    }
    for (int i = 0; i < size - 1; i++) {
      ans.add(matrix[offset + i][offset + size - 1]);
    }
    for (int i = size - 1; i >= 1; i--) {
      ans.add(matrix[offset + size - 1][offset + i]);
    }
    for (int i = size - 1; i >= 1; i--) {
      ans.add(matrix[offset + i][offset]);
    }
    helper(matrix, ans, size - 2, offset + 1);
  }

Solution 2: iterative，用start和end表示边界

  public List<Integer> spiral(int[][] matrix) {
    List<Integer> ans = new ArrayList<>();
    int start = 0, end = matrix.length - 1;
    while (start < end) {
      for (int i = start; i < end; i++) {
        ans.add(matrix[start][i]);
      }
      for (int i = start; i < end; i++) {
        ans.add(matrix[i][end]);
      }
      for (int i = end; i > start; i--) {
        ans.add(matrix[end][i]);
      }
      for (int i = end; i > start; i--) {
        ans.add(matrix[i][start]);
      }
      start++;
      end--;
    }
    if (start == end) {  //记得要有这
      ans.add(matrix[start][start]);
    }
    return ans;
  }