Spiral Matrix


  • 0

    Click here to see the full article post


  • -1
    B

    a = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
    b = []
    nrow = len(a)
    ncol = len(a[0])
    x,y,di = 0, 0, 0
    seen = [[False]*ncol for i in range(nrow)]

    r = [0,1,0,-1]
    c = [1,0,-1,0]

    for i in range(nrow*ncol):
    b.append(a[x][y])
    seen[x][y] = True
    x = x+r[di]
    y = y+c[di]
    if 0 <= x < nrow and 0<=y<ncol and not seen[x][y]:
    pass
    else:
    x = x-r[di]
    y = y-c[di]
    di = (di+1)%4
    x, y = x + r[di],y + c[di]
    return b


  • 0
    R

    Can be done with O(N) time complexity and O(1) space complexity.


  • 0
    C

    Layer by layer code could be more readable. Here is mine:

    class Solution {
        public List<Integer> spiralOrder(int[][] matrix) {
            ArrayList<Integer> sol = new ArrayList<Integer>();
            
            // if those jerks gave us an array instead of a matrix
            if(matrix.length == 0){
                return sol;
            }
            
            // sides of the box we are spiralling at right now
            int top, left, bottom, right;
            top = left = 0;
            bottom = matrix.length - 1;
            right = matrix[0].length - 1;
            
            // stop when we shrink the box to nothing
            while(left <= right && top <= bottom){
                // top side - left to right
                for(int i = left; i <= right; i++){
                    sol.add(matrix[top][i]);                
                }
                top++;
                // right side - top to bottom
                for(int i = top; i <= bottom; i++){
                    sol.add(matrix[i][right]);
                }
                right--;
                
                // if our box only has one row, top and
                // bottom will be the same, make sure we're not
                // on the last row and then proceed to go
                // through the bottom side
                if(top <= bottom){
                    // bottom side - right to left
                    for(int i = right; i >= left; i--){
                        sol.add(matrix[bottom][i]);
                    }
                    bottom--;
                }
                // now check for one column
                if(left <= right){
                    // left side - bottom to top
                    for(int i = bottom; i >= top; i--){
                        sol.add(matrix[i][left]);
                    }
                    left++;
                }
            }
            return sol;
        }
    }
    

  • 0
    C

    oops maybe highlight java

    class Solution {
        public List<Integer> spiralOrder(int[][] matrix) {
            ArrayList<Integer> sol = new ArrayList<Integer>();
            
            // if those jerks gave us an array instead of a matrix
            if(matrix.length == 0){
                return sol;
            }
            
            // sides of the box we are spiralling at right now
            int top, left, bottom, right;
            top = left = 0;
            bottom = matrix.length - 1;
            right = matrix[0].length - 1;
            
            // stop when we shrink the box to nothing
            while(left <= right && top <= bottom){
                // top side - left to right
                for(int i = left; i <= right; i++){
                    sol.add(matrix[top][i]);                
                }
                top++;
                // right side - top to bottom
                for(int i = top; i <= bottom; i++){
                    sol.add(matrix[i][right]);
                }
                right--;
                
                // if our box only has one row, top and
                // bottom will be the same, make sure we're not
                // on the last row and then proceed to go
                // through the bottom side
                if(top <= bottom){
                    // bottom side - right to left
                    for(int i = right; i >= left; i--){
                        sol.add(matrix[bottom][i]);
                    }
                    bottom--;
                }
                // now check for one column
                if(left <= right){
                    // left side - bottom to top
                    for(int i = bottom; i >= top; i--){
                        sol.add(matrix[i][left]);
                    }
                    left++;
                }
            }
            return sol;
        }
    }
    

  • 0
    C

    maybe not...


  • 0
    A

    public List<Integer> spiralOrder(int[][] matrix) {

    	 if (matrix.length == 0) {
    		 return new ArrayList<>();
    	 }
    	 
    	 List<Integer> list = new ArrayList<>();
    	 
    	 toSpiralOrder(matrix, 0, 0, matrix.length, matrix[0].length, list);
    	 
    	 return list;
            
     }
     
     public void toSpiralOrder(int[][] matrix, int startRow, int startColumn, int endRow, int endColumn, List<Integer> accumulator) {
    	 
    	 if (startRow >= endRow || startColumn >= endColumn) {
    		 return;
    	 }
    	 
    	 if (startRow == endRow - 1  && endColumn - 1 == startColumn) {
    		 accumulator.add(matrix[startRow][endRow-1]);
    		 return;
    	 } else if (startRow == endRow - 1 && endColumn - 1 > startColumn) {
    		 while (startColumn < endColumn) {
    			 accumulator.add(matrix[endRow - 1][startColumn++]);
    		 }
    		 return;
    	 } else if (endColumn - 1 == startColumn && endRow - 1 > startRow) {
    		 while (startRow < endRow) {
    			 accumulator.add(matrix[startRow++][endColumn - 1]);
    		 }
    		 return;
    	 }
    	 
    	 for (int i = startColumn ; i < endColumn - 1 ; i++) {
    		 accumulator.add(matrix[startRow][i]);
    	 }
    	 
    	 for (int i = startRow ; i < endRow - 1 ; i++) {
    		 accumulator.add(matrix[i][endColumn - 1]);
    	 }
    	 
    	 for (int i = endColumn - 1 ; i > startColumn ; i--) {
    		 accumulator.add(matrix[endRow - 1][i]);
    	 }
    	 
    	 for (int i = endRow - 1 ; i > startRow ; i--) {
    		 accumulator.add(matrix[i][startColumn]);
    	 }
    	 
    	 toSpiralOrder(matrix, startRow + 1, startColumn + 1, endRow - 1, endColumn - 1, accumulator);
     }

  • 0
    A

    //Solution in C#

    using System;
    using System.Collections;
    using System.Collections.Generic;

    public class Program
    {
    public static void Main()
    {
    //matrix declaration
    //int[,] matrix = new int[4,4]{{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
    int[,] matrix = new int[4,3]{{1,2,3},{5,6,7},{9,10,11},{13,14,15}};

    	if (matrix.Length == 0) 
    	{
    	 Console.WriteLine("Please define Matrix ");
    		
     	}
     
     List<int> list = new List<int>();
     
    	//matrix.GetLength(0) gives "Row length(First dimension size)" and matrix.GetLength(1) gives "column length(Second dimenstion size)"
     SpiralOrder(matrix, 0, 0, matrix.GetLength(0), matrix.GetLength(1), list);
     
    	//Display the Spiral order
     foreach(int l in list)
    	 Console.Write(l+ " " );
    }
    
    	
    public static void SpiralOrder(int[,] matrix, int startRow, int startColumn, int endRow, int endColumn, List<int> accumulator) {
     
     if (startRow >= endRow || startColumn >= endColumn) {
    	 return;
     }
     
     if (startRow == endRow - 1  && endColumn - 1 == startColumn) {
    	 accumulator.Add(matrix[startRow,endRow-1]);
    	 
     } else if (startRow == endRow - 1 && endColumn - 1 > startColumn) {
    	 while (startColumn < endColumn) {
    		 accumulator.Add(matrix[endRow - 1,startColumn++]);			 
    	 }
    	 return;
     } else if (endColumn - 1 == startColumn && endRow - 1 > startRow) {
    	 while (startRow < endRow) {
    		 accumulator.Add(matrix[startRow++,endColumn - 1]);			 
    	 }
    	 return;
     }
     
    	// Adds first row of the matrix from 0 to Last but one element , to the Final array.
     for (int i = startColumn ; i < endColumn - 1 ; i++) {
    	 accumulator.Add(matrix[startRow,i]);
    	
     }		 
     
    	// Adds Last column elements from top to (bottom-1) to the Final array.
     for (int i = startRow ; i < endRow - 1 ; i++) {
    	 accumulator.Add(matrix[i,endColumn - 1]);
     }
    			
     // Adds Last row elements from right to (extreme left-1) to the Final array.
     for (int i = endColumn - 1 ; i > startColumn ; i--) {
    	 accumulator.Add(matrix[endRow - 1,i]);
     }
    
    	// Adds First column elements from bottom to (top+1) to the Final array.
     for (int i = endRow - 1 ; i > startRow ; i--) {
    	 accumulator.Add(matrix[i,startColumn]);
     }	
     
    	//Increment Start row and Start column by 1 and also decrement EndRow and End Column by 1 and the call the recursive function
     SpiralOrder(matrix, startRow + 1, startColumn + 1, endRow - 1, endColumn - 1, accumulator);
    

    }

    }


  • 0
    P

    Good solution


  • -1
    W

    //this is my solution ,it is accepted!
    /**
    * 分析:
    * 1.设置4个point,left,right,top,bottom
    * 2.当left<=right||top<=bottom,循环
    * 1)→:for(int i= left;i<=right;i++) list.add(matrix[top][i]) top++;
    * 2)↓: for(int i =top;i<=bottom;i++) list.add(matrix[i][right]) right--;
    * 3)←: for(int i =right;i>=left;i--) list.add(matrix[bottom][i]) bottom--;
    * 4)↑: for(int i =bottom;i>=top;i--) list.add(matrix[i][left]) left++;
    *
    */
    //初始化
    List<Integer> list =new ArrayList<>();
    if(matrix.length==0) return list;
    int left = 0;
    int right =matrix[0].length-1;
    int top =0;
    int bottom =matrix.length-1;
    while(left<=right||top<=bottom) {
    if(top<=bottom) {
    for(int i= left;i<=right;i++) {
    list.add(matrix[top][i]);
    }
    top++;
    }

    		if(left<=right) {
    			for(int i =top;i<=bottom;i++) {
    				list.add(matrix[i][right]);
    			
    			}
    			right--;
    		}
    		if(top<=bottom) {
    			for(int i =right;i>=left;i--) {
    				list.add(matrix[bottom][i]) ;
    				
    			}
    			bottom--;
    		}
    		if(left<=right) {
    			for(int i =bottom;i>=top;i--) {
    				list.add(matrix[i][left]) ;
    			
    			}
    			left++;
    		}
    		
    	}
    	return list;

  • 0
    S

    // Another way
    class Solution {
    public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
    std::vector<int> ret;
    if (0 == matrix.size()) return ret;

        int r = 0, c = 0, round = 0;
        int n = matrix.size(), m = matrix[0].size(), cnt = m*n; --n; --m;
        int dx[kDirections] = {1, 0, -1,  0};
        int dy[kDirections] = {0, 1,  0, -1};
        
        ret.push_back(matrix[r][c]);
        Dirs_ dir = right;
        for (int i = 1; i < cnt; ++i) {
            if (0 == m) dir = down;
            r += dy[dir];
            c += dx[dir];
            ret.push_back(matrix[r][c]);
            if (0 == m) continue;
    
            if      (right == dir && c == m-round) { dir = down;           }
            else if (down  == dir && r == n-round) { dir = left;           }
            else if (left  == dir && c ==   round) { dir = up;             }
            else if (up    == dir && r == 1+round) { dir = right; ++round; }
            
        }
        return ret;
    }
    

    private:
    enum Dirs_ { right, down, left, up };
    const int kDirections = 4;
    };


Log in to reply
 

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