Solution by <monkeykingyan>


  • 2

    Approach #1 Using Assitant Matrix

    Intuition

    This method is straight forward,
    we are using an assistant matrix to help us
    to record the visiting information,
    i.e. when we meet the board or the element in the matrix has been visited,
    we have to change the direction.

    Algorithm

    Here are some comments before going into the strategy:
    1. we can visit all the elements in matrix[m,n] in m*n steps, so the loop is m*n and time complexity is $O(m*n)$
    2. there are 4 directions, right ->down -> left -> up and the back to the right, the order of the direction will not change.
       which means after going right and we have to change direction to down for sure.
    3. how can we check if we have to change the direction or not?
       a) when we reach the border of the matrix;
       b) when we reach the elements we have been visited;
    
    The strategy is as follows:
    Step1: denote num_row as matrix.row_length, num_col as matrix.column_length
           and initial checker[][] which help us to check if the elements in the matrix has been visited or not
    Step2: while not finish visiting all the elements in matrix
            -> check if can continue to go right
                if yes
                  continue to go right and add the element in the result list
                  set the position in checker as true;
            -> check if can continue to go down
                if yes
                  continue to go down and add the element in the result list
                  set the position in checker as true;
            -> check if can continue to go left
                if yes
                  continue to go left and add the element in the result list
                  set the position in checker as true;
            -> check if can continue to go up
                if yes
                  continue to go up and add the element in the result list
                  set the position in checker as true;
    Step3: return result list.
    
    
    

    Java

    public class Solution {
    
    	public List<Integer> spiralOrder(int[][] matrix) {
    		List<Integer> res = new ArrayList<>();
    		if (matrix.length == 0)
    			return res;
    
    		int num_row = matrix.length;
    		int num_col = matrix[0].length;
    		boolean[][] checker = new boolean[num_row][num_col];
    
    		// Initial
    		int row = 0, col = 0, flag = 0;
    		res.add(matrix[row][col]);
    		checker[row][col] = true;
    
    		while (flag<num_row*num_col-1) {
    			// move right
    			while ((col + 1 < num_col) && (checker[row][col + 1] == false)) {
    				col++;
    				flag++;
    				res.add(matrix[row][col]);
    				checker[row][col] = true;
    			}
    
    			// move down
    			while ((row + 1 < num_row) && (checker[row + 1][col] == false)) {
    				row++;
    				flag++;
    				res.add(matrix[row][col]);
    				checker[row][col] = true;
    			}
    
    			// move left
    			while ((col > 0) && (checker[row][col - 1] == false)) {
    				col--;
    				flag++;
    				res.add(matrix[row][col]);
    				checker[row][col] = true;
    			}
    
    			// move up
    			while ((row > 0) && (checker[row - 1][col] == false)) {
    				row--;
    				flag++;
    				res.add(matrix[row][col]);
    				checker[row][col] = true;
    			}
    		}
    		return res;
    	}
    }
    

    Complexity Analysis

    • Time complexity : $$O(m*n)$$. where m and n are rows and columns,
      we just need to check all the elements in the matrix, and no repeat visiting.

    • Space complexity: $$O(mn)$$, we use checker matrix to store the visited elements information. and mn length result list.


    Approach #2 Without Assisting Matrix [Accepted]

    Can we do better? Can we design an algorithm not using helper matrix? Yes,
    The strategy is: update matrix border.
    1.png
    As shown in the picture, every time we change the direction, we have to update border. For example,
    first, we go right as possible as we can and set blue as the new top border.
    So we can not visit the first row anymore, the highest row we can visit becomes the second row (row+1)...
    Therefore, we can implement the traverse strategy by updating the border.

    Algorithm

    while(topBoarder<=bottomBoarder && leftBoarder <= rightBoarder)
        1. go right as much as possible (when visiting the right border, go to 2)
           increase top border;
        2. go down as much as possible (when visiting the bottom border, go to 3)
           decrease right border;
        3. go left as much as possible (when visiting the left border, go to 4)
           decrease bottom border;
        4. go up as much as possible (when visiting the top border, back loop)
           increase left boarder;
    

    Java

    public class Solution {
    
    	public List<Integer> spiralOrder(int[][] matrix) {
    
    		List<Integer> res = new ArrayList<>();
    
    		if (matrix.length == 0) {
    			return res;
    		}
    
    		int topBorder = 0, bottomBorder = matrix.length - 1;
    		int leftBorder = 0, rightBorder = matrix[0].length - 1;
    
    		while (topBorder <= bottomBorder && leftBorder <= rightBorder) {
    			// Traverse Right
    			for (int j = leftBorder; j <= rightBorder; j++) {
    				res.add(matrix[topBorder][j]);
    			}
    			topBorder++;
    
    			// Traverse Down
    			for (int j = topBorder; j <= bottomBorder; j++) {
    				res.add(matrix[j][rightBorder]);
    			}
    			rightBorder--;
    
    			if (topBorder <= bottomBorder) {
    				// Traverse Left
    				for (int j = rightBorder; j >= leftBorder; j--) {
    					res.add(matrix[bottomBorder][j]);
    				}
    			}
    			bottomBorder--;
    
    			if (leftBorder <= rightBorder) {
    				// Traverse Up
    				for (int j = bottomBorder; j >= topBorder; j--) {
    					res.add(matrix[j][leftBorder]);
    				}
    			}
    			leftBorder++;
    
    		}
    		return res;
    	}
    }
    
    
    

    A Comment
    Please pay attention that before go in traverse left loop and traverse up loop,
    there is an if statement. Why we need this?

    Because that the top Boarder and right border have been updated.
    if top Border > bottom Boarder which means the row == top Border == bottom Boarder has been visited, we do not need to visit once more.
    In a word, this is to avoid duplications.

    for example: the matrix just have one row {{1,2,3}};

    after the traverse right loop, top boarder = 1;

    after the traverse down loop, right boarder = 1;

    not go into traverse left loop where top boarder = 1 > bottom boarder = 0;

    not go into traverse up loop where top boarder = 1 > bottom boarder = 0;

    Complexity Analysis

    • Time complexity : $$O(m*n)$$.

    • Space complexity : $$O(mn)$$. we use result list which length is mn

    Video Explanation
    Solution 54


Log in to reply
 

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