Spiral Matrix

Recently I tried to come up with not a fast, but easy to understand solution for one problem which dazzled me for a few days on Leetcode. Following explains the solution in short.

The solution comprises of a single function expression.

const spiralOrder = matrix => {
// ...
}

The initial step we need to take is to utilize a map in order to keep track of cells that we have previously iterated. Our map matrix should have the same number of rows and columns as our main matrix.

We initialize our map matrix by populating each cell with “false”, indicating that nothing has been iterated yet. As we iterate through the main matrix, we will concurrently update the map matrix.

const spiralOrder = matrix => {
  const map = Array(matrix.length).fill().map(row => {
      return Array(matrix[0].length).fill(false)
  })
}

Our final outcome is a one-dimensional array, so we create it, and the final line of the function will return it.

const spiralOrder = matrix => {
  const map = Array(matrix.length).fill().map(row => {
      return Array(matrix[0].length).fill(false)
  })
  const result = []
  // ...
  return result
}

We need a loop that keeps our program running until a certain condition is met. One possible solution is to continue iterating until there are no “false” values remaining in our map array. But how should we implement this logic? Take a look at my solution for more details.

const spiralOrder = matrix => {
  const map = Array(matrix.length).fill().map(row => {
      return Array(matrix[0].length).fill(false)
  })
  const result = []
  while( map.flat().filter(a => !a).length > 0 ) {
    // ...
  }
  return result
}

Another aspect we will implement is a robust method for controlling the direction in which we are traversing within our matrix. To accomplish this, I created a “direction” object with “x” and “y” properties, which I will modify based on specific conditions. These values will be added to our other indices (referred to as “i” and “j”) in every iteration of the “while” loop.

const spiralOrder = matrix => {
  const map = Array(matrix.length).fill().map(row => {
      return Array(matrix[0].length).fill(false)
  })
  const result = []
  const direction = { x: 1, y: 0 }
  let i = 0, j = 0
  
  while( map.flat().filter(a => !a).length > 0 ) {
    i += direction.x
    j += direction.y
  }
  return result
}

Before altering the indices, we record the current element in our “result” array and update the corresponding cell in the map matrix.

const spiralOrder = matrix => {
  const map = Array(matrix.length).fill().map(row => {
      return Array(matrix[0].length).fill(false)
  })
  const result = []
  const direction = { x: 1, y: 0 }
  let i = 0, j = 0
  
  while( map.flat().filter(a => !a).length > 0 ) {
    result.push(matrix[j][i])
    map[j][i] = true
    
    i += direction.x
    j += direction.y
  }
  
  return result
}

The only step remaining is to adjust our current direction as necessary. The only step remaining is to adjust our current direction as necessary.

This includes:
When we are moving rightwards and reach the farthest right cell
When we are moving leftwards and reach the farthest left cell
When we are moving upwards and reach the farthest top cell
When we are moving downwards and reach the farthest bottom cell

const spiralOrder = matrix => {
  const map = Array(matrix.length).fill().map(row => {
      return Array(matrix[0].length).fill(false)
  })
  const result = []
  const direction = { x: 1, y: 0 }
  let i = 0, j = 0

  while( map.flat().filter(a => !a).length > 0 ) {
    if(
      ( direction.x == 1 && i == matrix[0].length - 1 ) ||
      ( direction.x == -1 && i == 0 )                   ||
      ( direction.y == 1 && j == matrix.length - 1 )    ||
      ( direction.y == -1 && j == 0 )                   ||
    ) {
      // ...
    }

    result.push(matrix[j][i])
    map[j][i] = true

    i += direction.x
    j += direction.y
  }
  return result

}

There is one additional scenario in which we may want to change the direction of our traversal: when the next cell in our map matrix is evaluated as “false.”

const spiralOrder = matrix => {
  const map = Array(matrix.length).fill().map(row => {
      return Array(matrix[0].length).fill(false)
  })
  const result = []
  const direction = { x: 1, y: 0 }
  let i = 0, j = 0
  
  while( map.flat().filter(a => !a).length > 0 ) {
    if(
      ( direction.x == 1 && i == matrix[0].length - 1 ) ||
      ( direction.x == -1 && i == 0 )                   ||
      ( direction.y == 1 && j == matrix.length - 1 )    ||
      ( direction.y == -1 && j == 0 )                   ||
      map[j+direction.y][i+direction.x]
    ) {
      // ...
    }
    result.push(matrix[j][i])
    map[j][i] = true
    
    i += direction.x
    j += direction.y
  }
  
  return result
}

Finally, we adjust the direction, and we are done.

const spiralOrder = matrix => {
  const map = Array(matrix.length).fill().map(row => {
      return Array(matrix[0].length).fill(false)
  })
  const result = []
  const direction = { x: 1, y: 0 }
  let i = 0, j = 0
  
  while( map.flat().filter(a => !a).length > 0 ) {
    if(
      ( direction.x == 1 && i == matrix[0].length - 1 ) ||
      ( direction.x == -1 && i == 0 )                   ||
      ( direction.y == 1 && j == matrix.length - 1 )    ||
      ( direction.y == -1 && j == 0 )                   ||
      map[j+direction.y][i+direction.x]
    ) {
      if( direction.x == 1 ) {
        direction.x = 0
        direction.y = 1
      }else if( direction.x == -1 ) {
        direction.x = 0
        direction.y = -1
      }else if( direction.y == 1 ) {
        direction.x = -1
        direction.y = 0
      }else if( direction.y == -1 ) {
        direction.x = 1
        direction.y = 0
      }
    }
    result.push(matrix[j][i])
    map[j][i] = true
    
    i += direction.x
    j += direction.y
  }
  return result
}