javascript - Any Idea or solution to this matrix challenge?

Question

Hi I'm newbie practicing algorithms, I was just wondering how to solve this spiral matrix Challenge:

Have the function MatrixSpiral(strArr) read the array of strings stored in strArr which will represent a 2D N matrix, and your program should return the elements after printing them in a clockwise, spiral order. You should return the newly formed list of elements as a string with the numbers separated by commas. For example: input:

["[4, 5, 6, 5]",   
 "[1, 1, 2, 2]",  
 "[5, 4, 2, 9]"]   

output:

"4,5,6,5,2,9,2,4,5,1,1,2"

I have done simple matrix spiral before, but don't know how to solve one like this.

This is not a simple matrix spiral. I tried with this code, but output is way different

The input is an array of "string arrays" (see the double quotes), and the output should be a string with the numbers separated by commas.

const spiralOrder = (matrix) => {

if(!matrix.length || !matrix[0].length){
        return [];
}
//Use 4 pointes to create wall around square
let rowBegin = 0,
    rowEnd = matrix.length - 1,
    colBegin = 0,
    colEnd = matrix[0].length - 1;

let result = [];
while(rowBegin <= rowEnd && colBegin <= colEnd){

    //move right
    for(let i= colBegin; i<= colEnd; i++){
            result.push(matrix[rowBegin][i]);
    }
    rowBegin++; // mark row as traversed after moving right

    //move down
    for(let i=rowBegin; i<= rowEnd; i++){
            result.push(matrix[i][colEnd]);
    }
    colEnd--; //mark column as traversed after moving down

    //move left
    if(rowBegin <= rowEnd){
            for(let i=colEnd; i >= colBegin; i--){
                    result.push(matrix[rowEnd][i]); 
            }
    }
    rowEnd--; //mark end row as traversed after moving left

    //move up
    if(colBegin <= colEnd){ 
            for(let i=rowEnd; i >= rowBegin; i--){
                    result.push(matrix[i][colBegin]);
            }
    }
    colBegin++; //mark begining column as traversed after moving up
}

return result;
};

spiralOrder([[4, 5, 6, 5], [1, 1, 2, 2], [5, 4, 2, 9]])

Output: [ '[',
  '4',
  ',',
  ' ',
  '5',
  ',',
  ' ',
  '6',
  ',',
  ' ',
  '5',
  ']',
  ']',
  ']',
  '9',
  ' ',
  ',',
  '2',
  ' ',
  ',',
  '4',
  ' ',
  ',',
  '5',
  '[',
  '[',
  '1',
  ',',
  ' ',
  '1',
  ',',
  ' ',
  '2',
  ',',
  ' ',
  '2' ]

Could you please share any solution?

Answer 1

A somewhat different approach, one that fits the "recursion" tag, is to note that one good way to handle a spiral is to take the top row, remove it, rotate the matrix counterclockwise, and repeat until you've completed all rows. It looks something like this:

->  4 5 6 5  --------------+ 
    1 1 2 2  \_ rotate     |
    5 4 2 9  /          ___V___
                       [4 5 6 5]
                        -------

->  2 9  ------------------------+         
    2 2                         |
    1 4  +- rotate               |
    1 5 /                       _V_
                       [4 5 6 5 2 9]
                                ---

->  2 4 5  ---------------------------+  
    2 1 1  >- rotate                __V__
                       [4 5 6 5 2 9 2 4 5]  
                                    -----

->  1  -----------------------------------+
    1  \_ rotate                          |
    2  /                                  V
                       [4 5 6 5 2 9 2 4 5 1]  
                                          - 

->  1 2  ------------------------------------+
                                            _V_
                       [4 5 6 5 2 9 2 4 5 1 1 2]  
                                            ---

And we can write a counterclockwise rotation function just by reversing the result of transposing the matrix. A transposition is flipping it over the Northwest/Southeast diagonal. For example:

  transpose([[1, 2, 3], 
             [4, 5, 6]])

  //=>      [[1, 4],
  //         [2, 5],
  //         [3, 6]]

reversing those rows, we get

  //        [[3, 6],
  //         [2, 5],
  //         [1, 4]]

which is a counter-clockwise rotation of the input.

So the code, involving a few reusable functions, might look like this:

const reverse = a => 
  [...a] .reverse ();

const transpose = m => 
  m [0] .map ((c, i) => m .map (r => r [i]))

const rotate = m => 
  reverse (transpose (m))

const spiral = m => m .length < 2
  ? [... m [0]]
  : [... m [0], ... spiral (rotate (m .slice (1))) ] 

const spiralOrder = (strs) => 
  spiral (strs .map (row => JSON .parse (row)) ) .join (',')


console .log (
  spiralOrder(["[4, 5, 6, 5]",   
               "[1, 1, 2, 2]",  
               "[5, 4, 2, 9]"
  ])
)