Leetcode 54 Spiral Matrix

Spiral Matrix – LeetCode

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

This is indeed a very interesting problem. If we simulate the process, there are a couple of key points to notice:

The sequence of directions matters – as it’s a spiral, it always goes right first, then down following by left and up, then right again etc.
- We can use a hashTable/map for this, keyed by the current direction, value is the next direction if I need to change direction.

const directionsMap = {
        right: 'down',
        down: 'left',
        left: 'up',
        up: 'right'
    }

When we are at a certain cell noted by (x, y), and the currentDirection, how do we check what’s the coordinates of the next cell if we keep the same direction?
- We can do this by updating the value of x or y.

const getNextCell = (direction, x, y) => {
        if(direction === 'right') {
            return [ x, y + 1 ]
        } else if(direction === 'down') {
            return [x + 1, y]
        } else if(direction === 'up') {
            return [x - 1, y]
        } else {
            return [x, y - 1]
        }
    }

When we are at a certain cell noted by (x, y), how do we check what’s the next direction?
- First of all, we can assume that we will keep the same direction and see which cell it takes us to, we can do that by calling the getNextCell function defined above.
- Once we have the new x and y, we can check if they are valid by:
  - see if they are out of bound
  - OR the cell has already been visited
Obviously this is going to use some kind of a loop, how do we design the loop and when should it end?
- I’m using a while loop, at each iteration, I’m pushing the cell value into the result array. So all I need to do is to check if the result array length is smaller than the number of cells in the matrix

Solution

Javascript:

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {

    // key: currentDirection
    // value: next direction if currentDirection is done
    const directionsMap = {
        right: 'down',
        down: 'left',
        left: 'up',
        up: 'right'
    }

    let totalCells = matrix.length * matrix[0].length
    let x = 0
    let y = 0
    let currentDirection = 'right'
    let result = []

    // record the cell that are already visited
    let visitedMap = {}

    const getNextCell = (direction, x, y) => {
        if(direction === 'right') {
            return [ x, y + 1 ]
        } else if(direction === 'down') {
            return [x + 1, y]
        } else if(direction === 'up') {
            return [x - 1, y]
        } else {
            return [x, y - 1]
        }
    }

    const nextDirection = (currentDirection, x, y) => {
        const [nextX, nextY] = getNextCell(currentDirection, x, y)
        if(visitedMap[`${nextX}-${nextY}`] || nextY === matrix[0].length || nextY < 0 || nextX === matrix.length || nextX < 0) {
            return directionsMap[currentDirection]   
        } else {
            return currentDirection
        }
    }

    while(result.length < totalCells) {
        visitedMap[`${x}-${y}`] = true;
        result.push([matrix[x][y]]);
        currentDirection = nextDirection(currentDirection, x, y)
        const nextCell = getNextCell(currentDirection, x, y)
        x = nextCell[0]
        y = nextCell[1]
    }

    return result
};

Time Complexity:
O(m*n) since we visited all the cells in the matrix

Space Complexity:
O(1)

Leetcode 54 Spiral Matrix

Leetcode 54 Spiral Matrix

Solution

Leave a Reply Cancel reply