Spiral Order Print II

Traverse an M * 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 M * N where M, N >= 0

Examples

{ {1, 2, 3, 4},

{5, 6, 7, 8},

{9, 10, 11, 12} }

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

Solution: iterative four pointers, which together outlines the current printing rectangle

Base Case:

Nothing left: left > right || up > down

One row left: up == down

One column left: left == right

Iterative Steps:

Print top side, right side, bottom side, left side

 public class Solution {

  public List<Integer> spiral(int[][] matrix) {
    List<Integer> result = new ArrayList<>();

    int m = matrix.length;
    if (m == 0) return result;
    int n = matrix[0].length;

    

    int left = 0;
    int right = n - 1;
    int up = 0;
    int down = m - 1;

    while (left < right && up < down){
      //top side
      for (int i = left; i <= right; i++){
        result.add(matrix[up][i]);
      }
      //right side
      for (int i = up + 1; i < down; i++){
        result.add(matrix[i][right]);
      }
      //bottom side
      for (int i = right; i >= left; i--){
        result.add(matrix[down][i]);
      }
      //left side
      for (int i = down - 1; i > up; i--){
        result.add(matrix[i][left]);
      }
      left++;
      right--;
      up++; 
      down--;
    }

    //base cases
    //nothing left
    if (left > right || up > down) return result;

    //one column left
    if (left == right){
      for (int i = up; i <= down; i++){
        result.add(matrix[i][left]);
      }
      return result;
    } else { //one row left
      for (int i = left; i <= right; i++){
        result.add(matrix[up][i]);
      }
      return result;
    }
  }
}