public class Solution {
  public List<Integer> spiral(int[][] matrix) {
        List<Integer> res = new ArrayList<Integer>();
        if (matrix.length == 0 || matrix[0].length == 0) return res;
        int left = 0, right = matrix[0].length - 1;
        int up = 0, down = matrix.length - 1;
        helper(matrix, left, right, up, down, res);
        return res;
    }

    public void helper(int[][] matrix, int left, int right, int up, int down, List<Integer> res) {
        if (up > down || left > right) return;
        if (up == down) {
            for (int i = left; i <= right; i++) {
                res.add(matrix[up][i]);
            }
            return;
        }
        if (left == right) {
            for (int i = up; i <= down; i++) {
                res.add(matrix[i][left]);
            }
            return;
        }
        for (int i = left; i < right; i++) {
            res.add(matrix[up][i]);
        }
        for (int i = up; i < down; i++) {
            res.add(matrix[i][right]);
        }
        for (int i = right; i > left; i--) {
            res.add(matrix[down][i]);
        }
        for (int i = down; i > up; i--) {
            res.add(matrix[i][left]);
        }
        helper(matrix, left + 1, right - 1, up + 1, down - 1, res);
    }
}