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);
    

    }

    }


Log in to reply
 

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