Java Solution with explanation


  • 0
    L

    I got it mostly right failing a few cases initially. The tricky part was to realize that you should end the iteration when you have already visited the m*n items of the matrix. The idea is:

    Start with 4 variables : top_row, left_col, bottom_row,right_col
    As evident with their names, these will set the boundaries of the matrix. So let us do the following in that sequence:

    a. Go left--->right and top_row++
    b. Go top--->down and right_col--
    c. Go right--->left and bottom_row--
    d. Go bottom-->up and left_col++

    This mostly works but it will fail for matrix such as {{1,2}} as it will work on the same elements twice. So the trick is to check a condition if size(m*n)>list.size(). Code is below:

    public List<Integer> spiralOrder(int[][] matrix)
      {
        if(matrix.length==0) {
            return Collections.EMPTY_LIST;
        }
        int top_row = 0;
        int left_col = 0;
        int bottom_row = matrix.length - 1;
        int right_col = matrix[0].length - 1;
        // Each complete rotation will change the range to restrict it.
        List<Integer> list = new ArrayList<>();
        int size = matrix.length * matrix[0].length;
        while (top_row <= bottom_row
            && left_col <= right_col)
        {
          for (int i = left_col; i <= right_col
              && size > list.size(); i++)
          {
            list.add(matrix[top_row][i]);
          }
          top_row++;
          for (int i = top_row; i <= bottom_row
              && size > list.size(); i++)
          {
            list.add(matrix[i][right_col]);
          }
          right_col--;
          for (int i = right_col; i >= left_col
              && size > list.size(); i--)
          {
            list.add(matrix[bottom_row][i]);
          }
          bottom_row--;
          for (int i = bottom_row; i >= top_row
              && size > list.size(); i--)
          {
            list.add(matrix[i][left_col]);
          }
          left_col++;
        }
        return list;
      }
    

Log in to reply
 

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