54. Spiral Matrix

 

Spiral Matrix

Problem Description

Given an m x n matrix, return all elements of the matrix in spiral order.

 

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

Approach) Better Brute Force

let spiralOrder = function(matrix) {
    function moveForward() {
        if (dir.x > 0) {
            if (pos.col < walls.col.end) {
                // go right
                ++pos.col;
            } else {
                // hit the right wall, rotate and go down, update wall row start
                dir.x = 0;
                dir.y = 1;
                ++pos.row;
                ++walls.row.start;
            }
        } else if (dir.y > 0) {
            if (pos.row < walls.row.end) {
                // go down
                ++pos.row;
            } else {
                // hit the bottom wall, rotate and go left, update wall col end
                dir.y = 0;
                dir.x = -1;
                --pos.col;
                --walls.col.end;
            }
        } else if (dir.x < 0) {
            if (pos.col > walls.col.start) {
                // go left
                --pos.col;
            } else {
                // hit the left wall, rotate and go up, update wall row end
                dir.x = 0;
                dir.y = -1;
                --pos.row;
                --walls.row.end;
            }
        } else if (dir.y < 0) {
            if (pos.row > walls.row.start) {
                // go up
                --pos.row;
            } else {
                // hit the top wall, rotate and go right, update wall col start
                dir.y = 0;
                dir.x = 1;
                ++pos.col;
                ++walls.col.start;
            }
        }
    }

    if (matrix.length < 1) {
        return [];
    }

    let walls = {
        row: { start: 0, end: matrix.length - 1 },
        col: { start: 0, end: matrix[0].length - 1 }
    };
    let dir = { x: 1, y: 0 };
    let pos = { row: 0, col: 0 }, res = [], len = matrix.length * matrix[0].length;
    while (res.length < len) {
        res.push(matrix[pos.row][pos.col]);
        moveForward();
    }
    return res;
};

Approach) Recursion

var spiralOrder = function(matrix) { 
    if(matrix.length == 0) {
        return []
    }
    let m = matrix.length;
    let n = matrix[0].length;

    return spiralOrderHelper(matrix, 0, 0, m-1, n-1);
};

var spiralOrderHelper = function(matrix, startRow, startCol, endRow, endCol) {
    let result = [];
    
    if (startRow > endRow || startCol > endCol) {
        return []
    }
    
    if(startRow == endRow) {
        for(let i = startCol; i <= endCol; i++) {
            result.push(matrix[startRow][i])
        }
        return result;
    }
    
     if(startCol == endCol) {
        for(let i = startRow; i <= endRow; i++) {
            result.push(matrix[i][startCol])
        }
         return result;
    }
    
    for(let i = startCol; i < endCol; i++) {
        result.push(matrix[startRow][i])
    }
    for(let i = startRow; i < endRow; i++) {
        result.push(matrix[i][endCol])
    }
    for(let i = endCol; i > startCol; i--) {
        result.push(matrix[endRow][i])
    }
    for(let i = endRow; i > startRow; i--) {
        result.push(matrix[i][startCol])
    }
    
    let spiralArr = spiralOrderHelper(matrix, startRow + 1, startCol + 1, endRow - 1, endCol - 1);
    
    return result.concat(spiralArr);
}

Approach) One Liner

function spiral(m) {
  return m.shift().concat(m.length ? spiral(m[0].map((_,i) => m.map(x => x[i])).reverse()) : [])
}

the same code but expanded:

function spiral(matrix) {
  if (!matrix.length) return matrix;
  const firstRow = matrix.shift();
  const transponsed = matrix[0].map((a, i) => {
    return matrix.map(row => row[i]);
  });
  const rotated = transponsed.reverse(); // rotated 90*
  return firstRow.concat(spiral(rotated));
}

he same logic but in the diagram:

|1 2 3|      |6 9|      |8 7|      |4|  =>  |5|  =>  ||
|4 5 6|  =>  |5 8|  =>  |5 4|  =>  |5|
|7 8 9|      |4 7|

// rows extracted:

|1 2 3|      |6 9|      |8 7|      |4|      |5|

the same logic but in english:

1. Remove the first row and add it to the answer
2. Rotate the reminder of the matrix 90* counter clockwise
3. Repeat step 1 and 2 until there's no more rows

Conclusion

That’s all folks! In this post, we solved LeetCode problem 54. Spiral Matrix

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!