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?

Possible duplicate of [Print two-dimensional array in spiral order](https://stackoverflow.com/questions/726756/print-two-dimensional-array-in-spiral-order) — tevemadar, Sep 15 '19 at 17:17
@JohnColeman thanks for your answer. I have edit my question. I think is a bit different now. — Mauricio Orozco, Sep 15 '19 at 17:38

Scott Sauyet · Answer 1 · 2019-12-02T16:24:32.487

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]"
  ])
)

spiralOrder is the only function that deals with your somewhat unusual input. spiral, transpose, rotate, and reverse reverse work on plain matrices. (Well, it's JS, so they work on a an array of arrays.)

nice functional deconstruction of the problem ^^ – Mulan Sep 16 '19 at 17:53 — Mulan, Sep 16 '19 at 17:53

Nina Scholz · Accepted Answer · 2019-09-15T20:55:17.993

You could take an approach with four directions and an index pair (i/j), as well as four more variables for limiting the loops with upper and lower bound, as well as left and right limits.

After taking a limit, the limit is checked an incremented or decremented. If the limit is not inside of the wanted range, the loops ends.

At the end, the left over item is added to the result set.

function getSpiral(data) {
    var array = data.map(j => JSON.parse(j)),
        upper = 0,
        lower = array.length - 1,
        left = 0,
        right = array[0].length - 1,
        i = upper,
        j = left,
        result = [];

    while (true) {
        if (upper++ > lower) break;

        for (; j < right; j++) result.push(array[i][j]);
        if (right-- < left) break;

        for (; i < lower; i++) result.push(array[i][j]);
        if (lower-- < upper) break;

        for (; j > left; j--) result.push(array[i][j]);
        if (left++ > right) break;

        for (; i > upper; i--) result.push(array[i][j]);
    }
    result.push(array[i][j]);

    return result.join(',');
}

console.log(getSpiral(['[4, 5, 6, 5]', '[1, 1, 2, 2]', '[5, 4, 2, 9]']));
console.log(getSpiral(['[1, 2, 3, 4, 5]', '[6, 7, 8, 9, 10]', '[11, 12, 13, 14, 15]', '[16, 17, 18, 19, 20]']));

גלעד ברקן · Answer 3 · 2019-09-16T18:55:13.327

We can observe that turns happen (more or less :) on the diagonals. The function, f, is the main, recursive handler, which is basically a for loop.

function turnAndDeltas(direction){
  return {
            // dy dx
    'r': ['d', 0, 1],
    'd': ['l', 1, 0], 
    'l': ['u', 0,-1],
    'u': ['r',-1, 0]
  }[direction]
}

function isDiagonal(h, w, y, x){
  if (x >= w >> 1)
    return (y == w - x - 1) || (h - y - 1 == w - x - 1)
  else if (y > h >> 1)
    return (h - y - 1 == x)
  else
    return (y - 1 == x)
}
 
function f(h, w, d, y, x, count, fun){
  if (count == 0)
    return

  fun(y, x)

  let [_d, dy, dx] = turnAndDeltas(d)

  if (isDiagonal(h, w, y, x))
    [_, dy, dx] = turnAndDeltas(d = _d)

  f(h, w, d, y+dy, x+dx, count-1, fun)
}

function g(h, w, fun){
  f(h, w, 'r', 0, 0, h*w, fun)
}

var m = ["[ 1, 2, 3, 4]",
         "[10,11,12, 5]",
         "[ 9, 8, 7, 6]"]
        
var M = m.map(x => eval(x))

function fun(y, x){
  console.log(M[y][x])
}

g(M.length, M[0].length, fun)

m = ["[ 1, 2, 3]",
     "[10,11, 4]",
     "[ 9,12, 5]",
     "[ 8, 7, 6]"]
     
M = m.map(x => eval(x))

g(M.length, M[0].length, fun)

Any Idea or solution to this matrix challenge?

3 Answers3

Linked