Question

Formatted question description: https://leetcode.ca/all/54.html

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

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].

@tag-array

Algorithm

Define p and q to be the height and width of the current loop. When p or q is 1, it means that the last loop has only one row or one column, and you can jump out of the loop. The difficulty of this question lies in the conversion of subscripts. How to correctly convert subscripts is the key to solving this problem. You can complete the subscripts by referring to the 3x3 example above.

Code

Java

import java.util.ArrayList;
import java.util.List;

public class Spiral_Matrix {

	public class Solution {

	    List<Integer> list = new ArrayList<Integer>();

	    public List<Integer> spiralOrder(int[][] matrix) {
	        if (matrix == null || matrix.length == 0)   return list;

	        int row = matrix.length;
	        int column = matrix[0].length;

	        int leftBoundary = 0, upBoundary = 1;
	        int rightBoundary = column - 1, downBoundary = row - 1; // marking boundary index

	        /*
	            direction: 1 is up, 2 is down, 3 is left, 4 is right
	        */

	        // at beginning direction is right;
	        int direction = 4;
	        int i = 0, j = 0; // initial position of pointer

	        int count = 0;
	        while (count < row * column) { // @note: I see other solutions, with for() inside of while(), maybe a more intuitive way

	            list.add(matrix[i][j]);

	            // switch case
	            if (direction == 1) { // move right

	                if (i == upBoundary) {
	                    direction = 4;
	                    j++;

	                    upBoundary++;

	                } else {
	                    i--;
	                }
	            }

	            else if (direction == 2) {

	                if (i == downBoundary) {
	                    direction = 3;
	                    j--;

	                    // update boundary
	                    downBoundary--;
	                } else {
	                    i++;
	                }
	            }

	            else if (direction == 3) {

	                if (j == leftBoundary) {
	                    direction = 1;
	                    i--;

	                    // update boundary
	                    leftBoundary++;

	                } else {
	                    j--;
	                }
	            }

	            else { // direction == 4

	                // check boundary
	                if (j == rightBoundary) {
	                    direction = 2;
	                    i++;

	                    // row boundary is 1 less now
	                    rightBoundary--;
	                } else {
	                    j++;
	                }

	            }
	            // end of direction switch-case

	            count++;
	        }

	        return list;
	    }
	}

}

All Problems

All Solutions