Interview Questions

  • View all tutorials
  • blank
  • Print a matrix in spiral order
    The input for this problem will be a matrix, or multidimensional array, which will be represented by N arrays each of N length, and your goal is to print the matrix in a spiral order. For example, if the input is:
    [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    then this matrix should be printed out in a list like so:
    [1, 2, 3, 6, 9, 8, 7, 4, 5]
    The spiral begins at the top left of the matrix and loops around it towards the center in a clockwise pattern. Below is a clever algorithm that uses recursion to print a matrix in spiral order:

    Algorithm

    (1) Every other iteration through the matrix peel off the first row and last column of the matrix. So for the above array we should get: [[1, 2, 3], [6, 9]]. Store these elements in a list and then pass the modified matrix to another function. The modified matrix currently looks like this:
    [[4, 5], [7, 8]]
    (2) Now peel off the last row and first column from the matrix, reverse each one, and add them to the previous list. Our spiral list should look like the following so far: [[1, 2, 3], [6, 9], [8, 7], [4]]. (3) Now continue from step 1 until the matrix has no elements left and return the final spiraled list.

    Code

    function layerTopRight(matrix) {
      
      // remove and store the first row from matrix
      var top = matrix.splice(0, 1);
      
      // store the right column of the matrix
      var right = [];
      
      // remove the last column from the matrix
      for (var i = 0; i < matrix.length; i++) {
        var e = matrix[i].splice(-1, 1);  
        right.push(e);
      }
      
      // return the top row and last column elements as a list
      return top.concat(right).toString().split();
      
    }
    
    function layerBottomLeft(matrix) {
      
      // remove and store the last row from matrix in reverse order
      var bottom = matrix.splice(matrix.length-1, 1)[0].reverse();
      
      // store the left column of the matrix
      var left = [];
      
      // remove the first column from the matrix
      for (var i = 0; i < matrix.length; i++) {
        var e = matrix[i].splice(0, 1);  
        left.push(e);
      }
      
      // return the top row and last column elements as a list
      return bottom.concat(left.reverse()).toString().split();
      
    }
    
    // our main spiral function that will
    // return a final spiral ordered list
    function spiral(matrix) {
      
      // where we store our final spiraled list
      var spir = [];
      
      while (matrix.length > 0) {
        
        // if only 1 more element left in matrix
        if (matrix.length === 1) { 
          spir.push(matrix[0]); 
          break;
        }
        
        // return the spiraled list of the top row and
        // right column for this matrix
        var tr = layerTopRight(matrix);
        spir.push(tr);
        
        // return the spiraled list of the bottom row and
        // left column for this matrix
        var bl = layerBottomLeft(matrix);
        spir.push(bl);
    
      }
      
      return spir.toString().split();
      
    }
    
    // setup a matrix
    var M = [[1, 2, 3], 
             [4, 5, 6], 
             [7, 8, 9]];
    
    // return it in spiral order
    spiral(M); 
    
    def layerTopRight(matrix):
      
      # remove and store the first row from matrix
      top = matrix.pop(0)
      
      # store the right column of the matrix
      right = []
      
      # remove the last column from the matrix
      for i in range(0, len(matrix)):
        e = matrix[i].pop()
        right.append(e)
        
      # return the top row and last column elements as a list
      return top + right
    
    def layerBottomLeft(matrix):
      
      # remove and store the last row from matrix in reverse order
      bottom = matrix.pop()[::-1]
      
      # store the left column of the matrix
      left = []
      
      # remove the first column from the matrix
      for i in range(0, len(matrix)):
        e = matrix[i].pop(0)
        left.append(e)
        
      # return the top row and last column elements as a list
      return bottom + left[::-1]
    
    # our main spiral function that will
    # return a final spiral ordered list
    def spiral(matrix):
      
      # where we store our final spiraled list
      spir = []
      
      while len(matrix) > 0:
        
        # if only 1 more element left in matrix
        if len(matrix) == 1:
          spir += matrix[0]
          break
          
        # return the spiraled list of the top row and
        # right column for this matrix
        tr = layerTopRight(matrix)
        spir += tr
        
        # return the spiraled list of the bottom row and
        # left column for this matrix
        bl = layerBottomLeft(matrix)
        spir += bl
        
      return spir
      
      
    # setup a matrix  
    M = [[1, 2, 3],
         [4, 5, 6],
         [7, 8, 9]]
    
    # return it in spiral order
    print spiral(M)     
    
    Run Code
    Run Code

    Running time

    This algorithm runs in O(n2) time, where n represents an n x n matrix, because it needs to loop through the entire matrix at least once to reach every single element. Reversing the bottom row and left column of the matrix on every other iteration adds to the running time, but a fast array reverse algorithm can run in O(n).

    Sources

    http://www.careercup.com/question?id=2991909
    mrdaniel published this on 11/12/15 | array, matrix, Microsoft
    Comments
  • +
  • 4
  • -
  • I tried this way.........
    function spiral(matrix){
      var list= [];
    
      while(matrix.length>1){
    
        //Right
        list= list.concat(matrix.splice(0,1)[0]);
    
        //Down
        for(var idx in matrix){
          list.push(matrix[idx].splice(-1)[0]);
        }
    
        //Left
        list= list.concat(matrix.splice(-1,1)[0].reverse());
    
        //Up
        for(var idx=matrix.length-1;idx>=0;idx--){
          list.push(matrix[idx].splice(0,1)[0]);
        }
    
      }
      
      if(matrix.length>0){
      	list.push(matrix.pop()[0]);
      }
      
      return list;
    }
    
    // setup a matrix
    var M = [[1, 2, 3], 
             [4, 5, 6], 
             [7, 8, 9]];
    
    // return it in spiral order
    spiral(M); 
    
    Login to submit a comment